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

20 次查看（过去 30 天）
Mohammed Al-Darwbi
Mohammed Al-Darwbi 2020-3-10
评论： Mohammed Al-Darwbi 2020-3-11
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

请先登录，再回答此问题。

回答（1 个）

tmarske
tmarske 2020-3-11
编辑：tmarske 2020-3-11
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().
  1 个评论
Mohammed Al-Darwbi
Mohammed Al-Darwbi 2020-3-11
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).

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Linear Algebra 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by