What is the fastest way to find the exact solution of a linear system, matlab

user_1951705 0
Viewed 135

I am trying to solve a linear system (A*x=B) where B is a 64-bit length or more. I have used linsolve function in Matlab to solve the system of equations. I have used (inv(A)*B), A\B, and ttimes(A,B) as well, and they suffer from the same issues.

I am facing two problems:

  1. linslove function cannot find the exact solution if ( A and B) are not symbolic.
  2. If A and B are symbolic, linsolve manage to find the exact solution but it takes too much time.

Is there any way to find the exact solution but fast.

time=[]
i=50
a=magic(i);    
% B is a rendom numbers where each number is 64 bit length
B=double(bi2de(randi([0 1],i,64)));

%%****************************************
 % to make sure th matrix is not  **ill-conditioned***
        C = 1;              % desired condition number
        [u s v] = svd(a);
        s = diag(s);        % s is vector
        % ===== linear stretch of existing s
        s = s(1)*( 1-((C-1)/C)*(s(1)-s)/(s(1)-s(end)));
        % =====
        s = diag(s);           % back to matrix
        A = u*s*v';
%%****************************************
tic
x1=linsolve(A,B);
time(1,1)=toc;
%-------------------------------------
% convert A and B into symbolic 
Aa=sym(A);        Bb=sym(B);
tic
x2=linsolve(Aa,Bb);
time(1,2)=toc;
%-------------------------------------
% Show the accuracy of the first B(1), exact vs computed 
Exact=sym(double(B(1)))     
Computed=[ A(1,:)*x1  Aa(1,:)*x2]
time

x1 and x2 are the two solution. x2 is the solution of the sumbolic A and B.

Only X2 gives us the exact solution 

Exact solution =   2350911785583947776
Computed using x1= 2350911785583965184
Computed using x2= 2350911785583947776

Time required in seconds:

x1 time =    0.0007
x2 time =    6.7242
linear-algebra matlab
2 Answers

This is not an answer to your question, it is a demonstration of why your "exact" solution is not exact: the intput B is approximated. Try this in MATLAB:

a = randi([0 1],1,64);
a(1) = 0;
a1 = bi2de(a);
a(1) = 1;
a2 = bi2de(a);
a1-a2

You'll notice that a1 and a2 are identical, even though I flipped the least significant bit in both numbers. This is because a double-precision float cannot hold 64 bits of precision. It holds only 52. The other 12 bits in the 64-bit representation are to store the sign bit and the exponent (which scales the number).

user_73287820

I have built my own bi2de that converts the binary vector to an actual number.

I have replaced sym by vpa, and the performance enhanced.

sym(A) ----> vpa(A)

user_19517050
Related