sparsematrix

A sparse matrix is a matrix in which the majority of elements are zero. Such matrices occur frequently in representations of graphs, discretized physical systems, and high-dimensional data with many missing or irrelevant values. To save memory and speed up computation, sparse matrices are stored using formats that record only nonzero entries and their positions.

Common storage schemes include the coordinate list (COO), which stores triplets (row, column, value) for each nonzero element; compressed sparse row (CSR), which arranges nonzeros by row with an array of row pointers, a column index array, and a value array; and compressed sparse column (CSC), the column-oriented counterpart. Block formats such as BSR group nonzeros into small dense blocks. These formats enable efficient matrix-vector products and enable other operations to exploit sparsity. The choice of format affects performance for different operations and access patterns.

Operations on sparse matrices aim to scale with the number of nonzero elements (nnz), rather than the full matrix size. For example, sparse matrix–vector multiplication typically runs in O(nnz) time. Sparse addition or multiplication can introduce fill-in, where zero entries become nonzero, increasing memory usage and computation. Reordering techniques and specialized algorithms mitigate fill-in during factorization.

Applications include solving large sparse linear systems and eigenvalue problems, finite element analysis, network and graph algorithms, and machine learning with sparse feature representations. Sparse matrix theory encompasses a range of formats and operations tailored to balance memory efficiency with computational performance, depending on the matrix structure and the intended computations.