稀疏矩阵 (数学)
维基百科，自由的百科全书
 |
本条目或者章节被建议合并到稀疏矩阵。（讨论） |
稀疏矩阵是其元素大部分为零的矩阵。
在使用计算机存储和操作稀疏矩阵时，经常需要修改标准算法以利用矩阵的稀疏结构。由于其自身的稀疏特性，通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是，由于过大的尺寸，标准的算法经常无法操作这些稀疏矩阵。
目录 |
[编辑] 定义
给定一个N×M的稀疏矩阵A，其第n行的行带宽定义为： 
整个矩阵的带宽定义为： 
[编辑] 例子
- 一幅双色图像以位图方式存储，若其中一种颜色的像素远远多于另一种颜色的像素（比如手写签名的扫描图像），就可以将其按稀疏矩阵编码：仅保存其少数像素的行列信息。
- 数值法求解偏微分方程（比如差分法和有限元法）时通常会出现稀疏矩阵。比如最简单的差分法的五点模板（5-point-stencil)求解泊松方程或薛定谔方程会出现以下类型的稀疏矩阵：（图像有待上传）
[编辑] 存储稀疏矩阵
参见稀疏矩阵(数据结构)
[编辑] 计算方法
[编辑] 减少fill-in
矩阵的fill-in是指执行算法是从初始的零值变为非零值的那些元素。为减少内存要求和算术操作的次数，我们经常通过交换某些行或某些列来尽量减少fill-in。符号Cholesky分解可以用来在做实际的Cholesky分解之前计算最坏情况下fill-in的数目。与此类似，我们可以用符号QR分解在做实际的QR分解之前计算最坏情况下fill-in的数目。
消去树（elimination tree）法是一种用于高斯消去（en:Gaussian elimination）或LU分解（en:LU factorization)中的系统处理如何减少fill-in的方法。与此相关的一种称为en:nested dissection的方法可以看成是它的一个特例。
