稀疏矩陣

稀疏矩陣的例子
上述稀疏矩陣僅包含9個非零元素,另外包含26個零元素。其稀疏度為74%,密度為26%。

稀疏矩陣(英語:sparse matrix),在數值分析中,是其元素大部分為零的矩陣。反之,如果大部分元素都非零,則這個矩陣是稠密(dense)的。在科學工程學領域中求解線性模型時經常出現大型的稀疏矩陣。

計算有限元問題時得到的稀疏矩陣。非零元素用黑點表示。

在使用電腦儲存和操作稀疏矩陣時,經常需要修改標準演算法以利用矩陣的稀疏結構。由於其自身的稀疏特性,通過壓縮可以大大節省稀疏矩陣的主記憶體代價。更為重要的是,由於過大的尺寸,標準的演算法經常無法操作這些稀疏矩陣。

定義

給定一個N×M的稀疏矩陣A,其第n行的行頻寬定義為:

 

整個矩陣的頻寬定義為:

 

例子

計算方法

稀疏矩陣的「注入元」是指執行演算法是從初始的零值變為非零值的那些元素。為減少主記憶體要求和算術操作的次數,我們經常通過交換某些行或某些列來儘量減少注入元。符號柯列斯基分解英語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.

延伸閱讀