What is the fastest way to find the exact solution of a linear system
14 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Mohammed Al-Darwbi
el 10 de Mzo. de 2020
Comentada: Mohammed Al-Darwbi
el 11 de Mzo. de 2020
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:
- linslove function cannot find the exact solution if ( A and B) are not symbolic.
- 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
0 comentarios
Respuestas (1)
tmarske
el 11 de Mzo. de 2020
Editada: tmarske
el 11 de Mzo. de 2020
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().
Ver también
Categorías
Más información sobre Linear Algebra en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!