Solve large linear equations with backslash operator. Why is sparse matrix solved slower than the full matrix?
18 次查看(过去 30 天)
显示 更早的评论
Hello Community and Staff,
maybe somebody could explain to me why sparse matrix operation for a not so well condidioned matrix is maybe 2-5 times slower than the backslash operator.
And maybe somebody have an idea how to improve the speed.
% This script measure the time for solving large number of equations
% N is the number of N-1 chebyshev collocations points
% s is the size of the matrix and vector
% indices with an s denotes that tha variable is sparse
% rf is the ratio of numbers that are zero and the size s for vector f
% rA is the ratio of numbers that are zero and the size s for matrix A
% rA is approx.: 0.0255 for N=32
% 0.0175 for N=48
% 0.0133 for N=64
N = 48;
s = 2*(N+1)^2+(N-1)^2;
rf = (2*((N+1)^2-(N-1)^2)/s);
rA = 0.0175; %this variabel has to be set
f = rand(s,1);
f(f<(1-rf))=0;
fs = sparse(f);
A = rand(s,s);
A(A<1-rA) = 0;
As = sparse(A);
whos A* f*
disp([' solving q1 = A\f take ',num2str(timeit(@() A\f)),' seconds'])
disp([' solving q2 = A\fs take ',num2str(timeit(@() A\fs)),' seconds'])
disp([' solving q3 = As\f take ',num2str(timeit(@() As\f)),' seconds'])
disp([' solving q4 = As\fs take ',num2str(timeit(@() As\fs)),' seconds'])
I get these results:
Name Size Bytes Class Attributes
A 7011x7011 393232968 double
As 7011x7011 13821760 double sparse
f 7011x1 56088 double
fs 7011x1 6176 double sparse
solving q1 = A\f take 4.7096 seconds
solving q2 = A\fs take 4.7589 seconds
solving q3 = As\f take 12.0466 seconds
solving q4 = As\fs take 11.1677 seconds
something is also curious:
how much memory each "disp..." line need for solving:
q1 need approx. 0.37GB
q2 need approx. 0.35GB
q3 need approx. 2.79GB
q4 need approx. 1.43GB
------------------------------------------------------
Why does it take so much memory and time for solving A sparse matrix instead of solving a non-sparse matrix.
Maybe somebody could reproduce these results.
Any help would be appreciated.
2 个评论
dpb
2021-2-21
Sparse matrices are great for saving memory to be able to hold the data but; as you see "not so much" for working with them; it takes converting to full representation for most operations that can't be done on an element-wise basis. As your example shows, it's not so expensive for a vector as for the array.
回答(1 个)
Christine Tobler
2021-2-22
Sparse linear system solvers are usually fast for sparse matrices with specific structure of where the nonzeros are placed. For example, when most nonzeros are on a band around the diagonal, or if the sparse matrix has "arrow structure" (nonzeros on a band around the diagonal, and in the last rows and columns of the matrix). There are some reordering tools applied to the matrix in backslash, but it's usually impossible to do this kind of reordering on a sparse matrix with random distribution of the nonzeros.
2 个评论
Christine Tobler
2021-2-22
Here's an example where several reordering algorithms for sparse matrices are compared:
As mentioned, backslash does some of this internally - but it's only successful if the sparse matrix comes from an application that leads to this kind of structure in the sparse matrix to begin with.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Operating on Diagonal Matrices 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!