# 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*.

*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), or by a *point access method*.

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 E. Black.

Entry modified 18 December 2009.

HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:

Paul E. Black, "sparse matrix", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 18 December 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/sparsematrix.html