How to implement the lu function for fixed-point data types?

Hi there,

I'd like to implement fixed point functionality for lu. Unfortunately, I don't see any support in Matlab because I'd have to convert the fixed-point data to floating-point before using the lu function.

However, converting the data back to floating-point for the computation would defeat the goal of using fixed-point data types.

Here's my implementation; any help would be greatly appreciated if I could convert to fixed point.

Below is my code

% test bench
n = 5;
num_tests = 100;
testInvertMatrix(n, num_tests);

function max_error = testInvertMatrix(n, num_tests)
% Initialize the maximum error
max_error = 0;

% Run the test cases
for i = 1:num_tests
    % Generate a random matrix
    A = rand(n);
    
    % Compute the inverse of A using both fixed-point and floating-point
    [A_inv_fixed, A_inv_float] = invertMatrix(A);
    % I am observing following error 
    % Error using lu
    % Invalid data type. First argument must be double or single.
    
    % Compute the error
    error = norm(double(A_inv_fixed) - A_inv_float, 'fro');
    
    % Update the maximum error
    max_error = max(max_error, error);
end

% Display the maximum error
fprintf('The maximum error over %d test cases is %e\n', num_tests, max_error);
end

function [A_inv_fixed, A_inv_float] = invertMatrix(A)
% Convert the matrix to fixed-point
A_fixed = fi(A, 1, 16, 15);  % 1 sign bit, 16 total bits, 15 fraction bits

% Compute the LU decomposition of A for both fixed-point and floating-point
[L_fixed, U_fixed, P_fixed] = lu(A_fixed);
[L_float, U_float, P_float] = lu(A);

% Compute the inverse of A using the custom algorithm for both fixed-point and floating-point
A_inv_fixed = mldivide(U_fixed, mldivide(L_fixed, mldivide(P_fixed, eye(size(A_fixed)))));
A_inv_float = mldivide(U_float, mldivide(L_float, mldivide(P_float, eye(size(A)))));
end

[John D'Errico]

Yes. I know you WANT to do this. BUT my gut just screams at how bad of an idea this is.

I am sure you can find pseudo-code for an LU online. You can even find a pretty simple LU scheme in MATLAB, that you could then hack to use fixed point data types.

The probem is, subtractive cancellation and division will kill you in fixed point, especially when you are looking at very small numbers of bits. 15 bits, plus a sign bit for 16 total bits?

[Life is Wonderful]

Absolutely perfect!! Division is the one I dislike the most.

Answer 1

[Andy Bartlett]

Hi,

Fixed-Point Designer provides several tools for solving systems of linear equations, including QR decomposition and solving AX=B, in both MATLAB and Simulink.

The tools for use in MATLAB are found here.

The tools for use in Simulink are found here. The tools for Simulink also handle Singular Value Decompositon (SVD).

Most of these tools are optimized for hardware efficient implementations on FPGAs and ASICS. HDL code generation is supported, as is C code generation.

Customers in aerospace and communications have found these tools helped them achieve their design's behavioral requirements while meeting their constraints on timing budgets and hardware resource budgets. Using fixed-point data types was key to the smaller consumption of hardware resources and timing budgets.

Bigger systems of equations can be solved within hardware/timing constrains by using fixed-point data types, but there will still be limitations. Try to keep the size of the equations (matrices) modest and do a sanity check, such as generating HDL, early in the design flow to see if the hardware requirements are a fit for your intended device and hardware budget.

Regards,

Andy

[Life is Wonderful]

Yup, thanks - I'II have a look.