Storing A Sparse Matrix
The native data structure for a matrix is a two-dimensional array. Each entry in the array represents an element ai,j of the matrix and can be accessed by the two indices i and j. Traditionally, i indicates the row number (top-to-bottom), while j indicates the column number (left-to-right) of each element in the table. For an m×n matrix, enough memory to store up to (m×n) entries to represent the matrix is needed.
Substantial memory requirement reductions can be realized by storing only the non-zero entries. Depending on the number and distribution of the non-zero entries, different data structures can be used and yield huge savings in memory when compared to a native approach.
Formats can be divided into two groups: (1) those that support efficient modification, and (2) those that support efficient matrix operations. The efficient modification group includes DOK (Dictionary of keys), LIL (List of lists), and COO (Coordinate list) and is typically used to construct the matrix. Once the matrix is constructed, it is typically converted to a format, such as CSR (Compressed Sparse Row) or CSC (Compressed Sparse Column), which is more efficient for matrix operations.
Read more about this topic: Sparse Matrix
Famous quotes containing the words storing, sparse and/or matrix:
“Computers are good at swift, accurate computation and at storing great masses of information. The brain, on the other hand, is not as efficient a number cruncher and its memory is often highly fallible; a basic inexactness is built into its design. The brain’s strong point is its flexibility. It is unsurpassed at making shrewd guesses and at grasping the total meaning of information presented to it.”
—Jeremy Campbell (b. 1931)
“The report reflects incredibly terrible judgments, shockingly sparse concern for human life, instances of officials lacking the courage to exercise the responsibilities of their high office and some very bewildering thought processes.”
—Jane Jarrell Smith, U.S. widow of American astronaut Michael J. Smith. As quoted in Newsweek magazine, p. 13 (June 30, 1986)
“As all historians know, the past is a great darkness, and filled with echoes. Voices may reach us from it; but what they say to us is imbued with the obscurity of the matrix out of which they come; and try as we may, we cannot always decipher them precisely in the clearer light of our day.”
—Margaret Atwood (b. 1939)