3.1概述3.1概述3.1概述3.1概述3.1概述3．2稀疏(xīshū)技术稀疏矢量的存储：只需存储矢量中的非零元素值和相应的下标。对稀疏矩阵，有几种不同的存储方法，除了和矩阵的稀疏结构的特点有关，还和使用时所采用的算法有关。不同的算法往往要求对稀疏矩阵中的非零元素有不同的检索方式。因此，应根据应用对象的实际(shíjì)情况来选择合适的存储方式。3.2稀疏(xīshū)技术3.2稀疏(xīshū)技术3.2稀疏(xīshū)技术3.2稀疏(xīshū)技术3.2稀疏(xīshū)技术例：3.2稀疏(xīshū)技术3．2稀疏(xīshū)技术3.2稀疏(xīshū)技术3．2稀疏(xīshū)技术1.前代运算将L分解成一个单位矩阵和一个严格(yángé)下三角矩阵之和3．2稀疏(xīshū)技术3．2稀疏(xīshū)技术3.3稀疏(xīshū)矩阵的图论描述1基本定义(dìngyì)和术语2.因子分解过程的图论(túlùn)描述（2）消去运算(图3.4)取第p行第p列为轴线，第p步的消去运算实际上就是要对处于轴线上的非零元素所在的行列相交叉的位置上的元素进行消去运算。如图，需要对处于第p行第p列上的非零元素所在的j，k，l行和j，k，l列相交叉的位置上的共9个元素进行消去运算。如果只保留(bǎoliú)上三角矩阵，只需要对三个对角元素和三个非对角元素进行消去运算。对对角元素的修正公式是aii=aii-aipapip<i,i=j,k,l（式3）因为在消去运算之前已经对api进行过规格化运算，而式中的aip还没有进行过规格化，而aip=apiapp因此使用上三角元素计算时，消去运算的公式应该用下式：aii=aii–api2appp<i,i=j,k,l（式4）在赋权有向A图上，就是对节点p发出的边的收点j,k,l上的自边边权进行修正，边权减少api2app。对于上三角部分的非零元素，共有三个需要修正，即ajk,akl,ajl,如图3.4。对于非对角元素，消去运算的公式为：aim=aim–aipapmi<m,p<i,p<mi,m从j,k,l中取值（式5）因为只储存A的上三角部分，所以aip（下三角元素）应该用api代替，上述公式变为：aim=aim–apiapmappi<m,p<i,p<mi,m从j,k,l中取值（式6）在图中，相当于在节点(jiédiǎn)p发出的边中任取两边，其收点所夹的边的边权应被修正，该边权应减少这样的数值：p点发出的两个边的边权与p点自边边权三者的乘积。按这种叙述方法，前面描述的对角元素的修正可以看作（式6）的一种特殊情况，即（式4）相当于（式6）中节点(jiédiǎn)p发出的两条边重合（p,i），被夹住的边即为节点(jiédiǎn)i的自边。如果节点对之间原来无边，例如图上节点对j，l之间原来无边，消去运算后会产生新边，这和因子分解过程中产生注入元素相对应。当新边产生后，按节点号从小(cóngxiǎo)指向大给新边冠之以方向。对节点p进行消去运算后，节点p的自边和其发出的互边在后面的运算中不再需要，将它们遮住。按节点号从小(cóngxiǎo)到大依次进行计算，当所有节点的规格化和消去运算都做完之后，即得到赋权有向因子图。可见，在图上进行因子分解，每步操作都是对某节点p发出的边以及这些边所夹的边进行的，实际上和矩阵A中第p行的非零元素相对应。所做的都是有效操作，因为矩阵中的零元素，在赋权有向图中没有边相对应。在图上进行因子分解，可以使我们对稀疏矩阵的作用机理有更直观形象的理解。3前代回代过程的图论(túlùn)描述将这段程序和赋权有向因子图连系起来看，uij≠0就表示赋权有向因子图上节点i，j之间有边；uij＝0，则图上不出现边。把zi定义为赋权有向因子图上的点位，用ei表示；赋权有向因子图上的互边的边权是uij，则上面的程序可以写成：ej=ej-uijeii<j,j∈i（式7）线性代数方程组中独立矢量或解矢量中的非零元素可以用赋权有向因子图上节点的点位来描述，而前代过程可在赋权有向因子图上用点位的变化来描述。首先，在赋权有向因子图上，将每个节点的点位赋值以独立矢量b中相应的非零元素的值。然后在赋权有向因子图上按节点号i从小到大顺序（因为是前代）依次按（式7）修正该节点i发出边的对端节点j的点位，将对端节点j的点位减小uijei。这一过程一种进行到将所有点都扫描完。如果节点i的点位为零，说明zi为零，上述修正不需要做。这一过程结束后，因子图上的点位就是(jiùshì)前代的结果。（对照51页式3－6a）2.规格化过程规格化过程的实质是求解Dy=z中的y，D是对角元素矩阵，z在前代过程中已经求出。因此求解y很容易，只需要做除法运算(yùnsuàn)y