Sparse matrix

[1] There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse but a common criterion is that the number of non-zero elements is roughly equal to the number of rows or columns.

The concept of sparsity is useful in combinatorics and application areas such as network theory and numerical analysis, which typically have a low density of significant data or connections.

Large sparse matrices often appear in scientific or engineering applications when solving partial differential equations.

Specialized computers have been made for sparse matrices,[2] as they are common in the machine learning field.

[3] Operations using standard dense-matrix structures and algorithms are slow and inefficient when applied to large sparse matrices as processing and memory are wasted on the zeros.

Sparse data is by nature more easily compressed and thus requires significantly less storage.

Some very large sparse matrices are infeasible to manipulate using standard dense-matrix algorithms.

An important special type of sparse matrices is band matrix, defined as follows.

The lower bandwidth of a matrix A is the smallest number p such that the entry ai,j vanishes whenever i > j + p. Similarly, the upper bandwidth is the smallest number p such that ai,j = 0 whenever i < j − p (Golub & Van Loan 1996, §1.2.1).

To reduce the memory requirements and the number of arithmetic operations used during an algorithm, it is useful to minimize the fill-in by switching rows and columns in the matrix.

While the theoretical fill-in is still the same, in practical terms the "false non-zeros" can be different for different methods.

Both iterative and direct methods exist for sparse matrix solving.

Each entry in the array represents an element ai,j of the matrix and is accessed by the two indices i and j. Conventionally, i is the row index, numbered from top to bottom, and j is the column index, numbered from left to right.

In the case of a sparse matrix, substantial memory requirement reductions can be realized by storing only the non-zero entries.

Depending on the number and distribution of the non-zero entries, different data structures can be used and yield huge savings in memory when compared to the basic approach.

The trade-off is that accessing the individual elements becomes more complex and additional structures are needed to be able to recover the original matrix unambiguously.

Formats can be divided into two groups: DOK consists of a dictionary that maps (row, column)-pairs to the value of the elements.

[4] LIL stores one list per row, with each entry containing the column index and the value.

Typically, these entries are kept sorted by column index for faster lookup.

[5] COO stores a list of (row, column, value) tuples.

This format allows fast row access and matrix-vector multiplications (Mx).

[7] The CSR format stores a sparse m × n matrix M in row form using three (one-dimensional) arrays (V, COL_INDEX, ROW_INDEX).

Let NNZ denote the number of nonzero entries in M. (Note that zero-based indices shall be used here.)

In this case the CSR representation contains 13 entries, compared to 16 in the original matrix.

Note that in this format, the first value of ROW_INDEX is always zero and the last is always NNZ, so they are in some sense redundant (although in programming languages where the array length needs to be explicitly stored, NNZ would not be redundant).

Moreover, the memory cost of this redundant storage is likely insignificant for a sufficiently large matrix.

The (old and new) Yale sparse matrix formats are instances of the CSR scheme.

The name is based on the fact that column index information is compressed relative to the COO format.

This format is efficient for arithmetic operations, column slicing, and matrix-vector products.

The following are open-source: The term sparse matrix was possibly coined by Harry Markowitz who initiated some pioneering work but then left the field.