爱华网非零元素占全部元素的百分比很小(例如5%以下)的矩阵。有的矩阵非零元素占全部元素的百分比较大（例如近50％），但它们的分布很有规律，利用这一特点可以避免存放零元素或避免对这些零元素进行运算，这种矩阵仍可称为稀疏矩阵。
稀疏矩阵稀疏矩阵(sparse matrix)是其元素大部分为零的矩阵。在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。在使用计算机存储和操作稀疏矩阵时，经常需要修改标准算法以利用矩阵的稀疏结构。由于其自身的稀疏特性，通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是，由于过大的尺寸，标准的算法经常无法操作这些稀疏矩阵。
稀疏矩阵_稀疏矩阵 -定义
非零元素占全部元素的百分比很小(例如5%以下)的矩阵。有的矩阵非零元素占全部元素的百分比较大（例如近50％），但它们的分布很有规律，利用这一特点可以避免存放零元素或避免对这些零元素进行运算，这种矩阵仍可称为稀疏矩阵。
给定一个N×M的稀疏矩阵A，其第n行的行带宽定义为：
（图）稀疏矩阵
整个矩阵的带宽定义为：
（图）稀疏矩阵
稀疏矩阵_稀疏矩阵 -历史
高斯早在20世纪，C.F.高斯、C.G.J.雅可比和其他一些人已经研究过利用矩阵稀疏性的一些办法。20世纪50年代，在线性规划和边值问题的数值解中曾出现过一些处理稀疏问题的技术。D.M.杨和R.S.瓦尔加关于迭代法方面的研究也可看作处理高阶稀疏问题的结果。但是，现代的稀疏矩阵技术主要是在60年代以后发展起来的，以60年代初期和中期W.F.廷尼和R.A.威洛比等人关于直接法的研究作为开端。
稀疏矩阵_稀疏矩阵 -优点
稀疏矩阵的计算速度更快,因为M AT L A B只对非零元素进行操作,这是稀疏矩阵的一个突出的优点.假设矩阵A,B中的矩阵一样.计算2*A需要一百万次的浮点运算,而计算2*B只需要2 0 0 0次浮点运算.因为M AT L A B不能自动创建稀疏矩阵,所以要用特殊的命令来得到稀疏矩阵.
对于一个用二维数组存储的稀疏矩阵Amn,如果假设存储每个数组元素需要L个字节,那么存储整个矩阵需要m*n*L个字节.但是,这些存储空间的大部分存放的是0元素,从而造成大量的空间浪费.为了节省存储空间,可以只存储其中的非0元素.
对于矩阵Amn的每个元素aij,知道其行号i和列号j就可以确定其位置.因此对于稀疏矩阵可以用一个结点来存储一个非0元素.该结点可以定义如下:[i,j,aij] 该结点由3个域组成,i:行号,j:列号;aij元素值.这样的结点被称为三元组结点.矩阵的每一个元素Qij,由一个三元组结点(i,j,aij)唯一确定.
例如稀疏矩阵A:
50 0 0 0
10 0 20 0
0 0 0 0
-30 0 -60 5
其对应的三元组表为：
0 0 50
1 0 10
1 2 20
3 0 -30
3 2 -60
3 3 5
稀疏矩阵_稀疏矩阵 -线性方程组
解线性方程组的直接法的稀疏矩阵技术，根据不同领域中不同问题的特点，有各种不同稀疏解法。最常用的方法有稀疏去零消元法、等带或变带宽消元法、波阵法、子结构法、撕裂和修改技术等，它们都只不过是消元法或三角分解法在各种具体场合下的运用。
各种消元法方案中的关键问题都是方程式和未知数的排序问题。确切地说，就是在用某种直接法解稀疏线性方程组时，对方程式和未知数进行适当排序，使得在满足一定的稳定性要求的前提下，解方程组所需的运算量和存贮量最少。一般说来，这等价于使新产生的非零元（“添补数”）最少。例如，对矩阵
作一步消元法，将A变成
，
，
对?作消元法时,不会有新的非零元产生，存贮量和运算量大大减少。
稀疏矩阵_稀疏矩阵 -存贮
与常用的算法相对应,排序问题可分为以下三类:①预先把矩阵排列成带型或变带宽型，并使带宽或剖面尽可能小；②预先把矩阵排列成块三角矩阵或其他特殊分块矩阵；③在稀疏消元法的消元过程中，根据产生添补数最少的原则来确定选主元的次序（这也是一种排序）。对一般矩阵，排序问题是一个非常困难的问题，因为对一个给定的矩阵来说，所有可能的次序总数是一个巨大的数字，可以给出的排序算法只是按某一特殊准则来确定“最佳次序”的。讨论中常用图论作为工具。
稀疏矩阵的存贮并没有一种最好的方式，在各种具体情况下，最好的方式与要存贮矩阵的结构及用途有关一种好的标准是矩阵的元素容易查找而且存贮量少。存贮方式基本上采用压缩形式，使矩阵中大量的零元素不参加运算，以减少机器的运行时间，并可提高机器处理高阶矩阵问题的能力。
对于带型矩阵，只存贮带内或剖面内的元素。如对矩阵
可用等带宽存贮法，在带的左上角和右下角增添若干个任意元素x，把带内的元素存放在矩形数组
中。
对于元素随机分布的稀疏矩阵，只存贮矩阵的非零元素和必要的检索信息。如对可用行指针列标格式存贮，它需要三个数组：①根据按行向右的次序，存放矩阵非零元值的数组V={p11，p12，p14，p23，p31，p34，p41，p43,p44};②存放V中每一元素在原矩阵中的列标的数组C=｛1,2,4,3,1,4,1,3,4｝;③数组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，2，3，4，5号,而总局编为6号，在平面上分别使用①，②，…,⑥这六个点表示（图2）。如果规定i局和j局之间有通信关系的话，在点i和j之间用一条线连结，对应于矩阵中Aij块和Aji块非零,i局本身内部也有通信关系,对应于矩阵Aii块非零,那么，这个问题所导出的矩阵是一个双面镶边的块对角矩阵它是一个稀疏矩阵。
稀疏矩阵_稀疏矩阵 -相关词条
矩阵
微积分
迭代
存贮
稀疏矩阵_稀疏矩阵 -参考资料
[1]. 梯华森著,朱季纳译：《稀疏矩阵》，科学出版社,北京，1981。(R.P.Tewarson,Sparse Matrices,AcademicPress, New York, 1973.)
[2].数据结构http://www.hiahia.org/datastructure/duoweishuzu/duoweishuzu5.2.3.1.htm
