Content deleted Content added
→Compressed sparse row (CSR, CRS or Yale format): ROW_INDEX vector of the first example was wrong. It must have a length of num_rows+1, with the last element being the (total) number of nonzero values in the matrix. |
Fgnievinski (talk | contribs) |
||
Line 21:
When storing and manipulating sparse matrices on a [[computer]], it is beneficial and often necessary to use specialized [[algorithm]]s and [[data structure]]s that take advantage of the sparse structure of the matrix. Specialized computers have been made for sparse matrices,<ref>{{Cite web|url=https://www.businesswire.com/news/home/20190819005148/en/Cerebras-Systems-Unveils-Industry%E2%80%99s-Trillion-Transistor-Chip|title=Cerebras Systems Unveils the Industry's First Trillion Transistor Chip| quote=The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation|date=2019-08-19 |website=www.businesswire.com|language=en|access-date=2019-12-02}}</ref> as they are common in the machine learning field.<ref>{{Cite press release|url=https://www.anl.gov/article/argonne-national-laboratory-deploys-cerebras-cs1-the-worlds-fastest-artificial-intelligence-computer|title=Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer {{!}} Argonne National Laboratory|quote=The WSE is the largest chip ever made at 46,225 square millimeters in area, it is 56.7 times larger than the largest graphics processing unit. It contains 78 times more AI optimized compute cores, 3,000 times more high speed, on-chip memory, 10,000 times more memory bandwidth, and 33,000 times more communication bandwidth.| website=www.anl.gov|language=en|access-date=2019-12-02}}</ref> Operations using standard dense-matrix structures and algorithms are slow and inefficient when applied to large sparse matrices as processing and [[Computer memory|memory]] are wasted on the zeros. Sparse data is by nature more easily [[data compression|compressed]] and thus requires significantly less [[computer data storage|storage]]. Some very large sparse matrices are infeasible to manipulate using standard dense-matrix algorithms.
=={{anchor|storage}}
A matrix is typically stored as a two-dimensional array. Each entry in the array represents an element {{math|''a''<sub>''i'',''j''</sub>}} of the matrix and is accessed by the two [[Array data structure|indices]] {{math|''i''}} and {{math|''j''}}. Conventionally, {{math|''i''}} is the row index, numbered from top to bottom, and {{math|''j''}} is the column index, numbered from left to right. For an {{math|''m'' × ''n''}} matrix, the amount of memory required to store the matrix in this format is proportional to {{math|''m'' × ''n''}} (disregarding the fact that the dimensions of the matrix also need to be stored).
| |||