Sparse Matrices (Basics)

Sparse Matrices (Basics)

This post is my personal experience with sparse matrices and is not extensive as is my knowledge about them. I would like to go through these as follows steps / directions.

1. What is a sparse matrix ?

A matrix having many zero elements or block elements (a matrix consisting of smaller matrices of size m-by-m, can be zero as well) .

Example of sparse matrix (Wikipedia)     1   2  3  4  5  6  7  

1  [ 11 22  0  0  0  0  0 ]

2  [  0 33 44  0  0  0  0 ]

3  [  0  0 55 66 77  0  0 ]

4  [  0  0  0  0  0 88  0 ]

5  [  0  0  0  0  0  0 99 ]

2. Why do we need a "sparse " matrix ?

As shown in the example above when handling the sparse matrices there is no need to store the zero-elements. Say, using an addition / multiplication on these full matrices does not have an effect with the zero element. Hence, the matrix can be compressed i.e. storing only the non-zero elements. This would save a lot of memory and floating point operation count. The bold numbers show the row and column indices respectively.

3. What is a sparse matrix format ?

The format mentioned is a "way" of storing the non-zero elements. Foe example, we can store the above example as (using 1-indexing, row-major)

Example of sparse matrix format

Values =  [ 11 22  33 44  55 66 77  88 99 ]

Rows =    [ 1   1   2  2  3  3  3   4  5  ]

Cols =    [ 1   2   2  3  3  4  5   6  7  ]

The above format is known as COO (short for Co-ordinate format). There are many such formats available [ http://web.eecs.utk.edu/~dongarra/etemplates/node372.html ]

4. Sparse matrices applied in CFD, where do they come in ?

Sparse matrices come into picture in incompressible solvers (poisson solvers), compressible (implicit solvers), Multi-grid acceleration techniques etc in FDM, FVM, FEM based solvers. The sparsity pattern comes from the stencil and the grid itself. 

5. Some useful ways to work them out

It is always good to start with a very small matrix (i.e. grid) when starting and noting the matrix structure. It is also good practice to test out from a hand-generated mapping (grid) the sparse matrix and then working on it to understand your format of choice for doing matrix operations.

6. Some useful utility codes

It is always good to use the available sparse matrix format converters and libraries that work on sparse matrices to avoid unnecessary bugs in your code. There are many such available converters, (the libraries are presented in different posts);

• A good idea to monitor sparse conversions, construction and assembly is to use debugging tools like valgrind (presented in other post) and extensive (yes! extensive) use of assert.
• MATLAB : Good to test the sparsity pattern, format, etc in matlab.
• C / C++ : MKL , ViennaCL, CSparse, etc links are presented in other posts
• A COO to CSR converter [ http://crd-legacy.lbl.gov/~yunhe/cs267/final/source/utils/convert/ ]
• FORTRAN : [ http://www-users.cs.umn.edu/~saad/software/SPARSKIT/  ]