稀疏矩阵

稀疏矩陣的例子 $\left[\begin{array}{ccccccc}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{array}\right]$

Template:Midsize

计算有限元问题时得到的稀疏矩阵。非零元素用黑点表示。

稀疏矩阵（Template:Lang-en），在数值分析中，是其元素大部分为零的矩阵。反之，如果大部分元素都非零，则这个矩阵是稠密(dense)的。在科学与工程学领域中求解线性模型时经常出现大型的稀疏矩阵。

在使用计算机存储和操作稀疏矩阵时，经常需要修改标准算法以利用矩阵的稀疏结构。由于其自身的稀疏特性，通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是，由于过大的尺寸，标准的算法经常无法操作这些稀疏矩阵。

定义

给定一个N×M的稀疏矩阵A，其第n行的行带宽定义为：

$b_n(𝐀):={\mathrm{m}\mathrm{i}\mathrm{n}}_{1\le m\le M}\{m\mid a_{n,m}\ne 0\}$

整个矩阵的带宽定义为：

$B(𝐀):={\mathrm{m}\mathrm{a}\mathrm{x}}_{1\le n\le N}{b}_n(𝐀)$

例子

• 一幅双色图像以位图方式存储，若其中一种颜色的像素远远多于另一种颜色的像素（比如手写签名的扫描图像），就可以将其按稀疏矩阵编码：仅保存其少数像素的行列信息。
• 数值法求解偏微分方程（比如差分法和有限元法）时通常会出现稀疏矩阵。比如最简单的差分法的五点模板（5-point-stencil）求解泊松方程或薛定谔方程会出现稀疏矩阵。

计算方法

稀疏矩阵的「注入元」是指执行算法是从初始的零值变为非零值的那些元素。为减少内存要求和算术操作的次数，我们经常通过交换某些行或某些列来尽量减少注入元。Template:Le可以用来在做实际的柯列斯基分解之前计算最坏情况下注入元的数目。与此类似，可以用符号QR分解在做实际的QR分解之前计算最坏情况下注入元的数目。

Template:Le法是一种用于高斯消元法或LU分解中的系统处理如何减少注入元的一種方法。与此相关的一种称为Template:Link-en的方法，可以看成是它的一个特例。

參考文獻

• Template:Cite book
• Template:Cite book
• Template:Cite book (This book, by a professor at the State University of New York at Stony Book, was the first book exclusively dedicated to Sparse Matrices. Graduate courses using this as a textbook were offered at that University in the early 1980s).
• Template:Cite web
• Template:Cite book
• Template:Cite journal Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.

延伸閱讀

• Template:Cite journal
• Template:Cite journal
• Sparse Matrix Algorithms Research Template:Wayback at the University of Florida, containing the UF sparse matrix collection.
• SMALL project Template:Wayback A EU-funded project on sparse models, algorithms and dictionary learning for large-scale data.