Sparse matrix: Difference between revisions

Revision as of 03:56, 29 August 2024

Revision as of 01:17, 11 September 2024

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–18831880–3 | 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.

Line 102:

* The arrays {{math|V}} and {{math|COL_INDEX}} are of length {{math|NNZ}}, and contain the non-zero values and the column indices of those values respectively

* {{math|COL_INDEX}} contains the column in which the corresponding entry {{math|V}} is located.

* The array {{math|ROW_INDEX}} is of length {{math|''m'' + 1}} and encodes the index in {{math|V}} and {{math|COL_INDEX}} where the given row starts. This is equivalent to {{math|ROW_INDEX[j]}} encoding the total number of nonzeros above row {{math|j}}. The last element is {{math|NNZ}} , i.e., the fictitious index in {{Math|V}} immediately after the last valid index {{math|NNZ − 1}}.<ref name=Saad03>{{cite book harvnb|last1=Saad |first1=Yousef |title=Iterative methods for sparse linear systems |date=2003 |publisher=SIAM}}</ref>

For example, the matrix

Line 197:

* {{Cite web |title=Sparse Matrix Multiplication Package|first1= Randolph E.|last1= Bank|first2= Craig C.|last2= Douglas |url=http://www.mgnet.org/~douglas/Preprints/pub0034.pdf}}

* {{Cite book |last=Pissanetzky|first= Sergio|year= 1984|title=Sparse Matrix Technology|url=https://archive.org/details/sparsematrixtech0000piss|url-access=registration|publisher= Academic Press |isbn=978-0-12-557580-5 |oclc=680489638 }}

*{{cite journal|doi=10.1007/BF02521587|title=Reducing the profile of sparse symmetric matrices|year=1976|last1=Snay|first1=Richard A.|journal=[[Bulletin Géodésique]]|volume=50|issue=4|pages=341–352|bibcode=1976BGeod..50..341S|hdl=2027/uc1.31210024848523|s2cid=123079384|hdl-access=free}} Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.<ref> Referencing {{cite book harvnb|last1=Saad |first1=Yousef |title=Iterative methods for sparse linear systems |date=2003 |publisher=SIAM}}</ref>.

* {{cite book |first=Jennifer |last=Scott |first2=Miroslav |last2=Tuma |title=Algorithms for Sparse Linear Systems |publisher=Birkhauser |date=2023 |doi=10.1007/978-3-031-25820-6 }} (Open Access)

{{refend}}

==Further reading==

{{refbegin}}

* {{cite journal | title = A comparison of several bandwidth and profile reduction algorithms | journal = ACM Transactions on Mathematical Software | year = 1976 | volume = 2 | issue = 4 | pages = 322–330 | url = http://portal.acm.org/citation.cfm?id=355707 | doi = 10.1145/355705.355707 | last1 = Gibbs | first1 = Norman E. | last2 = Poole | first2 = William G. | last3 = Stockmeyer | first3 = Paul K. | s2cid = 14494429 }}

* {{cite journal | title = Sparse matrices in MATLAB: Design and Implementation | journal = SIAM Journal on Matrix Analysis and Applications | year = 1992 | volume = 13 | issue = 1 | pages = 333–356 | url = http://citeseer.ist.psu.edu/gilbert91sparse.html | doi = 10.1137/0613024 | last1 = Gilbert | first1 = John R. | last2 = Moler | first2 = Cleve | last3 = Schreiber | first3 = Robert | citeseerx = 10.1.1.470.1054 }}

Line 208 ⟶ 209:

* [http://www.small-project.eu SMALL project] A EU-funded project on sparse models, algorithms and dictionary learning for large-scale data.

* {{cite book |first=Wolfgang |last=Hackbusch |title=Iterative Solution of Large Sparse Systems of Equations |publisher=Springer |date=2016 |doi=10.1007/978-3-319-28483-5 |edition=2nd}}

* {{cite book |first=Yousef |last=Saad |title=Iterative Methods for Sparse Linear Systems |publisher=SIAM |date=2003 |isbn=978-0-89871-534-7 |doi=10.1137/1.9780898718003 |oclc=693784152 }}

* {{cite book |first=Timothy A. |last=Davis |title=Direct Methods for Sparse Linear Systems |publisher=SIAM |date=2006 |isbn=978-0-89871-613-9 |doi=10.1137/1.9780898718881 |oclc=694087302 }}

{{refend}}

{{Data structures}}