NIST

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

Entry modified 18 December 2009.
HTML page formatted Tue May 6 13:48:56 2014.

Cite this as:
Paul E. Black, "sparse matrix", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 18 December 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/sparsematrix.html