# sparse matrix

(data structure)

**Definition:**
A *matrix* that has relatively few non-zero (or "interesting") entries. It may be represented in much less than n × m space.

**Aggregate child** (... is a part of or used in me.)

*list*, *orthogonal lists*, *array*, or *point access method*.

**See also**
*ragged matrix*, *huge sparse array*, *adjacency-matrix representation*, *k²-tree*.

*Note:
A n × m matrix with k non-zero entries is sparse if k << n × m. It may be faster to represent the matrix compactly as a **list* of the non-zero entries in coordinate format (the value and its row/column position), as a list or *array* of lists of entries (one list for each row), two *orthogonal lists* (one list for each column and one list for each row), by a *point access method*, or a *k²-tree*.

Author: PEB

## Implementation

Input/output for sparse matrices stored in Harwell-Boeing Format (C)
## More information

Yousef Saad's Iterative methods for sparse linear systems (PDF), chapters 1-3 of a textbook covering linear algebra and types of matrices. Sparse matrix implementations, including the coordinate format, begin on page 85 (PDF page 97). Other formats and information on a newer edition.

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with Paul Black.

Entry modified 8 June 2023.

HTML page formatted Wed Aug 9 16:21:12 2023.

Cite this as:

Paul E. Black, "sparse matrix", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 8 June 2023. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/sparsematrix.html