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

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) or 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. Here is a simple version of the code.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function solve()
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
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

Answer 1

[tmarske]

You cannot obtain an 'exact' solution to this or any other calculation without using a high-precision numerical format like the symbolic toolbox. To see why, try typing the following:

>> 2350911785583947777 - 2350911785583947700

ans =

     0  
     

or:

>> fprintf(1, '%d\n', 2350911785583947700)
2350911785583947776

Matlab 'believes' that 2350911785583947700 == 2350911785583947776 because double-precision floating point (Matlab's default numerical datatype) is not precise enough to distinguish between these two numbers. This is not unique to Matlab - you will get exactly the same behaviour in any other language whose floating point arithmetic conforms to the IEEE 754 standard.

If you really need the exact solution then your only option is to use a high-precision format (like the symbolic toolbox). This will always be much slower, as you have found. However you should ask yourself whether you really need this level of accuracy = in your example above double-precision calculations were accurate to 15 significant figures. If this is enough then there is no need to use sym().

[Mohammed Al-Darwbi]

Thanks. I was just wondering if there is a faster way than using the symbolic.

I have used vpa() and it improved the performance and maintained the required acuracy.

Instead of sym(A), I used vpa(A).