Solve large linear equations with backslash operator. Why is sparse matrix solved slower than the full matrix?

19 views (last 30 days)
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 Comments
dpb
dpb on 21 Feb 2021
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.
Marko
Marko on 21 Feb 2021
hm, so the path for a fast simulation (in this case) is if the machine has enough memory use all of it with an dense matrix.
i believe that the ratio of non-zero-elemts and number of elements of the matrix A is still high enough, that a sparse algorithm don't have any advanteges...

Sign in to comment.

Answers (1)

Christine Tobler
Christine Tobler on 22 Feb 2021
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 Comments
Christine Tobler
Christine Tobler on 22 Feb 2021
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.

Sign in to comment.

Categories

Find more on Operating on Diagonal Matrices in Help Center and File Exchange

Products


Release

R2020b

Community Treasure Hunt

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

Start Hunting!