Sparse matrix

Definition and Properties of Sparse Matrices
– A sparse matrix is a matrix in which most of the elements are zero.
– There is no strict definition for sparsity, but a common criterion is that the number of non-zero elements is roughly equal to the number of rows or columns.
– The sparsity of a matrix is the number of zero-valued elements divided by the total number of elements.
– Sparse matrices have few pairwise interactions and are useful in combinatorics, network theory, and numerical analysis.
– Large sparse matrices often appear in scientific or engineering applications when solving partial differential equations.

Benefits and Usage of Sparse Matrices
– Storing and manipulating sparse matrices requires specialized algorithms and data structures that take advantage of the sparse structure.
– Specialized computers have been made for sparse matrices, especially in the field of machine learning.
– Operations using standard dense-matrix structures and algorithms are slow and inefficient for large sparse matrices.
– Sparse data is more easily compressed, requiring significantly less storage.
– Some very large sparse matrices are infeasible to manipulate using standard dense-matrix algorithms.
– Sparse matrices are used for reducing fill-in, solving sparse matrix equations, and optimizing memory usage.

Special Cases of Sparse Matrices
– Banded matrices have a lower and upper bandwidth, representing the smallest number of non-zero elements in certain positions.
– Band matrices often lend themselves to simpler algorithms than general sparse matrices.
– Rearranging the rows and columns of a matrix can sometimes reduce the bandwidth.
– Algorithms are designed for bandwidth minimization.
– Diagonal matrices store only the entries in the main diagonal as a one-dimensional array.
– Diagonal matrices require fewer entries to store compared to general sparse matrices.
– Symmetric sparse matrices arise as the adjacency matrix of an undirected graph.
– They can be stored efficiently as an adjacency list.
– Block-diagonal matrices consist of sub-matrices along the diagonal blocks.
– They have a specific form that allows for efficient storage and manipulation.

Storage Formats for Sparse Matrices
– Dictionary of Keys (DOK) consists of a dictionary that maps (row, column) pairs to the value of the elements.
– Missing elements in the dictionary are considered zero.
– DOK is good for incrementally constructing a sparse matrix but inefficient for iterating over non-zero values.
– List of Lists (LIL) stores the non-zero elements in a list of lists format.
– It is useful for constructing sparse matrices in random order but not efficient for iterating over non-zero values.
– Compressed Sparse Row (CSR) and Compressed Sparse Column (CSC) formats support efficient access and matrix operations.
– They are used for efficient storage and manipulation of sparse matrices.
– CSR is optimized for row-wise access, while CSC is optimized for column-wise access.
– COO, Yale format, and CSC are other examples of sparse matrix representations.

Sparse Matrix Software Libraries and Related Concepts
– SuiteSparse, PETSc, Trilinos, Eigen3, MUMPS, deal.II, DUNE, SciPy, spam, and Wolfram Language are software libraries for solving sparse linear systems.
– The term ‘sparse matrix’ may have been coined by Harry Markowitz.
– Matrix representation, Pareto principle, Ragged matrix, Single-entry matrix, and Skyline matrix are related concepts.
– Sparse graph code, sparse file, Harwell-Boeing file format, and Matrix Market exchange formats are related to sparse matrices.
– Yan et al. (2017) proposed an efficient sparse-dense matrix multiplication algorithm for multicore systems.

Sparse matrix (Wikipedia)

"sparsity" redirects here. For other uses, see Sparse (disambiguation).

Example of sparse matrix ${\displaystyle \left({\begin{smallmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&99\\\end{smallmatrix}}\right)}$

The above sparse matrix contains only 9 non-zero elements, with 26 zero elements. Its sparsity is 74%, and its density is 26%.

In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse but a common criterion is that the number of non-zero elements is roughly equal to the number of rows or columns. By contrast, if most of the elements are non-zero, the matrix is considered dense. The number of zero-valued elements divided by the total number of elements (e.g., m × n for an m × n matrix) is sometimes referred to as the sparsity of the matrix.

Conceptually, sparsity corresponds to systems with few pairwise interactions. For example, consider a line of balls connected by springs from one to the next: this is a sparse system as only adjacent balls are coupled. By contrast, if the same line of balls were to have springs connecting each ball to all other balls, the system would correspond to a dense matrix. The concept of sparsity is useful in combinatorics and application areas such as network theory and numerical analysis, which typically have a low density of significant data or connections. Large sparse matrices often appear in scientific or engineering applications when solving partial differential equations.

When storing and manipulating sparse matrices on a computer, it is beneficial and often necessary to use specialized algorithms and data structures that take advantage of the sparse structure of the matrix. Specialized computers have been made for sparse matrices, as they are common in the machine learning field. Operations using standard dense-matrix structures and algorithms are slow and inefficient when applied to large sparse matrices as processing and memory are wasted on the zeros. Sparse data is by nature more easily compressed and thus requires significantly less storage. Some very large sparse matrices are infeasible to manipulate using standard dense-matrix algorithms.