《三、稀疏技术及稀疏向量法PPT优秀课件.ppt》由会员分享，可在线阅读，更多相关《三、稀疏技术及稀疏向量法PPT优秀课件.ppt（81页珍藏版）》请在三一文库上搜索。
1、版权所有,1,三稀疏技术及稀疏向量法,版权所有,2,主要内容,因子表应用因子表元素因子表求解稀疏因子表,稀疏技术概述稀疏技术稀疏存储稀疏矩阵因子分解利用稀疏矩阵因子表求解稀疏线性方程组稀疏技术的图论描述术语及定义因子分解的图论描述前代回代的图论描述,稀疏向量法,版权所有,3,回顾几个结论：以高斯消元法逐列消元，对应于以消去节点法逐个消去节点消元过程中的注入元，在物理意义上对应于由于消去某节点而出现新的互联支路导纳。就形成因子表而言，三角分解法与高斯消元法完全等效，而以高斯消元法逐列消元又对应于以消去节点法逐个消去节点，因此可通过考察消去节点以考察因子表的形成基于如上关系，高斯消元后如出现注入元
2、，该注入元也将出现在三角分解后所得的上、下三角矩阵中，并将出现在所形成的因子表中。因子表中是否会出现注入元等价于网络消去节点后是否会出现新的互联支路。,版权所有,4,一、 因子表应用,网络方程需要求解多次，每次只是改变方程右端的常数向量，因此，考虑采用因子表因子矩阵的元素以适当的形式贮存起来以备反复应用。 因子表的形成有多种方式，一般有按行消元，逐行规格化的高斯消去与上面高斯消去法对应的CROUT分解LDU分解,版权所有,5,作LDU分解时，把各因子矩阵的元素排列成因子表：,对对称矩阵的因子矩阵L和U互为转置矩阵，在因子表中保留上三角部分（或下三角部分）对角线位置则存放矩阵D的对应元素的倒数，
3、便于计算,版权所有,6,（226）,因子矩阵的元素表达式如下,版权所有,7,利用因子表(LDU分解)求解分两步：,前代（消元）：,（i=n,n-1,.,1 ) (32),（31）,回代：,或者前代（消元）：,（33）,回代：,（34）,（35）,版权所有,8,右端的常数向量取为：,解：形成LDU分解后因子表如下：,例31 用因子表求解方程组AX=B。,版权所有,9,先做消元运算,再做回代,版权所有,10,做规格化及消元运算,1.,2.,3.,版权所有,11,做回代运算,1.,2.,3.,版权所有,12,稀疏因子表的利用,如对原始方程，令：,得到同解方程:,相应因子表（LDU）是稀疏的:,相当于
4、优化编号,版权所有,13,求解：,LDU因子表:,以上完成全部消去,以上完成全部回代,版权所有,14,从例子中看出,当线性方程组的稀疏性得到充分应用时形成因子表过程中减少了计算量更重要的是减少了求解方程组时前代和回代的计算量,版权所有,15,电力网络特点决定了电网计算中的矩阵及矢量是稀疏的 对mn阶矩阵A的稀疏度定义：,对稀疏矩阵,二、稀疏技术1、概述,如对节点导纳矩阵，如果每个节点的出线度是，则对N维导纳阵,版权所有,16,稀疏技术 针对稀疏矩阵及稀疏矢量，进行排零存储及排零计算W. F. Tinney,版权所有,17,2. 稀疏技术,对mn阶稀疏矩阵A，其非零元素共有个，令aij是A中第i
5、行第j列非零元素。可以定义三个数组，按下面的存储格式存储矩阵A中非零元素的信息：VA存储A中非零元素aij的值，共 个IA存储A中非零元素aij的行指标i，共 个 JA存储A中非零元素aij的列指标j，共 个,2.1.1 散居格式,2.1 稀疏存储,总共需要3 个存储单元优点：A中非零元在数组中的位置可任意排列，修改灵活。缺点：其存储顺序无一定规律，检索起来不方便。最差的可能性要在整个数组中查找一遍。,版权所有,18,如查找第i行的非零元素在VA中取出从kIA(i)到IA(i1)1共IA(i1)IA(i)个非零元就是A中第i行的全部非零元非零元的值是VA(k)，列号JA(k),2.1.2 按行
6、（列）存储格式,按行(列)顺序依次存储A中的非零元，同一行(列)元素依次排在一起。以按行为例，其存储格式是：VA按行存储矩阵A中非零元aij ，共 个；JA按行存储矩阵A中非零元的列号，共 个；IA记录A中每行第一个非零元素在VA中的位置，共m个。,如查找第i行第j列的元素aij在VA中的位置对k从IA(i)到IA(i1)1，判断列号JA(k)是否等于j，如等， VA(k) 就是 要的非零元aij,版权所有,19,U存A的上三角部分的非零元的值，按行依次存储JU存A的上三角部分的非零元的列号IU存A中上三角部分每行第一个非零元在U中的位置(首地址)L按列存储A中下三角非零元素的值IL按列存储A
7、中下三角非零元素的行号JL存储A的下三角部分每列第一个非零元在L中的位置(首地址)D存储A的对角元素的值，其检索下标不需要存储,2.1.3 三角检索存储格式,特别适用于稀疏矩阵的三角分解。有几种不同的存储格式。以按行存储A的上三角部分非零元按列存A的下三角部分非零元存储格式为例来说明。令A是n n阶方阵：,版权所有,20,U存A的上三角部分的非零元的值，按行依次存储JU存A的上三角部分的非零元的列号IU存A中上三角部分每行第一个非零元在U中的位置(首地址)L按列存储A中下三角非零元素的值IL按列存储A中下三角非零元素的行号JL存储A的下三角部分每列第一个非零元在L中的位置(首地址)D存储A的对
8、角元素的值，其检索下标不需要存储,三角检索存储格式示例,版权所有,21,IU（3）为4，表明A矩阵上三角部分第3行的第1个非零元如果有的话应在U的第4个位置，而U表中第4个位置没有非零元素，为了检索方便，IU(3)仍应赋值4。有了IU表即可知道A的上三角部分第i行的非零元的数目如果要查找A的上三角第i行所有非零元素，只要扫描A从IU(i)到IU(i+1)1即可，JU(k)指出了该元素的列号，U(k)是该非零元素的值。对于按列存储的格式进行查找的情况类同。,IU,JU,U,版权所有,22,UJUIU LILJL D,三角检索存储,占用的存储单元分析:对于数组U,L,D共需 个存储单元，此例为10
9、。对JU，IL共需n个存储单元，此例中为6；对IU，JL，共需2n个存储单元，此例为8总计需占用2 +n个存储单元。 是矩阵A中的非零元素的数目。,版权所有,23,三角检索存储格式在矩阵A的稀疏结构已确定的情况下使用是十分方便的。但在计算过程中，如果A的稀疏结构发生了变化，即其中的非零元素的分布位置发生变化，相应的检索信息也要随着变化，很不方便。有两种办法处理事先估计注入，符号分解。链表格式,版权所有,24,2.1.4 链表存储格式,以按行存储的格式为例来说明。这时除了需要按行存储格式中的三个数组外还需要增加下列数组：LINK下一个非零元素在VA中的位置，对每行最后一个非零元素，该值置为0。N
10、A每行非零元素的个数。,版权所有,25,当新增加一个非零元素时，可把它排在最后，并根据该非零元素在该行中的位置的不同来修改其相邻元素的LINK值。例如，新增a13，把a13排在第11个位置，把a12的LINK值由3改为11， a13本身的LINK值置为3，NA(1)增加1，变为4。,链表存储格式,重现第i行的所有元素：,所以，只要用IA把该行第一个非零元素找到，就可以按LINK的指示找下一个非零元素。直到把该行中所有非零元素都找出来为止。当找到第i行最后一个非零元素时LINK(A)0，这时do循环结束。,版权所有,26,2.2 稀疏矩阵因子分解,对nn阶矩阵A，分解成下三角矩阵L和单位上三角矩
11、阵U两者的乘积，即ALU。常规计算流程如下：,在第p步计算中，规格化只有apj0计算才有效。在消去运算中，只有aip以及apj都不为零才有效。,判apj0则执行,判aip及apj 0则执行,版权所有,27,对稀疏存储格式应按所采用的存储格式的要求进行计算。例如，当假定对矩阵A进行了符号分解，当用三角检索存储格式时可用下面计算流程。,注意,稀疏存储格式时的因子分解,只用非零元素U(k)，L(l)计算,版权所有,28,对不同的分解方法有不同的计算流程。但主要是避免无效运算。,版权所有,29,2.3 利用稀疏矩阵因子表求解稀疏线性方程组,对Ax=b ，假定分解成ALDU。则有：Lz=b 前代过程Dy
12、=zUx=y 回代过程,如果b是稀疏向量，则仅有L的列子集参与（33）及（34）前代运算，而不是L的所有列参与，这种算法被称之为快速前代。,对于解向量一般不稀疏，但如果只对其中的某些元素感兴趣，只求解部分元素，仅有U的行子集参与（35）回代运算，而不是U的所有行参与。这种算法就是快速回代。,（36）,（37）,（38）,版权所有,30,1. 前代过程,如果将L分解成一个单位矩阵和一个严格下三角矩阵 的和，则Lz=b式可改写成:,式中，li 是 的第i个列矢量,（39）,版权所有,31,结构如下：,矢量li的元素从第1个到第i个都是零，所以式中右边的zi对左边矢量z中前i个元素没有贡献，只会对i
13、1到n的有影响。,（39a）,版权所有,32,即z中的第i个元素zi ，只会对z中下标大于i的元素有影响。换句话说， z中某元素只会受z中比该元素下标小的元素影响。因此，前代运算应从小号到大号依次进行。计算流程如下：,还要考虑li的稀疏性，所以对lji为0的不计算。对外循环中，zi 为0则该次循环不计算。,（39b）,版权所有,33,考虑了矩阵和矢量的稀疏性，重写前代的计算流程：,实际应用中，并不需要去判断元素是否为零，而是按排零存储格式直接取出非零元来进行运算。,（39c）,版权所有,34,首先将独立b矢量送入z,依次对i=2,3,4，有,例32 求前代过程,对i=1，只有两个非零元l21和
14、l52和，因此有,版权所有,35,可见： (1) 矢量z中下标小的元素只会影响下标大的元素，而不会影响比该元素下标小的元素。例如z2不会影响z1，z3不会影响z1和z2，等等。 (2) 前代中只取 每列中非零元素并用它和z矢量中相应元素进行前代运算。例如i1时，l3l和l4l是零元素，不必考虑z1和这两个零元素的运算。在稀疏矩阵计算中，实际上只扫描该列中的非零元素，而不必扫描零元素。 (3) 如果前代之前b中只有少数非零元素，例如b中只有b2是非零元素，由上面计算过程可知，i1的计算步可省去(因为z1 =0)。i2的计算步结束后， z4和z5变成非零元素， z3仍是零。i= 3的计算步也可省去
15、。经过i4计算步后，最终的解z中也只有三个非零元素，即z2，z4，z5。这说明如果原来独立矢量是稀疏的，前代结束后，解矢量仍可能是稀疏的。到底哪些元素将由零元素变成非零元素，取决于 的稀疏结构，也取决于独立矢量b中非零元素的分布。,版权所有,36,求解(37)式，只需做以下除法运算； yizidii i1，n (310) dii是D的第i个对角元素。很明显，对于zi 0的除法运算可以省略。,2. 除法运算,版权所有,37,用(38)式求解x时，将U分解为一个单位矩阵和一个严格上三角矩阵，则(38)式可以写成:,3. 回代运算,（311）,可以写成,（312）,版权所有,38,uj是严格上三角矩
16、阵 的第j个列矢量。对应上式的流程：,可见，矢量x中的元素下标大的可能影响下标小的，而不会影响下标大的。回代应从大号到小号依次进行。(3-12)可写成,（313）,（313a）,版权所有,39,考虑稀疏性的回代运算流程：S是x当中应当进行回代的元素的集合。,如果：x中只有少数元素是我们所需要的，其它元素不需要，例如某元素xk需要计算，(313a)式的回代的外环只需扫描到k十1即可，这是因为jk的回代对xk无贡献。,（313b）,版权所有,40,首先将y送入x,j=4，有,例33 回代过程,j=5，uj有三个非零元,j=3，u23和u13都是0，此步不做j=2， x1 x1u12 x2,版权所有
17、,41,可见：x中下标小的元素不会影响下标大的元素。例如x4不会影响x5， x3 x2 不会影响x4等等，所以回代运算应从后向前进行。每步回代过程中，只取uj中非零元素和x矢量中相应元素进行乘法运算，不必考虑uj中的零元素和x中相应元素进行的运算。例如j5时，u35是零元素，不必考虑u35和x5的运算。如果在最终的结果x中，我们只要用到其中一个元素x2，其它4个元素我们不需要，这时上面的计算步中有些可以省略。,版权所有,42,3. 稀疏技术的图论描述,3.1 术语及定义,对称矩阵A中的非零元素的分布可用一个网络图来描述。矩阵A的因子表矩阵D中的非零元素的分布也可以用一个网络图来描述。例如，矩阵
18、A非零元素的分布是： 因子分解后U的非零元是：,（314）,（315）,版权所有,43,A图：和矩阵A有相同拓扑结构的网络图。有向A图：在给定的A图上，对于给定的节点编导，规定每条边的正方向都是由小号节点指向大号节点，这样形成的有向图。赋权有向A图：在有向A图上，将A的非对角非零元素所对应的边称为互边，并将该边的权赋之以该非零元素的值。将A的对角元素用在有向A图上的接地边模拟，称之为自边，并赋之以该对角元素的值。这样得到的有向A图称之为赋权有向A图。,版权所有,44,类似，可以用图描述因子表U。因子图 有向因子图 赋权有向因子图,对对称矩阵A的图上因子分解就是要将赋权有向A图变成赋权有向因子图
19、。两者图的结构不同，后者互边的边数比前者多，而且两者的边权也不同。,版权所有,45,以下图为例，对第p行规格化。,3.2 因子分解的图论描述,3.2.1 规格化运算,这在赋权有向A图上，相当于对节点p发出的所有互边的边权加以修正。新的边权等于原边权除以节点p的自边边权。节点p发出的互边边权发生了变化，边数并未增加。,（316）,版权所有,46,取第p行第p列为轴线。第p步的消去运算实际上是要对处于轴线上的非零元素所在的行列相交叉的位置上的元素进行消去运算。在图中用划表示。图中划O表示消去前已经存在非零元素。需要进行消去运算的元素中3个是对角元素，6个是非对角元素。如果只保留上三角矩阵，只需对3
20、个对角元素和3个非对角元素进行消去运算。,3.2 因子分解的图论描述,3.2.2 消去运算,版权所有,47,对对角元素消去运算的修正公式是 aii=aiiaipapi pi, i=j,k,l,由于在消去前已经对api进行过规格化，而上式中aip还没有规格化，有aip=apiapp， 所以当使用上三角元素计算时，有：,aii=aiiapi2 app pi, i=j,k,l,（317）,在赋权有向A图上，就是对节点p发出的边的收点j，k，l上的自边边权进行修正，边权减少api2 app,版权所有,48,对上三角元素消去运算，有三个元素ajk，akl，ajl，公式是: aim=aimaipapm p
21、im, i,m从j,k,l取值,由于仅使用上三角元素计算, 有aip=apiapp，所以有：,aim=aimapiapmapp pim, i,m从j,k,l取值,（318）,在赋权有向A图上，相当于在节点 p发出的边中任取两边，其收点所夹的边的边权应被修正，该边权应减少 p点发出的两个边的边权与p点自边边权三者的乘积。,版权所有,49,可以认为，对角元计算公式（317）是上三角元素计算公式（318）的特例消去运算后，如互边边权为0，仍应该保留产生新边时，按节点号从小到大冠以方向对节点p进行消去运算后，节点p的自边和节点p发出的互边在后面的消去运算中不再需要，我们将它们遮盖住。按节点号大小从小号
22、到大号依次进行上述过程，当对所有节点的规格化和消去运算都做完之后，图全部被遮盖住，把遮盖打开，这个图就是赋权有向因子图。,版权所有,50,在赋权有向A图上按节点号由小到大顺序(例如对节点p)执行下面的操作：对节点p发出的互边将其边权除以节点p的自边边权；对节点p发出的互边的对端收点，将该点上的自边边权减去该互边边权平方乘以节点p上的自边边权；对节点p发出的所有互边，这些互边两两之间所夹的互边边权应减去两条相夹边边权与节点p的自边边权三者乘积。操作前被夹节点对之间无边的情况可视为有一条零权值边。将所有和p相联的边遮盖住，选下一个节点，返回步骤(1)。,总结图上因子分解,版权所有,51,例34 图
23、上因子分解,版权所有,52,版权所有,53,版权所有,54,版权所有,55,考虑对称矩阵A，假定已经将独立矢量b赋值到工作矢量z中，前代从小号点到大号点进行，对第i步前代，对应（39C）,3.3 前代回代的图论描述,3.3.1 前代运算,注意到两点：1. 下标ji，说明边是由小号节点指向大号节点。2. uij0，表示是上三角中的非零元素。该流程可以与赋权有向图联系。,版权所有,56,如果把zi定义为赋权有向因子图上的点位，用ei表示，赋权有向因子图上的互边边权是uij，则上面程序可写成：,3.3.1 前代运算,前代过程在赋权有向因子图上用点位变化描述：每个节点点位赋值独立矢量b中相应值。在图上
24、按节点i由小到大顺序修正该节点i发出对端节点j的点位,（319）,表示uij是从节点i发出的边的边权。隐含着 uij 0,版权所有,57,参考(310)式，将前代结束后节点i的点位ei除以赋权有向因子图上节点i的自边边权，即,3.3.2 规格化运算,上式即是规格化结果,（320）,版权所有,58,参考(3l3a)式。令赋权有向因子图上的点位已经是经过前代和规格化后的值。在此图上节点号j从n开始，由大到小，对所有指向j的边其发端节点i的点位进行修正，修正公式是：,3.3.3 回代运算,（321）,当所有节点的点位都修正完后，回代过程结束。,也可以换一种说法，将赋权有向因子图上所有边反向然后按节点
25、号从大到小顺序象前代计算过程一样按箭头方向去修正点位。,版权所有,59,总结1,图上前代回代计算步骤如下：将独立矢量b的非零元素赋值为赋权有向因子图上的点位；扫描i从1到n1。用(319)式修正节点i发出的边的对端节点j的点位。对所有节点用(320)式对点位规格化。扫描j从n到2。对所有指向节点j的边的发端节点i，用(321)式修正其点位。,如果图上有条互边，n条自边。则前代回代最多进行次乘法，规格化最多要进行n次除法运算。所以整个前代回代最多要进行2n次乘除运算。,版权所有,60,总结2,图上前代回代中有关问题：在前代过程中，某节点i的点位是零时，该步前代计算可以省略，即(319)式只需对e
26、i0的节点进行计算，但应注意前代开始前点位是零的节点在前代进行过程中也可能会变成非零。(320)式的规格化计算也只在点位不等于零的节点上进行。在回代过程中，某点i的点位只受到由该点i发出的边的收点j的点位的影响，这些收点j的点位，又受到它们各自发出的边的收点的点位的影响，以此类推。所以，从某节点i沿图上箭头方向搜索直到根节点n，就可以找到影响该节点i的点位的所有节点。就研究节点i的点位而言，其它节点的回代可以省略。如果解矢量x中我们只需要少数几个元素，我们则可以用这一原理在图上找到影响这几个元素的节点，回代计算只对这些节点的点位进行。,版权所有,61,例35 图上前代回代运算,（a）赋权有向因
27、子图和独立矢量的点位,前代过程 (对独立矢量b=0 1 0 0T),按节点号从小到大顺序搜索点位不是零的节点进行运算。节点点位为零不用计算对节点进行前代运算。节点发出两条边，(2，3)和(2，4)。利用(319)式则：,再做节点，它只发出一条边(3，4)，则：,前代后点位如图（b）,d,d,u,u,u,u,d,（b）前代后点位,版权所有,62,规格化过程,点的点位是零，只需利用(320)式对点， 和规格化。,规格化后点位如图（c）,d,d,d,（b）前代后点位,（c）规格化后点位,u,u,u,u,u,版权所有,63,回代过程,按节点号由大到小做。以节点为收点的边有三条：(3，4)，(2，4)，
28、(1，4)。用(321)式修正指向节点的边的发点的点位：,最后得到点位图（d），这组点位就是前代回代的结果x1 1.5 1 0.5T,（c）规格化后点位,u,u,u,u,u,以节点为收点的边只有一条(2，3)，修正发点的点位,以节点为收点的边只有一条(1，2)，修正发点的点位：,（d）回代后点位,版权所有,64,三、稀疏向量法,主要用来解决右端向量仅仅有少量非零元素对待求向量中个别元素感兴趣可用于满矩阵或稀疏矩阵,对方程：,A可经过三角分解：,则有：,求解过程成为： 1. 消去,2. 回代,版权所有,65,上述运算可以按行进行，也可按列进行。用稀疏向量法时，消去过程必须按列进行，回代过程必须按
29、行进行。在许多情况下，独立向量b是稀疏的，但待求x一般不稀疏。如果b是稀疏向量，则在消去过程中只用L中某几列元素，称为快速消去，简称FF。如果只求x中几个元素，则在回代过程中只用U中某几行元素，称为快速回代，简称FB,版权所有,66,例36 对如下方程求解，右端b为稀疏,首先讨论消去过程。由消去公式：当 为零时，所有与 有关的运算可以忽略。即下三角阵中第k列元素可以忽略不用。,重写分解因子表：,版权所有,67,对本例，消去过程如下,由于b1为0，故可以跳过L中第一列元素。消去从第二列开始，包括规格化和消去运算。,对第三列，由于上面B(2)中的第三个元素为0，可以跳过L中第三列元素，直接进入第四
30、列消去，此时，只需要规格化B(2)中第四个元素2。,版权所有,68,对本例回代过程。,回代按行进行如果只对x3感兴趣，则上三角阵U中，第一第二行元素有关运算可以免去。如果只对x2感兴趣，则上三角阵U中，第一行运算可以免去。而且，由于 为0，与U中第三行运算也可以免去。因此，只用上三角阵U中第二行元素进行回代即可。,结论：稀疏向量法的关键在于找出FF和FB所需要进行运算的L及U的有效子集。FF的有效子集与L和b的稀疏结构有关FB的有效子集与U和x的稀疏结构有关,版权所有,69,稀疏向量法的图论基础,道路树：是在有向因子图上，从每个节点发出的边中取收点号最小的边作为树边，这样得到的有向树。在由连通
31、的有向A图形成的有向因子图上，其道路树的根节点只有一个。点的路：是在道路树上该点沿道路树到树根所经过的路径，它是道路树的一个子集。点集的路集；是该点集中所有点的路的并集。,版权所有,70,定理一：在有向因子图上，前代运算只在稀疏独立矢量中非零元素点集的路集上进行。定理二；路集上任一点的前代运算必须在路集上比该点编号小且其道路经过该点的点的前代完成之后才能进行，而路集中分支点以上的几条路先做哪个没有关系。,稀疏向量法的图论基础续一,例如图中给出了点集， ，的路集。由定理二，必须在点， ，上的前代都做完后才能做点的前代。点是分支点。分支点以上几条路既可先做点、 、再做点， ，也可先做，后做 ，。点
32、也是分支点，先做或先做 ，都是可以的，但只有 ，的前代都做完后才能做点的前代。,版权所有,71,定理三：在有向因子图上，回代运算只在稀疏解矢量的待解元素的点集的路集上进行。定理四；任一点的回代运算都必须在该点的道路上比该点编号大的点的回代运算完成之后才能进行。而路集中分支点以上几条路先沿哪条路做回代没有关系。,稀疏向量法的图论基础续二,例如图中要求点的位，回代运算应在点的路集，即沿一一一进行。若要求点集(， ，三个点的位，就应在如前图d所示的路集上进行回代。,例如图中点的回代必须在点的道路上比点编号大的点 ， ， 的回代运算完成之后才能进行。由于小号点的回代不会影响大号点的点位，所以点的回代做
33、完之后，先做一的回代或先做一一的回代都是可以的。,版权所有,72,由以上分析可见，要确定稀疏矢量的前代回代路径，只需确定稀疏矢量非零元素点集的路集。根据道路树的定义，某点的道路是由该点发出边中收点号最小的点确定的，这在因子表检索信息中就是上三角中该行第一个非零元素的列号，这很容易由搜索上三角每行第一个非零元素的列号来确定这个点的道路。对多个节点组成的点集，在道路树上，只需将点集中每一个点沿树达根所经过的道路的并集组成该点集的路集。,版权所有,73,稀疏向量法的因子化路径（道路集）,因子化路径是进行FF时用到的L的列数顺序表，对FF而言采用前向顺序，对FB而言采用逆向顺序。当向量I中只有一个非零
34、元素时，称为单元素向量，设其点号为k 。用下列算法求因子化路径。（1）令k为路径中第一个点号。（2）寻找L阵的k列中（或U阵的k 行中）最小的非零元素的点号，将此点号置入k，并列入路径中。（3）如果kn，结束，否则转到（2）。一般稀疏向量为单元素向量之和，其路径为各单元素向量路径的并集。,版权所有,74,稀疏向量法的因子化路径（道路集）,如果将三角检索的存储格式应用于对称矩阵的因子表，即只存上三角部分的信息，则找某节点A的道路可用下面流程实现：,(322)式中，P是节点p的路集，IU存上三角矩阵因子表每行第一个非零元素的首地址，JU是非零元素的列号，root是有向因子图的根节点。,（322）,
35、版权所有,75,例37：求图示网络的因子化路径,因子表结构图,因子化路径：k=1时： 12712131415k=5时： 511131415k=6时： 691012131415当稀疏向量为非单元素向量时：如当k=1 及k=5时： 12712511131415,版权所有,76,此例题的全部因子化路径图,如果希望求得当已知b5时（其它为0）的x1则有：按以下因子化路径进行消去： 511131415按以下因子化路径进行回代： 15141312721以上求解只涉及5列下三角元素和7行上三角元素，计算效率明显提高。应用稀疏向量法时，上述因子化路径预先求出。,版权所有,77,例38：求图示网络的因子化路径,
36、因子表结构图,因子化路径：对b1： 17101112对b4： 47101112对b7： 7101112 对b8 x8 ： 8 9 101112对x3， 3 6 9101112根据并集，可得到路径树,设b中非零元b1,b4,b7,b8，而感兴趣解为x3 , x8。,版权所有,78,根据并集，得到路径树：,对b中非零元b1,b4,b7,b8，而感兴趣解为x3 , x8。,在路径树中，点7、9、10被称为分支点（junction）,前代运算（DkLk)是从小编号点到大编号点，按递增顺序依次进行。在分支点以上的几条支路中，先做哪个没有关系。,以下前代运算路径均可：1478910111289417101
37、11281497101112,版权所有,79,对b中非零元b1,b4,b7,b8，而感兴趣解为x3 , x8。,回代运算是从大编号点到小编号点反向进行。在分支点以后的几条支路中，先做哪条没有关系。,为求x3，x8以下回代运算路径均可：12111098631211109638,版权所有,80,提高稀疏矢量法计算效率的优化编号方法（MD-ML）,Minmum DegreeMinimum Length，MDML算法在因子道路树上，每一个节点都处于一定的深度，例如节点i所处的深度是L(i)。在用Tinney的最小度(Minimum Degree，MD)算法进行编号时，如果有几个节点具有同样的最小出线度，在选择优先编号的节点时，MDML算法在这些节点中选择具有最小深度的节点优先编号。还有其它方法,版权所有,81,结 束,待续,