稀疏矩陣

稀疏矩陣（英語：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.