稀疏矩阵

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

稀疏矩阵的例子 ${\displaystyle \left[{\begin{smallmatrix}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{smallmatrix}}\right]}$

上述稀疏矩阵仅包含9个非零元素，另外包含26个零元。其稀疏度为74%，密度为26%。

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

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

定义

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

${\displaystyle b_{n}(\mathbf {A} ):=\mathrm {min} _{1\leq m\leq M}\lbrace m\mid a_{n,m}\neq 0\rbrace }$

整个矩阵的带宽定义为：

${\displaystyle B(\mathbf {A} ):=\mathrm {max} _{1\leq n\leq N}b_{n}(\mathbf {A} )}$

例子

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

计算方法

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

消去树（英语：elimination tree）法是一种用于高斯消元法或LU分解中的系统处理如何减少注入元的一种方法。与此相关的一种称为嵌套解剖（英语：Nested dissection）的方法，可以看成是它的一个特例。

参考文献

• Golub, Gene H.; Van Loan, Charles F. Matrix Computations 3rd. Baltimore: Johns Hopkins. 1996. ISBN 978-0-8018-5414-9.
• Stoer, Josef; Bulirsch, Roland. Introduction to Numerical Analysis 3rd. Berlin, New York: Springer-Verlag. 2002. ISBN 978-0-387-95452-3.
• Tewarson, Reginald P. Sparse Matrices (Part of the Mathematics in Science & Engineering series). Academic Press Inc. May 1973. (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).
• Bank, Randolph E.; Douglas, Craig C. Sparse Matrix Multiplication Package (PDF). [2019-02-09]. （原始内容 (PDF)存档于2014-12-21）.
• Pissanetzky, Sergio. Sparse Matrix Technology. Academic Press. 1984.
• Snay, Richard A. Reducing the profile of sparse symmetric matrices. Bulletin Géodésique. 1976, 50 (4): 341. doi:10.1007/BF02521587. Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.

延伸阅读

• Gibbs, Norman E.; Poole, William G.; Stockmeyer, Paul K. A comparison of several bandwidth and profile reduction algorithms. ACM Transactions on Mathematical Software. 1976, 2 (4): 322–330. doi:10.1145/355705.355707.
• Gilbert, John R.; Moler, Cleve; Schreiber, Robert. Sparse matrices in MATLAB: Design and Implementation. SIAM Journal on Matrix Analysis and Applications. 1992, 13 (1): 333–356 [2019-02-09]. CiteSeerX 10.1.1.470.1054 . doi:10.1137/0613024. （原始内容存档于2008-06-06）.
• Sparse Matrix Algorithms Research （页面存档备份，存于互联网档案馆） at the University of Florida, containing the UF sparse matrix collection.
• SMALL project （页面存档备份，存于互联网档案馆） A EU-funded project on sparse models, algorithms and dictionary learning for large-scale data.