关于稀疏矩阵介绍

[拼音]：xishu juzhen

[外文]：sparse matrix

非零元素占全部元素的百分比很小(例如5%以下)的矩阵。有的矩阵非零元素占全部元素的百分比较大（例如近50％），但它们的分布很有规律，利用这一特点可以避免存放零元素或避免对这些零元素进行运算，这种矩阵仍可称为稀疏矩阵。图1

用阴影表示出一些常见的稀疏矩阵中非零元素的分布。

早在一个世纪以前，C.F.高斯、C.G.J.雅可比和其他一些人已经研究过利用矩阵稀疏性的一些办法。20世纪50年代，在线性规划和边值问题的数值解中曾出现过一些处理稀疏问题的技术。D.M.杨和R.S.瓦尔加关于迭代法方面的研究也可看作处理高阶稀疏问题的结果。但是，现代的稀疏矩阵技术主要是在60年代以后发展起来的，以60年代初期和中期W.F.廷尼和R.A.威洛比等人关于直接法的研究作为开端。稀疏矩阵的研究已经渗入到很多领域。例如，在结构分析、网络理论、电力分配系统、化学工程、摄影测绘学以及管理科学等方面研究中，都出现了上千阶直至几十万阶的稀疏矩阵。

这里考察从一个电信总局到其各支局间的通信问题。不妨假定有五个支局，依次编为1，2，3，4，5号，而总局编为6号，在平面上分别使用①，②，…，⑥这六个点表示（图2

）。如果规定i局和j局之间有通信关系的话，在点i和j之间用一条线连结，对应于矩阵中Aij块和Aji块非零，i局本身内部也有通信关系，对应于矩阵Aii块非零，那么，这个问题所导出的矩阵是一个双面镶边的块对角矩阵

它是一个稀疏矩阵。

解线性方程组的直接法的稀疏矩阵技术，根据不同领域中不同问题的特点，有各种不同稀疏解法。最常用的方法有稀疏去零消元法、等带或变带宽消元法、波阵法、子结构法、撕裂和修改技术等，它们都只不过是消元法或三角分解法在各种具体场合下的运用。

各种消元法方案中的关键问题都是方程式和未知数的排序问题。确切地说，就是在用某种直接法解稀疏线性方程组时，对方程式和未知数进行适当排序，使得在满足一定的稳定性要求的前提下，解方程组所需的运算量和存贮量最少。一般说来，这等价于使新产生的非零元（“添补数”）最少。例如，对矩阵

作一步消元法，将A变成

，

右下角子阵是满的，A的零元所在位置上产生了许多非零元，破坏了稀疏性，这就要增加许多存贮量和运算量；如果将矩阵A的第一行与最后一行，第一列与最后一列交换，这相当于重新排列方程式和未知数的次序，得矩阵

，

对Ã作消元法时，不会有新的非零元产生，存贮量和运算量大大减少。

与常用的算法相对应，排序问题可分为以下三类：

（1）预先把矩阵排列成带型或变带宽型，并使带宽或剖面尽可能小；

（2）预先把矩阵排列成块三角矩阵或其他特殊分块矩阵；

（3）在稀疏消元法的消元过程中，根据产生添补数最少的原则来确定选主元的次序（这也是一种排序）。对一般矩阵，排序问题是一个非常困难的问题，因为对一个给定的矩阵来说，所有可能的次序总数是一个巨大的数字，可以给出的排序算法只是按某一特殊准则来确定“最佳次序”的。讨论中常用图论作为工具。

稀疏矩阵的存贮并没有一种最好的方式，在各种具体情况下，最好的方式与要存贮矩阵的结构及用途有关一种好的标准是矩阵的元素容易查找而且存贮量少。存贮方式基本上采用压缩形式，使矩阵中大量的零元素不参加运算，以减少机器的运行时间，并可提高机器处理高阶矩阵问题的能力。

对于带型矩阵，只存贮带内或剖面内的元素。如对矩阵

可用等带宽存贮法，在带的左上角和右下角增添若干个任意元素x，把带内的元素存放在矩形数组

中。

对于对称带型阵

可用变带宽存贮法。它需要两个数组：

（1）存放剖面内的元素的一维数组S[1:11]={b11，b21，b22，b31，0，b33，b44，b53，0，b55，b66}；

（2）对角元数组D[1:6]={1，3，6，7，10，11}，在它的第i个位置上存放对角元bii在数组S中的序号。这样，矩阵的元素bij可通过D，i，j在S中找到。对应关系为

并规定D(0)=0。例如，由D[3]=6，D[2]=3，D[3]-3+1>D[2]，可得b31=S[4]。

对于元素随机分布的稀疏矩阵，只存贮矩阵的非零元素和必要的检索信息。如对

可用行指针列标格式存贮，它需要三个数组：

（1）根据按行向右的次序，存放矩阵非零元值的数组 V={p11，p12，p14，p23，p31，p34，p41，p43，p44}；

（2）存放V中每一元素在原矩阵中的列标的数组C=｛1，2，4，3，1，4，1，3，4｝；

（3）数组R=｛1，4，5，7，10｝，在它的第i个位置上存放矩阵第i行的第一个非零元在数组V中的序号，最后一个位置上的数等于矩阵非零元素个数加1。矩阵p的任意非零元素可根据R和C的值定出它在V中的位置。例如p31，先由R[3]=5，R[4]=7，确定第三行有两个非零元V[5]和V[6]，再检查V[5]和V[6]的列标，由C[5]=1，C[6]=4，可推出V[5]=p31。

此外，还有连接表存贮法和超矩阵存贮法等。

对稀疏矩阵的共轭斜量法、隆措什法等迭代法研究的兴趣日益浓厚，稀疏矩阵的研究也不再局限于稀疏线性方程组的解法问题，而是扩展为对所有高阶稀疏问题的研究。

参考书目

1. 梯华森著，朱季纳译：《稀疏矩阵》，科学出版社，北京，1981。(R.P.Tewarson，Sparse Matrices，AcademicPress， New York， 1973.)