稀疏矩阵

维基百科,自由的百科全书
跳转至: 导航搜索

稀疏矩阵(Sparse matrix),是其元素大部分为零的矩阵。在科学工程领域中求解线性模型时经常出现大型的稀疏矩阵。

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

定义[编辑]

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

b_n(\mathbf{A}) := \mathrm{min}_{1 \le m \le M} \lbrace m \mid a_{n, m} \neq 0 \rbrace

整个矩阵的带宽定义为:

B(\mathbf{A}) := \mathrm{max}_{1 \le n \le N} b_n(\mathbf{A})

例子[编辑]

计算方法[编辑]

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

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