Sparse matrix

In numerical mathematics is called sparse or sparse matrix (English sparse matrix) a matrix with as many entries consist of zeros that it pays to take advantage of this. For square matrices with entries in total, these are many matrices with or even entries equal to zero. The counterpart of a sparse matrix is called fully occupied matrix. The term was introduced by James Hardy Wilkinson, who in 1971 wrote him. Analogously, a vector which consists largely of zeros as sparse vector ( engl. sparse vector) respectively. Often, the row or column vectors of a sparse matrix sparse vectors, but there are also sparse matrices, in which some rows or columns are fully occupied.

Use

The discretization of partial differential equations usually leads to sparse matrices, such as on band matrices, also the representation of many typical graphs ( with limited node degree, planarity or the like. ) Through its adjacency matrix. Note that the inverse of a sparse matrix normally is fully occupied, as well as the LU decomposition. Exceptions to this are the banded matrices, in which such a decomposition can also be sparse.

Sparse matrices have the property that they can be stored efficiently by stores only position and value of the non-zero entries. The position of the non-zero entries is also known as cast structure or sparsity pattern. The evaluation of a sparse matrix-vector product can also be done efficiently, the zeros are not included in the calculation of the product by.

This finds particular use in Krylov subspace methods for the approximate solution of linear systems of equations that require only scalar and matrix - vector products to carry. Since the calculation of the fully occupied LU decomposition requires operations, the matrix-vector product of a matrix with entries but only are these procedures if they only converge after a few iterations, extremely efficient. There called the preconditioner can be used to increase efficiency. Here is For sparse matrices, the incomplete LU decomposition is a common technique that computes an erroneous LU decomposition, but scoring similar structure as the original matrix and thus does not need much more memory.

CRS (Compressed Row Storage) and CCS (Compressed Column Storage) are two ways to store a sparse matrix space.