Sparse matrix: Difference between revisions

Revision as of 22:48, 18 May 2023

Revision as of 06:52, 19 May 2023

Line 15:

[[Image:Finite element sparse matrix.png|right|thumb|A sparse matrix obtained when solving a [[finite element method|finite element problem]] in two dimensions. The non-zero elements are shown in black.]]

In [[numerical analysis]] and [[scientific computing]], a '''sparse matrix''' or '''sparse array''' is a [[matrix (mathematics)|matrix]] in which most of the elements are zero.<ref name="Yan Wu Liu Gao 2017 p. ">{{cite conference | last1=Yan | first1=Di | last2=Wu | first2=Tao | last3=Liu | first3=Ying | last4=Gao | first4=Yang | title=2017 IEEE 17th International Conference on Communication Technology (ICCT) | chapter=An efficient sparse-dense matrix multiplication on a multicore system | publisher=IEEE | year=2017 | pages=1880–1883 | isbn=978-1-5090-3944-9 | doi=10.1109/icct.2017.8359956 | quote=The computation kernel of DNN is large sparse-dense matrix multiplication. In the field of numerical analysis, a sparse matrix is a matrix populated primarily with zeros as elements of the table. By contrast, if the number of non-zero elements in a matrix is relatively large, then it is commonly considered a dense matrix. The fraction of zero elements (non-zero elements) in a matrix is called the sparsity (density). Operations using standard dense-matrix structures and algorithms are relatively slow and consume large amounts of memory when applied to large sparse matrices. }}</ref> 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'''.<ref name="Yan Wu Liu Gao 2017 p. "/> 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 equation]]s.