Why multiply a sparse matrix(0.5) with a dense vector is slower than the normal multiply?

matlab

Solution

No. That is simply NOT a sparse matrix. You misunderstand when sparse matrices are useful. Those of us who do use them heavily would say that a matrix is not really sparse unless it has a density of less than 1%. Even that density is not very sparse!

A sparse matrix has extra bookkeeping when you use it, because now MATLAB essentially needs to worry about where the non-zeros are. So if you make a matrix that is essentially a dense matrix, and pretend that it is sparse, you are defeating the value of the tool.

Lets make a comparison or two. First, a completely dense matrix. I'll use Steve Eddins timeit tool from the file exchange. This does a very good job of estimating time taken, and does not require an explicit loop.

A = rand(1000);
As = sparse(A);
b = rand(1000,1);

whos A As
  Name         Size                 Bytes  Class     Attributes
  A         1000x1000             8000000  double              
  As        1000x1000            16008008  double    sparse

See that the fully dense matrix takes up considerably less space than the sparse form.

timeit(@() A*b)
ans =
   0.00039474

timeit(@() As*b)
ans =
    0.0023663

The overhead of the sparse matrix in a simple multiply is way too large.

As = sprand(1000,1000,.5);
A = full(As);
b = rand(1000,1);

whos A As
Name         Size                Bytes  Class     Attributes
  A         1000x1000            8000000  double              
  As        1000x1000            6303448  double    sparse

Here the two matrices barely show a size reduction for the sparse version. So calling it sparse is a waste of time in terms of space consumed. As well, as you found, the time consumed for multiplies is still not a gain.

timeit(@() A*b)
ans =
   0.00027594

timeit(@() As*b)
ans =
    0.0005011

However, what happens when the matrix is closer to what I suggested in terms of sparsity?

As = sprand(1000,1000,.01);
A = full(As);
b = rand(1000,1);

whos A As
  Name         Size                Bytes  Class     Attributes

  A         1000x1000            8000000  double              
  As        1000x1000             167176  double    sparse   

timeit(@() A*b)
ans =
   0.00023629

timeit(@() As*b)
ans =
   5.3167e-05

Ok, so this now is saving some serious space. And some serious time too.

But really, the time for a multiply is NOT why we use sparse matrices. It is the time required to solve a linear system of equations that makes us use sparse matrices. This can be a MASSIVE savings, where the problem will be essentially unsolvable using full matrices. A common problem for me might involve a 40000x40000 matrix, with perhaps a density of 0.02%. I would spend days waiting for the full version to finish, but only seconds for a sparse solve in that case.

For example, consider gridfit, a function of mine that is on the file exchange. It creates surfaces from scattered data. In this example, the tool will need to solve a linear system of equations with 40000 unknowns.

timeit(@() gridfit(rand(100,1),rand(100,1),rand(100,1),linspace(0,1,200),linspace(0,1,200)))
ans =
      0.83624

So for everything, including setting up that system of equations, it took less than 1 second.

The (in this case, non-square) linear system that it solves is VERY sparse.

whos A
  Name          Size                 Bytes  Class     Attributes
  A         80100x40000            4126408  double    sparse

How sparse is it?

nnz(A)
ans =
      237900

nnz(A)/40000
ans =
       5.9475

So on average, only 5.9475 non-zeros per row, with 40000 columns. And we don't have the time it would take for me to do a full linear solve with that system. At least I don't have any desire to try it.

Problem

I generated a matrix with sparsity 0.5, and I want to know its speed multiplying a dense vector compared to the multiplying in the normal way. ``` function sparseTest() A = sprand(1000, 1000, 0.5); test(A); test(full(A)); end function test(A) tic; b = rand(size(A, 2), 1); for i = 1:10000 c = A * b; end toc; end ``` The result is ``` Elapsed time is 10.968797 seconds. Elapsed time is 10.194440 seconds. ``` what confuses me is that since there is only half non-zero numbers, I think the sparse multiplying should somehow be faster.

Original source