Sparse Matrix
A sparse matrix is a matrix in which the vast majority of elements are zero. Many real-world matrices are sparse: the adjacency matrix of a large social ne...
Efficient Storage and Operations on Mostly-Zero Matrices
A sparse matrix is a matrix in which the vast majority of elements are zero. Many real-world matrices are sparse: the adjacency matrix of a large social network, where most pairs of users are not connected; the coefficient matrix of a system of differential equations; or the term-document matrix in natural language processing, where most words do not appear in most documents.
Storing a sparse matrix naively as a full two-dimensional array wastes enormous amounts of memory. A million-by-million matrix would require 10^12 entries. If only a million of those are non-zero, storing all 10^12 entries wastes memory proportional to the number of zero entries, and operations that iterate over all entries are correspondingly slow.
Several storage formats have been developed for sparse matrices. The simplest is the coordinate list, or COO format: three arrays store the row indices, column indices, and values of the non-zero elements. If there are k non-zero elements, these arrays each have length k, requiring O(k) space. Looking up a specific element, however, requires a search through the row and column arrays, taking O(k) time.
The compressed sparse row format, or CSR, improves lookup and arithmetic efficiency. It uses three arrays: values stores the non-zero elements in row order, column_indices stores the column index of each value, and row_pointers is an array of length m plus one where row_pointers[i] gives the index in values where row i begins. With CSR, iterating over all non-zeros in a given row is O(number of non-zeros in that row), and matrix-vector multiplication runs in O(m plus k) instead of O(m times n).
Sparse matrix representations are critical in scientific computing, machine learning (sparse feature vectors), and graph processing. Libraries like SciPy, MATLAB, and LAPACK provide optimized sparse matrix routines that exploit these formats.
Addition of two sparse matrices in COO format: merge the coordinate lists, sort by (row, col), and sum values for matching coordinates. The result is O(k1 log k1 plus k2 log k2) where k1 and k2 are the non-zero counts of the two matrices.
Worked example: represent a 1000 by 1000 matrix with only 500 non-zero entries. Dense storage requires one million entries. COO storage requires only 1500 numbers (500 row indices, 500 column indices, 500 values), a 666x reduction in memory.
Interview tip: if an interview problem mentions a very large matrix and states that most elements share a common value (often zero), immediately consider a sparse representation. Ask what percentage of elements are non-zero; below about 30 percent, sparse formats are typically beneficial.