MATLAB Answers

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

16 views (last 30 days)
Marko
Marko on 21 Feb 2021
Commented: Marko on 22 Feb 2021
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
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

Sign in to comment.

Products


Release

R2020b

Community Treasure Hunt

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

Start Hunting!