Sparse Matrix · aiwiki.page

A sparse matrix is a matrix whose entries are predominantly zero, or whose zero structure makes specialized representation computationally advantageous. Unlike dense storage, which records every entry, sparse storage typically records nonzero values and information identifying their positions. Sparse matrices are central to numerical linear algebra because this representation can substantially reduce memory requirements and avoid arithmetic involving zeros. Sparsity describes the matrix’s entries; sparse storage describes how those entries are represented on a computer. (mathworks.com)

Definition and structure

For an $m\times n$ matrix $A$ , let $k=\operatorname{nnz}(A)$ denote its number of mathematically nonzero entries. Its density is $k/(mn)$ , and its sparsity, when expressed as the proportion of zero entries, is $1-k/(mn)$ . No universal density threshold separates sparse from dense matrices: the practical distinction depends on storage overhead, matrix dimensions, and the operations performed. Sparse representations must store indices as well as values, so they are not automatically economical for every matrix containing zeros. (mathworks.com)

The sparsity pattern is the set of positions occupied by nonzero entries. Its arrangement matters as well as its size: diagonal, banded, block-structured, and irregular matrices can require different storage strategies. An $n\times n$ identity matrix, for example, has only $n$ nonzero entries, giving density $1/n$ . This illustrates how a matrix family can become increasingly sparse as its dimensions grow. (netlib.org)

Mathematical nonzeros must sometimes be distinguished from stored entries. Software may retain explicit zeros or repeated coordinates, so a stored-entry count need not equal the mathematical nonzero count. In graph applications, an explicitly stored zero can distinguish a zero-weight connection from an absent connection. (docs.scipy.org)

Storage formats

Sparse data structures trade compactness against ease of construction, modification, and access. Several formats are widely used:

Coordinate format (COO) stores row indices, column indices, and corresponding values. It is convenient for assembling matrices from individual contributions. Duplicate coordinates may be retained temporarily and later combined.
**Compressed sparse row (CSR), also called compressed row storage (CRS), groups entries by row. It uses an array of values, an array of column indices, and a row-pointer array marking row boundaries.
Compressed sparse column (CSC) uses the analogous arrangement by column, with row indices and column pointers.
Block sparse formats record small dense blocks rather than individual scalar entries. Diagonal formats store selected diagonals and their offsets. These exploit regularity that general-purpose coordinate or compressed formats do not explicitly encode. (docs.scipy.org)

For an illustrative zero-based CSR encoding,

A=\begin{pmatrix} 4&0&7\\ 0&0&0\\ 2&5&0 \end{pmatrix}

can be represented by values = [4,7,2,5], column_indices = [0,2,0,1], and row_pointers = [0,2,2,4]. The repeated pointer value indicates the empty second row. With $k$ stored entries, CSR uses $k$ values, $k$ column indices, and $m+1$ row pointers: its space complexity is $O(k+m)$ , rather than $O(mn)$ for dense storage, using big-O notation. (netlib.org)

Arithmetic and computational behavior

A fundamental operation is sparse matrix–vector multiplication. For a dense vector $x$ ,

y_i=\sum_{j:A_{ij}\ne0}A_{ij}x_j.

A row-oriented implementation visits stored entries instead of every matrix position. Its time complexity is typically $O(k+m)$ , including initialization of the output. This operation is a basic building block of iterative linear-system solvers. (netlib.org)

Sparsity is not preserved by every operation. Addition can combine two sparsity patterns, multiplication can create additional nonzeros, and a sparse matrix’s inverse may be dense. Consequently, the cost of sparse multiplication or solving equations cannot generally be inferred from input nonzero counts alone. Output structure and intermediate results also matter. (mathworks.com)

Index lookup, indirect memory access, and irregular workloads introduce overhead. A specialized algorithm may perform fewer arithmetic operations without achieving a proportionate reduction in runtime. Storage format and hardware characteristics influence performance, particularly in parallel computing. (netlib.org)

Solving sparse linear systems

Sparse matrices frequently appear in a system of linear equations $Ax=b$ . Direct methods use matrix factorization, such as LU decomposition or Cholesky decomposition. During elimination, positions initially containing zero can become nonzero in the factors. This phenomenon, called fill-in, can substantially increase memory use and computation. Reordering rows and columns can reduce fill-in, although numerical requirements also constrain the factorization. (mathworks.com)

Iterative methods instead improve an approximate solution through repeated operations, often dominated by matrix–vector products. The conjugate gradient method applies to symmetric positive-definite systems, while other methods accommodate different matrix classes. Preconditioning modifies the problem or iteration to improve convergence; incomplete factorizations provide one way to construct a preconditioner while limiting fill. The number of iterations depends on more than sparsity, including spectral properties and the effectiveness of the preconditioner. (netlib.org)

Applications

Discretizing partial differential equations commonly produces sparse matrices because local equations couple only nearby unknowns. For example, finite-difference methods generate structured interactions among neighboring grid points. Sparse systems also arise in structural analysis, circuit analysis, fluid dynamics, and large-scale mathematical optimization. (mathworks.com)

In machine learning and natural language processing, document–term matrices often have many zeros because each document contains only a small portion of the vocabulary. The bag-of-words model and related weighted representations therefore support sparse storage. Text-processing tools can construct these matrices directly, without first allocating a dense document-by-vocabulary array. (scikit-learn.org)