打开主菜单
稀疏矩陣的例子
上述稀疏矩陣僅包含9個非零元素,另外包含26個零元素。其稀疏度為74%,密度為26%。
A sparse matrix obtained when solving a finite element problem in two dimensions. The non-zero elements are shown in black.

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

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

目录

定义编辑

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

 

整个矩阵的带宽定义为:

 

例子编辑

计算方法编辑

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

延伸閱讀编辑