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

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.

[dpb]

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]

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...

Answer 1

[Christine Tobler]

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.

[Christine Tobler]

Here's an example where several reordering algorithms for sparse matrices are compared:

https://www.mathworks.com/help/matlab/math/sparse-matrix-reordering.html

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.

[Marko]

Hallo Christine,

thank you for your detailed explanation and the very informative link.