Computational efficiency: sparse vs. full

Question

I found out the fact that if a matrix is (almost) full, then storing it in sparse leads to (much) more time to compute.

Though it is trivial to store a full matrix in sparse form, I just want to know the reason behind this fact.

My speculation is that the index reading in sparse would be the major contributor to the computing time. Any other elegant thoughts?

Answer 1

There are a few reasons for an almost full sparse matrix being more computationally expensive than just using a full matrix. The most obvious, as you pointed out, is that sparse elements must be indexed (for a general sparse matrix, I believe Matlab uses a Compressed Row Storage scheme).

Another, less apparent slowdown, is due to vectorization and pipelining data into the processor. In the case of a fully stored matrix, the data is in a neat, linear format, so operations can be easily vectorized. For storage schemes like CRS, this is not the case, especially for Matrix*Vector operations, which tend to be the most used (e.g.- when using iterative solvers to solve systems of equations). For a CRS scheme, moving across the matrix row can be fed to the processor in a nice, linear manner, however, the elements pulled from the vector the matrix is multiplied by, will jump around.

Answer 2

Consider the following dense matrix:

1 2 3
4 5 6
7 8 9

If I store it in a contiguous block:

1 2 3 4 5 6 7 8 9

I can directly access the elements of the matrix given the row and column number with some basic arithmetic.

Now consider this sparse matrix:

1 0 0
0 0 2
0 3 0

In order to efficiently store this matrix, I discard non-zero elements so it now becomes

1 2 3

But this is obviously not enough information to do operations like a matrix vector multiplication! So we need to add additional information to extract the elements from the matrix.

But you can see that irrespective of the storage method used, we need to

1. Do extra work to access the elements
2. Store more information to keep the structure of the matrix

So as you can see, the benefits of storage arises only if there are enough zeros in the matrix to compensate for the extra information we store to preserve the structure of the matrix. For example, in the Yale format, we only save on memory when the number of non-zero (NNZ) values is less than (m(n − 1) − 1) / 2 where m = number of rows and n = number of columns.