Creating a sparse matrix from a dense matrix

Question

I would like to know whether there is a general method (and, if so, which one) to create a sparse matrix from a dense matrix. I know a sparse matrix simply does not include the zero entries, but since their allocation in the matrix can be very diverse, I am wondering whether that derivation from dense to sparse can be somehow automatized......

Answer 1

Somewhat longer comment:

Some problems lead naturally to sparse matrices, e.g., PDE discretizations using finite difference/volume/element methods, some Markov chains (when, e.g., you know a priori that a given state is related with a nonzero probability to a small number of other states) like in PageRank, etc.

The first question to answer is if it is really worth trying to convert a dense matrix to a sparse one and why? Is it to make the storage more efficient (in terms of the number of stored bytes), to use algorithms which benefit from the sparse structure, or...?

Note that just having a lot of zeros in your matrix does not mean it makes sense to convert it to a sparse one. While the dense matrix is usually stored in the form of a single array of numbers (with some sort of two-index access to it), sparse matrices, usually storing only the nonzero entries, need additional information about the distribution of the entries in the matrix (their "coordinates"). This additional information does represent an unnegligible storage overhead (in particular when the matrix is not so sparse). In addition, access to matrix entries involves indirect addressing and is not generally very "cache friendly" as in the case of dense matrices. Traditionally, a matrix is considered sparse if there the number of entries in rows/columns remain bounded by a constant independently of the size of the matrix (this is the when solving discretized PDEs). If, e.g., just half of the matrix entries are zeros, certainly it does not make sense to consider it as sparse.

Algorithms for sparse matrices are normally more complicated than their dense counterparts. One must pay attention, e.g., when factorizing the matrix, to the ordering and fill-in issues, which might destroy the sparsity of the factors and in fact make the use of sparse structures useless.

To the question: Yes, it is of course possible to convert a dense matrix to a sparse one (consider, e.g., the function sparse in Matlab). For example, the CSR format (essentially the Yale one) can be created by traversing the rows of the dense matrix and filling sequentially the related arrays of the CSR structure. With the zero-based indexing, this can go as follows:

$$ \begin{split} &\text{Input: $A\in\mathrm{R}^{m\times n}$}\\ &\text{Output: $RP=[0]$ (row pointers), $CI=[\;]$ (column indices), $VAL=[\;]$ (values)}\\ &PTR\gets 0\\ &\text{for $i=0,\ldots,m-1$}\\ &~~~~~~\text{for $j=0,\ldots,n-1$}\\ &~~~~~~~~~~~~\text{if $A(i,j)\neq0$ then}\\ &~~~~~~~~~~~~~~~~~~CI.\text{append}(j)\\ &~~~~~~~~~~~~~~~~~~VAL.\text{append}(A(i,j)\\ &~~~~~~~~~~~~~~~~~~PTR\gets PTR+1\\ &~~~~~~RP.\text{append}(PTR)\\ \end{split} $$

Nevertheless, it makes more sense to create a sparse matrix directly instead of storing it as a dense one in the first place.