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.