稀疏矩阵

稀疏矩阵是其元素大部分为零的矩阵。

在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。

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

定义

给定一个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})$

例子

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

存储稀疏矩阵

参见稀疏矩阵(数据结构)

计算方法

减少注入元(fill-in)

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

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