Sparse matrix

A matrix in which most entries are zero. Sparse matrices can be stored efficiently by recording their nonzero values and positions rather than every entry.

Matrix: A rectangular array of elements arranged in rows and columns. A sparse matrix is a matrix whose entries are mostly zero.
Sparse matrix–vector multiplication: The operation of multiplying a sparse matrix by a vector without processing its zero entries. It is a core operation in iterative numerical methods and graph algorithms.
Finite element method: A numerical method that approximates solutions to differential equations by dividing a domain into smaller elements. Local interactions produce sparse system matrices in many finite element models.
Dense matrix: A matrix in which most entries are nonzero. Dense storage is often simpler and faster when zeros are uncommon.
Sparsity: The proportion of elements in a structure that are zero or absent. It quantifies how many entries a sparse matrix omits.
Sparse matrix–matrix multiplication: Matrix multiplication algorithms that exploit sparsity to avoid unnecessary operations on zero entries. Products can become less sparse or more sparse, affecting storage and runtime.
Graph Laplacian: A matrix encoding the degrees and adjacency relationships of a graph. For sparse graphs, its nonzero pattern is sparse and reflects local connections.
Banded matrix: A matrix whose nonzero entries lie within a fixed number of diagonals around the main diagonal. It is a structured sparse matrix with a narrow, predictable nonzero pattern.
Compressed sparse row: A storage format that records nonzero values, their column indices, and row boundaries. It stores row-oriented sparse matrices compactly and supports efficient row operations.
Fill-in: The creation of new nonzero entries during matrix factorization or elimination. It can erase the storage and computational advantages of sparse matrices.

Linked from 18 pages