Data Structure by Vinay Kumar Saini: Sparse matrix

A Sparse matrix is a matrix populated primarily with zeros as elements of the table. When storing and manipulating sparse matrices on a computer, it is better to be smart and use specialized algorithms and data structures that take advantage of the sparse structure of the matrix to improve the performance of you program. Sparse data is can easily be compressed and almost always results in significantly less computer data storage usage.

Storing a sparse matrix

The basic data structure for a matrix is a two-dimensional array. Each entry in the array represents an element A(i,j) of the matrix and can be accessed by the two indices i and j. 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 the basic 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.

Dictionary of keys (DOK) : DOK represents non-zero values as a dictionary (e.g., a hash table or binary search tree) mapping (row, column)-pairs to values. This format is good for incrementally constructing a sparse array, but poor for iterating over non-zero values in sorted order. One typically creates the matrix with this format, then converts to another format for processing

List of lists (LIL): LIL stores one list per row, where each entry stores a column index and value. Typically, these entries are kept sorted by column index for faster lookup. This is another format which is good for incremental matrix construction.

Coordinate list (COO): COO stores a list of (row, column, value) tuples. Ideally, the entries are sorted (by row index, then column index) to improve random access times. This is another format which is good for incremental matrix construction.

-----------------

Vinay Kumar Saini

Assistant Professor (I.T Department)

Maharaja Agrasen Institute of Technology (MAIT)

Sector-22, Rohini, Delhi-110086, India
Email-Id : vinay.kr.saini@gmail.com
Connect with me