三、稀疏技术及稀疏向量三、稀疏技术及稀疏向量法法东南大学电气工程学院东南大学电气工程学院主要内容主要内容主要内容主要内容n因子表应用因子表应用n因子表元素n因子表求解n稀疏因子表n稀疏技术稀疏技术n概述n稀疏技术n稀疏存储n稀疏矩阵因子分解n n利用稀疏矩阵因子表求解稀疏线性方程组利用稀疏矩阵因子表求解稀疏线性方程组n n稀疏技术的图论描述稀疏技术的图论描述n术语及定义n因子分解的图论描述n前代回代的图论描述n稀疏向量法稀疏向量法版权所有东南大学电气工程学院东南大学电气工程学院回顾几个结论：n以高斯消元法逐列消元，对应于以消去节点法逐个消去节点n消元过程中的注入元，在物理意义上对应于由于消去某节点而出现新的互联支路导纳。n就形成因子表而言，三角分解法与高斯消元法完全等效，而以高斯消元法逐列消元又对应于以消去节点法逐个消去节点，因此可通过考察消去节点以考察因子表的形成n基于如上关系，高斯消元后如出现注入元，该注入元也将出现在三角分解后所得的上、下三角矩阵中，并将出现在所形成的因子表中。n因子表中是否会出现注入元因子表中是否会出现注入元等价于等价于网络消去节点后是否会出现新的网络消去节点后是否会出现新的互联支路互联支路。版权所有东南大学电气工程学院东南大学电气工程学院一、一、 因子表应用因子表应用n网络方程需要求解多次，每次只是改变方程右端的常数向量，因此，考虑采用因子表n因子矩阵的元素以适当的形式贮存起来以备反复应用。 n因子表的形成有多种方式，一般有n按行消元，逐行规格化的高斯消去n与上面高斯消去法对应的CROUT分解nLDU分解版权所有东南大学电气工程学院东南大学电气工程学院作LDU分解时，把各因子矩阵的元素排列成因子表： n对对称矩阵的因子矩阵L和U互为转置矩阵，在因子表中保留上三角部分（或下三角部分）n对角线位置则存放矩阵D的对应元素的倒数，便于计算版权所有东南大学电气工程学院东南大学电气工程学院（226）n因子矩阵的元素表达式如下版权所有东南大学电气工程学院东南大学电气工程学院利用因子表(LDU分解)求解分两步：n前代（消元）：（i=n,n-1,.,1 ) (32)（31） 回代：n或者前代（消元）：（33） 回代：（34）（35）版权所有东南大学电气工程学院东南大学电气工程学院右端的常数向量取为： 解：解：形成LDU分解后因子表如下： 例例3 31 1 用因子表求解方程组AX=B。 版权所有东南大学电气工程学院东南大学电气工程学院n先做消元运算n再做回代版权所有东南大学电气工程学院东南大学电气工程学院n做规格化及消元运算1.2.3.版权所有东南大学电气工程学院东南大学电气工程学院n做回代运算1.2.3.版权所有东南大学电气工程学院东南大学电气工程学院稀疏因子表的利用 如对原始方程，令： 得到同解方程: 相应因子表（LDU）是稀疏的: 相当于优化编号版权所有东南大学电气工程学院东南大学电气工程学院求解： LDU因子表: 以上完成全部消去 以上完成全部回代版权所有东南大学电气工程学院东南大学电气工程学院从例子中看出n当线性方程组的稀疏性得到充分应用时n形成因子表过程中减少了计算量n更重要的是减少了求解方程组时前代和回代的计算量版权所有东南大学电气工程学院东南大学电气工程学院n电力网络特点决定了电网计算中的矩阵及矢量是稀疏的 n对mn阶矩阵A的稀疏度定义：对稀疏矩阵二、稀疏技术二、稀疏技术1 1 1 1、概述、概述、概述、概述 n如对节点导纳矩阵，如果每个节点的出线度是，则则对对N维导纳维导纳阵 版权所有东南大学电气工程学院东南大学电气工程学院n稀疏技术 针对稀疏矩阵及稀疏矢量，进行排零存储及排零计算nW. F. Tinney 版权所有东南大学电气工程学院东南大学电气工程学院2. 2. 2. 2. 稀疏技术稀疏技术稀疏技术稀疏技术n对mn阶稀疏矩阵A，其非零元素共有个，令aij是A中第i行第j列非零元素。可以定义三个数组，按下面的存储格式存储矩阵A中非零元素的信息：nVA存储A中非零元素aij的值，共 个nIA存储A中非零元素aij的行指标i，共 个 nJA存储A中非零元素aij的列指标j，共 个 2.1.1 散居格式2.1 2.1 稀疏存储稀疏存储稀疏存储稀疏存储n总共需要3 个存储单元n优点：A中非零元在数组中的位置可任意排列，修改灵活。n缺点：其存储顺序无一定规律，检索起来不方便。最差的可能性要在整个数组中查找一遍。版权所有东南大学电气工程学院东南大学电气工程学院n如查找第i行的非零元素n在VA中取出从kIA(i)到IA(i1)1共IA(i1)IA(i)个非零元就是A中第i行的全部非零元n非零元的值是VA(k)，列号JA(k)2.1.2 按行（列）存储格式n按行(列)顺序依次存储A中的非零元，同一行(列)元素依次排在一起。n以按行为例，其存储格式是：nVA按行存储矩阵A中非零元aij ，共 个；nJA按行存储矩阵A中非零元的列号，共 个；nIA记录A中每行第一个非零元素在VA中的位置，共m个。n如查找第i行第j列的元素aij在VA中的位置n对k从IA(i)到IA(i1)1，判断列号JA(k)是否等于j，如等， VA(k) 就是 要的非零元aij版权所有东南大学电气工程学院东南大学电气工程学院nU存A的上三角部分的非零元的值，按行依次存储nJU存A的上三角部分的非零元的列号nIU存A中上三角部分每行第一个非零元在U中的位置(首地址)nL按列存储A中下三角非零元素的值nIL按列存储A中下三角非零元素的行号nJL存储A的下三角部分每列第一个非零元在L中的位置(首地址)nD存储A的对角元素的值，其检索下标不需要存储2.1.3 三角检索存储格式n特别适用于稀疏矩阵的三角分解。有几种不同的存储格式。n以按行存储A的上三角部分非零元按列存A的下三角部分非零元存储格式为例来说明。令A是n n阶方阵：版权所有东南大学电气工程学院东南大学电气工程学院nU存A的上三角部分的非零元的值，按行依次存储nJU存A的上三角部分的非零元的列号nIU存A中上三角部分每行第一个非零元在U中的位置(首地址)nL按列存储A中下三角非零元素的值nIL按列存储A中下三角非零元素的行号nJL存储A的下三角部分每列第一个非零元在L中的位置(首地址)nD存储A的对角元素的值，其检索下标不需要存储三角检索存储格式示例版权所有东南大学电气工程学院东南大学电气工程学院nIU（3）为4，表明A矩阵上三角部分第3行的第1个非零元如果有的话应在U的第4个位置，而U表中第4个位置没有非零元素，为了检索方便，IU(3)仍应赋值4。n有了IU表即可知道A的上三角部分第i行的非零元的数目n如果要查找A的上三角第i行所有非零元素，只要扫描A从IU(i)到IU(i+1)1即可，JU(k)指出了该元素的列号，U(k)是该非零元素的值。n对于按列存储的格式进行查找的情况类同。IUJUU版权所有东南大学电气工程学院东南大学电气工程学院n UnJUnIUn LnILnJLn D三角检索存储n 占用的存储单元分析:n对于数组U,L,D共需 个存储单元，此例为10。n对JU，IL共需n个存储单元，此例中为6；n对IU，JL，共需2n个存储单元，此例为8n总计需占用2 +n个存储单元。n 是矩阵A中的非零元素的数目。版权所有东南大学电气工程学院东南大学电气工程学院n三角检索存储格式在矩阵A的稀疏结构已确定的情况下使用是十分方便的。n但在计算过程中，如果A的稀疏结构发生了变化，即其中的非零元素的分布位置发生变化，相应的检索信息也要随着变化，很不方便。n有两种办法处理n事先估计注入，符号分解。n链表格式版权所有东南大学电气工程学院东南大学电气工程学院2.1.4 链表存储格式n以按行存储的格式为例来说明。这时除了需要按行存储格式中的三个数组外还需要增加下列数组：nLINK下一个非零元素在VA中的位置，对每行最后一个非零元素，该值置为0。nNA每行非零元素的个数。版权所有东南大学电气工程学院东南大学电气工程学院n当新增加一个非零元素时，可把它排在最后，并根据该非零元素在该行中的位置的不同来修改其相邻元素的LINK值。n例如，新增a13，把a13排在第11个位置，把a12的LINK值由3改为11， a13本身的LINK值置为3，NA(1)增加1，变为4。链表存储格式n重现第i行的所有元素：n所以，只要用IA把该行第一个非零元素找到，就可以按LINK的指示找下一个非零元素。n直到把该行中所有非零元素都找出来为止。当找到第i行最后一个非零元素时LINK(A)0，这时do循环结束。版权所有东南大学电气工程学院东南大学电气工程学院2.2 2.2 2.2 2.2 稀疏矩阵因子分解稀疏矩阵因子分解稀疏矩阵因子分解稀疏矩阵因子分解n对nn阶矩阵A，分解成下三角矩阵L和单位上三角矩阵U两者的乘积，即ALU。n常规计算流程如下：n在第p步计算中，规格化只有apj0计算才有效。在消去运算中，只有aip以及apj都不为零才有效。判判apj0则执则执行行判判aip及apj 0则执行则执行版权所有东南大学电气工程学院东南大学电气工程学院n对稀疏存储格式应按所采用的存储格式的要求进行计算。n例如，当假定对矩阵A进行了符号分解，当用三角检索存储格式时可用下面计算流程。注意稀疏存储格式时的因子分解只用非零元素U(k)，L(l)计算版权所有东南大学电气工程学院东南大学电气工程学院n对不同的分解方法有不同的计算流程。但主要是避免无效运算。版权所有东南大学电气工程学院东南大学电气工程学院2.3 2.3 2.3 2.3 利用稀疏矩阵因子表求解稀疏线性方程组利用稀疏矩阵因子表求解稀疏线性方程组利用稀疏矩阵因子表求解稀疏线性方程组利用稀疏矩阵因子表求解稀疏线性方程组n对Ax=b ，假定分解成ALDU。则有：nLz=b 前代过程nDy=znUx=y 回代过程n如果b是稀疏向量，则仅有L的列子集参与（33）及（34）前代运算，而不是L的所有列参与，这种算法被称之为快速前代。n对于解向量一般不稀疏，但如果只对其中的某些元素感兴趣，只求解部分元素，仅有U的行子集参与（35）回代运算，而不是U的所有行参与。这种算法就是快速回代。（36）（37）（38）版权所有东南大学电气工程学院东南大学电气工程学院1. 前代过程前代过程n如果将L分解成一个单位矩阵和一个严格下三角矩阵 的和，则Lz=b式可改写成:n式中，li 是 的第i个列矢量（39）版权所有东南大学电气工程学院东南大学电气工程学院结构如下：n矢量li的元素从第1个到第i个都是零，所以式中右边的zi对左边矢量z中前i个元素没有贡献，只会对i1到n的有影响。（39a）版权所有东南大学电气工程学院东南大学电气工程学院n即z中的第i个元素zi ，只会对z中下标大于i的元素有影响。换句话说， z中某元素只会受z中比该元素下标小的元素影响。因此，前代运算应从小号到大号小号到大号依次进行。计算流程如下：n还要考虑li的稀疏性，所以对lji为0的不计算。n对外循环中，zi 为0则该次循环不计算。（39b）版权所有东南大学电气工程学院东南大学电气工程学院n考虑了矩阵和矢量的稀疏性，重写前代的计算流程：n实际应用中，并不需要去判断元素是否为零，而是按排零存储格式直接取出非零元来进行运算。（39c）版权所有东南大学电气工程学院东南大学电气工程学院n首先将独立b矢量送入zn依次对i=2,3,4，有例例32 求前代过程n对i=1，只有两个非零元l21和l52和，因此有版权所有东南大学电气工程学院东南大学电气工程学院n可见： (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的计算步也可省去。经过i4计算步后，最终的解z中也只有三个非零元素，即z2，z4，z5。这说明如果原来独立矢量是稀疏的，前代结束后，解矢量仍可能是稀疏的。到底哪些元素将由零元素变成非零元素，取决于 的稀疏结构，也取决于独立矢量b中非零元素的分布。版权所有东南大学电气工程学院东南大学电气工程学院n求解(37)式，只需做以下除法运算；n yizidii i1，n (310) dii是D的第i个对角元素。很明显，对于zi 0的除法运算可以省略。2. 除法运算除法运算版权所有东南大学电气工程学院东南大学电气工程学院n用(38)式求解x时，将U分解为一个单位矩阵和一个严格上三角矩阵，则(38)式可以写成:3. 回代运算回代运算（311）可以写成（312）版权所有东南大学电气工程学院东南大学电气工程学院 uj是严格上三角矩阵 的第j个列矢量。n对应上式的流程：n可见，矢量x中的元素下标大的可能影响下标小的，而不会影响下标大的。回代应从大号到小号依次进行。n(3-12)可写成（313）（313a）版权所有东南大学电气工程学院东南大学电气工程学院n考虑稀疏性的回代运算流程：S是x当中应当进行回代的元素的集合。n如果：x中只有少数元素是我们所需要的，其它元素不需要，例如某元素xk需要计算，(313a)式的回代的外环只需扫描到k十1即可，这是因为jk的回代对xk无贡献。（313b）版权所有东南大学电气工程学院东南大学电气工程学院n首先将y送入xnj=4，有例例33 回代过程nj=5，uj有三个非零元nj=3，u23和u13都是0，此步不做nj=2， x1 x1u12 x2版权所有东南大学电气工程学院东南大学电气工程学院n可见：nx中下标小的元素不会影响下标大的元素。例如x4不会影响x5， x3 x2 不会影响x4等等，所以回代运算应从后向前进行。n每步回代过程中，只取uj中非零元素和x矢量中相应元素进行乘法运算，不必考虑uj中的零元素和x中相应元素进行的运算。例如j5时，u35是零元素，不必考虑u35和x5的运算。n如果在最终的结果x中，我们只要用到其中一个元素x2，其它4个元素我们不需要，这时上面的计算步中有些可以省略。版权所有东南大学电气工程学院东南大学电气工程学院3. 3. 3. 3. 稀疏技术的图论描述稀疏技术的图论描述稀疏技术的图论描述稀疏技术的图论描述3.1 3.1 术语及定义术语及定义术语及定义术语及定义n对称矩阵A中的非零元素的分布可用一个网络图来描述。矩阵A的因子表矩阵D中的非零元素的分布也可以用一个网络图来描述。例如，矩阵A非零元素的分布是： 因子分解后U的非零元是：（314）（315）版权所有东南大学电气工程学院东南大学电气工程学院nA图：和矩阵A有相同拓扑结构的网络图。n有向A图：在给定的A图上，对于给定的节点编导，规定每条边的正方向都是由小号节点指向大号节点，这样形成的有向图。n赋权有向A图：在有向A图上，将A的非对角非零元素所对应的边称为互边，并将该边的权赋之以该非零元素的值。将A的对角元素用在有向A图上的接地边模拟，称之为自边，并赋之以该对角元素的值。这样得到的有向A图称之为赋权有向A图。版权所有东南大学电气工程学院东南大学电气工程学院n类似，可以用图描述因子表U。n因子图 有向因子图 赋权有向因子图n对对称矩阵A的图上因子分解就是要将赋权有向A图变成赋权有向因子图。n两者图的结构不同，后者互边的边数比前者多，而且两者的边权也不同。版权所有东南大学电气工程学院东南大学电气工程学院n以下图为例，对第p行规格化。3.2 3.2 因子分解的图论描述因子分解的图论描述因子分解的图论描述因子分解的图论描述3.2.1 规格化运算n这在赋权有向A图上，相当于对节点p发出的所有互边的边权加以修正。n新的边权等于原边权除以节点p的自边边权。节点p发出的互边边权发生了变化，边数并未增加。（316）版权所有东南大学电气工程学院东南大学电气工程学院n取第p行第p列为轴线。第p步的消去运算实际上是要对处于轴线上的非零元素所在的行列相交叉的位置上的元素进行消去运算。n在图中用划表示。图中划O表示消去前已经存在非零元素。n需要进行消去运算的元素中3个是对角元素，6个是非对角元素。如果只保留上三角矩阵，只需对3个对角元素和3个非对角元素进行消去运算。3.2 3.2 因子分解的图论描述因子分解的图论描述因子分解的图论描述因子分解的图论描述3.2.2 消去运算版权所有东南大学电气工程学院东南大学电气工程学院n对对角元素消去运算的修正公式是 aii=aiiaipapi pi, i=j,k,l 由于在消去前已经对api进行过规格化，而上式中aip还没有规格化，有aip=apiapp， 所以当使用上三角元素计算时，有： aii=aiiapi2 app pi, i=j,k,l（317）n在赋权有向A图上，就是对节点p发出的边的收点j，k，l上的自边边权进行修正，边权减少api2 app 版权所有东南大学电气工程学院东南大学电气工程学院n对上三角元素消去运算，有三个元素ajk，akl，ajl，公式是: aim=aimaipapm pim, i,m从j,k,l取值 由于仅使用上三角元素计算, 有aip=apiapp，所以有： aim=aimapiapmapp pii，说明边是由小号节点指向大号节点。2. uij0，表示是上三角中的非零元素。该流程可以与赋权有向图联系。版权所有东南大学电气工程学院东南大学电气工程学院n如果把zi定义为赋权有向因子图上的点位，用ei表示，赋权有向因子图上的互边边权是uij，则上面程序可写成：3.3.1 前代运算n前代过程在赋权有向因子图上用点位变化描述：n每个节点点位赋值独立矢量b中相应值。n在图上按节点i由小到大顺序修正该节点i发出对端节点j的点位（319）表示uij是从节点i发出的边的边权。隐含着 uij 0版权所有东南大学电气工程学院东南大学电气工程学院n参考(310)式，将前代结束后节点i的点位ei除以赋权有向因子图上节点i的自边边权，即3.3.2 规格化运算上式即是规格化结果（320）版权所有东南大学电气工程学院东南大学电气工程学院n参考(3l3a)式。令赋权有向因子图上的点位已经是经过前代和规格化后的值。在此图上节点号j从n开始，由大到小，对所有指向j的边其发端节点i的点位进行修正，修正公式是：3.3.3 回代运算（321）n当所有节点的点位都修正完后，回代过程结束。n也可以换一种说法，将赋权有向因子图上所有边反向然后按节点号从大到小顺序象前代计算过程一样按箭头方向去修正点位。版权所有东南大学电气工程学院东南大学电气工程学院总结1图上前代回代计算步骤如下：n将独立矢量b的非零元素赋值为赋权有向因子图上的点位；n扫描i从1到n1。用(319)式修正节点i发出的边的对端节点j的点位。n对所有节点用(320)式对点位规格化。n扫描j从n到2。对所有指向节点j的边的发端节点i，用(321)式修正其点位。n如果图上有条互边，n条自边。则前代回代最多进行次乘法，规格化最多要进行n次除法运算。所以整个前代回代最多要进行2n次乘除运算。版权所有东南大学电气工程学院东南大学电气工程学院总结2图上前代回代中有关问题：n在前代过程中，某节点i的点位是零时，该步前代计算可以省略，即(319)式只需对ei0的节点进行计算，但应注意前代开始前点位是零的节点在前代进行过程中也可能会变成非零。n(320)式的规格化计算也只在点位不等于零的节点上进行。n在回代过程中，某点i的点位只受到由该点i发出的边的收点j的点位的影响，这些收点j的点位，又受到它们各自发出的边的收点的点位的影响，以此类推。n所以，从某节点i沿图上箭头方向搜索直到根节点n，就可以找到影响该节点i的点位的所有节点。就研究节点i的点位而言，其它节点的回代可以省略。n如果解矢量x中我们只需要少数几个元素，我们则可以用这一原理在图上找到影响这几个元素的节点，回代计算只对这些节点的点位进行。版权所有东南大学电气工程学院东南大学电气工程学院例例35 图上前代回代运算（a）赋权有向因子图和独立矢量的点位n前代过程 (对独立矢量b=0 1 0 0T)n按节点号从小到大顺序搜索点位不是零的节点进行运算。节点点位为零不用计算n对节点进行前代运算。节点发出两条边，(2，3)和(2，4)。利用(319)式则：n再做节点，它只发出一条边(3，4)，则：n前代后点位如图（b）dduuuud（b）前代后点位版权所有东南大学电气工程学院东南大学电气工程学院n规格化过程n点的点位是零，只需利用(320)式对点， 和规格化。n规格化后点位如图（c）ddd（b）前代后点位（c）规格化后点位uuuuu版权所有东南大学电气工程学院东南大学电气工程学院n回代过程n按节点号由大到小做。以节点为收点的边有三条：(3，4)，(2，4)，(1，4)。用(321)式修正指向节点的边的发点的点位：n最后得到点位图（d），这组点位就是前代回代的结果x1 1.5 1 0.5T（c）规格化后点位uuuuun以节点为收点的边只有一条(2，3)，修正发点的点位n以节点为收点的边只有一条(1，2)，修正发点的点位：（d）回代后点位版权所有东南大学电气工程学院东南大学电气工程学院三、稀疏向量法三、稀疏向量法n主要用来解决n右端向量仅仅有少量非零元素n对待求向量中个别元素感兴趣n可用于满矩阵或稀疏矩阵对方程：A可经过三角分解：则有：求解过程成为： 1. 消去2. 回代版权所有东南大学电气工程学院东南大学电气工程学院n上述运算可以按行进行，也可按列进行。n用稀疏向量法时，消去过程必须按列进行，回代过程必须按行进行。n在许多情况下，独立向量b是稀疏的，但待求x一般不稀疏。n如果b是稀疏向量，则在消去过程中只用L中某几列元素，称为快速消去，简称FF。n如果只求x中几个元素，则在回代过程中只用U中某几行元素，称为快速回代，简称FB版权所有东南大学电气工程学院东南大学电气工程学院例例3 36 6 对如下方程求解，右端b为稀疏n首先讨论消去过程。由消去公式：n当 为零时，所有与 有关的运算可以忽略。即下三角阵中第k列元素可以忽略不用。重写分解因子表：版权所有东南大学电气工程学院东南大学电气工程学院对本例，消去过程如下n由于b1为0，故可以跳过L中第一列元素。n消去从第二列开始，包括规格化和消去运算。n对第三列，由于上面B(2)中的第三个元素为0，可以跳过L中第三列元素，直接进入第四列消去，此时，只需要规格化B(2)中第四个元素2。版权所有东南大学电气工程学院东南大学电气工程学院对本例回代过程。n回代按行进行n如果只对x3感兴趣，则上三角阵U中，第一第二行元素有关运算可以免去。n如果只对x2感兴趣，则上三角阵U中，第一行运算可以免去。而且，由于 为0，与U中第三行运算也可以免去。因此，只用上三角阵U中第二行元素进行回代即可。n结论：n稀疏向量法的关键在于找出FF和FB所需要进行运算的L及U的有效子集。nFF的有效子集与L和b的稀疏结构有关nFB的有效子集与U和x的稀疏结构有关版权所有东南大学电气工程学院东南大学电气工程学院稀疏向量法的图论基础n道路树道路树：是在有向因子图上，从每个节点发出的边中取收点号最小的边作为树边，这样得到的有向树。在由连通的有向A图形成的有向因子图上，其道路树的根节点只有一个。n点的路点的路：是在道路树上该点沿道路树到树根所经过的路径，它是道路树的一个子集。n点集的路集点集的路集；是该点集中所有点的路的并集。版权所有东南大学电气工程学院东南大学电气工程学院n定理一：在有向因子图上，前代运算只在稀疏独立矢量中非零元素点集的路集上进行。n定理二；路集上任一点的前代运算必须在路集上比该点编号小且其道路经过该点的点的前代完成之后才能进行，而路集中分支点以上的几条路先做哪个没有关系。稀疏向量法的图论基础续一n例如图中给出了点集， ，的路集。由定理二，必须在点， ，上的前代都做完后才能做点的前代。点是分支点。分支点以上几条路既可先做点、 、再做点， ，也可先做，后做 ，。点也是分支点，先做或先做 ，都是可以的，但只有 ，的前代都做完后才能做点的前代。版权所有东南大学电气工程学院东南大学电气工程学院n定理三：在有向因子图上，回代运算只在稀疏解矢量的待解元素的点集的路集上进行。n定理四；任一点的回代运算都必须在该点的道路上比该点编号大的点的回代运算完成之后才能进行。而路集中分支点以上几条路先沿哪条路做回代没有关系。稀疏向量法的图论基础续二n例如图中要求点的位，回代运算应在点的路集，即沿一一一进行。若要求点集(， ，三个点的位，就应在如前图d所示的路集上进行回代。n例如图中点的回代必须在点的道路上比点编号大的点 ， ， 的回代运算完成之后才能进行。由于小号点的回代不会影响大号点的点位，所以点的回代做完之后，先做一的回代或先做一一的回代都是可以的。版权所有东南大学电气工程学院东南大学电气工程学院n由以上分析可见，要确定稀疏矢量的前代回代路径，只需确定稀疏矢量非零元素点集的路集。n根据道路树的定义，某点的道路是由该点发出边中收点号最小的点确定的，这在因子表检索信息中就是上三角中该行第一个非零元素的列号，这很容易由搜索上三角每行第一个非零元素的列号来确定这个点的道路。n对多个节点组成的点集，在道路树上，只需将点集中每一个点沿树达根所经过的道路的并集组成该点集的路集。版权所有东南大学电气工程学院东南大学电气工程学院稀疏向量法的因子化路径（道路集）n因子化路径是进行FF时用到的L的列数顺序表，对FF而言采用前向顺序，对FB而言采用逆向顺序。n当向量I中只有一个非零元素时，称为单元素向量，设其点号为k 。用下列算法求因子化路径。（1）令k为路径中第一个点号。（2）寻找L阵的k列中（或U阵的k 行中）最小的非零元素的点号，将此点号置入k，并列入路径中。（3）如果kn，结束，否则转到（2）。n一般稀疏向量为单元素向量之和，其路径为各单元素向量路径的并集。版权所有东南大学电气工程学院东南大学电气工程学院稀疏向量法的因子化路径（道路集）n如果将三角检索的存储格式应用于对称矩阵的因子表，即只存上三角部分的信息，则找某节点A的道路可用下面流程实现：n(322)式中，P是节点p的路集，IU存上三角矩阵因子表每行第一个非零元素的首地址，JU是非零元素的列号，root是有向因子图的根节点。（322）版权所有东南大学电气工程学院东南大学电气工程学院例例3 37 7：求图示网络的因子化路径因子表结构图12345678910 11 12 13 14 1512 34 5678910 1112 13 14 15 因子化路径：k=1时： 12712131415k=5时： 511131415k=6时： 691012131415当稀疏向量为非单元素向量时：如当k=1 及k=5时： 12712511131415版权所有东南大学电气工程学院东南大学电气工程学院此例题的全部因子化路径图n如果希望求得当已知b5时（其它为0）的x1则有：n按以下因子化路径进行消去： 511131415n按以下因子化路径进行回代： 15141312721n以上求解只涉及5列下三角元素和7行上三角元素，计算效率明显提高。n应用稀疏向量法时，上述因子化路径预先求出。版权所有东南大学电气工程学院东南大学电气工程学院例例3 38 8：求图示网络的因子化路径1 2 3 4 5 6 7 8 9 10 11 121 234567 89 10 11 12 因子表结构图因子化路径：对b1： 17101112对b4： 47101112对b7： 7101112 对b8 x8 ： 8 9 101112对x3， 3 6 9101112根据并集，可得到路径树设b中非零元b1,b4,b7,b8，而感兴趣解为x3 , x8。版权所有东南大学电气工程学院东南大学电气工程学院根据并集，得到路径树：对b中非零元b1,b4,b7,b8，而感兴趣解为x3 , x8。n在路径树中，点7、9、10被称为分支点（junction）n前代运算（DkLk)是从小编号点到大编号点，按递增顺序依次进行。在分支点以上的几条支路中，先做哪个没有关系。n以下前代运算路径均可：n14789101112n89417101112n81497101112版权所有东南大学电气工程学院东南大学电气工程学院对b中非零元b1,b4,b7,b8，而感兴趣解为x3 , x8。n回代运算是从大编号点到小编号点反向进行。在分支点以后的几条支路中，先做哪条没有关系。n为求x3，x8以下回代运算路径均可：n1211109863n1211109638版权所有东南大学电气工程学院东南大学电气工程学院提高稀疏矢量法计算效率的优化编号方法（MD-ML）nMinmum DegreeMinimum Length，MDML算法n在因子道路树上，每一个节点都处于一定的深度，例如节点i所处的深度是L(i)。在用Tinney的最小度(Minimum Degree，MD)算法进行编号时，如果有几个节点具有同样的最小出线度，在选择优先编号的节点时，MDML算法在这些节点中选择具有最小深度的节点优先编号。n还有其它方法版权所有东南大学电气工程学院东南大学电气工程学院结 束n待续版权所有结束结束