三、稀疏技术及稀疏向量法

东南大学电气工程学院©版权所有三稀疏技术及稀疏向量法东南大学电气工程学院©版权所有主要内容因子表应用因子表元素因子表求解稀疏因子表稀疏技术概述稀疏技术稀疏存储稀疏矩阵因子分解利用稀疏矩阵因子表求解稀疏线性方程组稀疏技术的图论描述术语及定义因子分解的图论描述前代回代的图论描述稀疏向量法东南大学电气工程学院©版权所有回顾几个结论：以高斯消元法逐列消元，对应于以消去节点法逐个消去节点消元过程中的注入元，在物理意义上对应于由于消去某节点而出现新的互联支路导纳。就形成因子表而言，三角分解法与高斯消元法完全等效，而以高斯消元法逐列消元又对应于以消去节点法逐个消去节点，因此可通过考察消去节点以考察因子表的形成基于如上关系，高斯消元后如出现注入元，该注入元也将出现在三角分解后所得的上、下三角矩阵中，并将出现在所形成的因子表中。因子表中是否会出现注入元等价于网络消去节点后是否会出现新的互联支路。东南大学电气工程学院©版权所有一、因子表应用网络方程需要求解多次，每次只是改变方程右端的常数向量，因此，考虑采用因子表因子矩阵的元素以适当的形式贮存起来以备反复应用。因子表的形成有多种方式，一般有按行消元，逐行规格化的高斯消去与上面高斯消去法对应的CROUT分解LDU分解东南大学电气工程学院©版权所有作LDU分解时，把各因子矩阵的元素排列成因子表：对对称矩阵的因子矩阵L和U互为转置矩阵，在因子表中保留上三角部分（或下三角部分）对角线位置则存放矩阵D的对应元素的倒数，便于计算111213111222323132333123nnnnnnnnduuulduulldullld东南大学电气工程学院©版权所有11iiiiiikkikkkdalud(1,2,,)in11()/iijijikkjkkiikualudd1,2,,11,,injin11()/jijijikkjkkjjklaludd2,3,,1,2,,1injnij（2－26）因子矩阵的元素表达式如下东南大学电气工程学院©版权所有利用因子表(LDU分解)求解分两步：前代（消元）：1niijjjiixfux（i=n,n-1,...,1)(3－2)11()/iiiijjjjiijfbldfd(1,2,,)in（3－1）回代：或者前代（消元）：()nnnxb()(1)/iiiiiibbd（3－3）回代：()(1)()(1,,)kkkikkkiikbbldbikn（3－4）（3－5）1()niijjjiiixbux东南大学电气工程学院©版权所有右端的常数向量取为：解：形成LDU分解后因子表如下：111213212223313233231371542aaaAaaaaaa12135TB例3－1用因子表求解方程组AX=B。1112132122233132331/1/23/21/21/1.52/511/2.54.61/12duuldulld东南大学电气工程学院©版权所有先做消元运算111122211112233311113222233/1/262()/(1.526)2551()/(2.526(4.62))422151123fbdfbldfdfbldfldfd再做回代33222331112213342(14)2316(2)(4)122xfxfuxxfuxux1niijjjiixfux11()/iiiijjjjiijfbldfd1112132122233132331/1/23/21/21/1.52/511/2.54.61/12duuldulld东南大学电气工程学院©版权所有(1)1111(1)(1)2221111(1)(1)3331111T(1)/121/26131.526552.52625B=6525bbdbbldbbbldb首先规格化用下三角第一列元素：故有()nnnxb()(1)/iiiiiibbd()(1)()kkkikkkiikbbldb1()niijjjiiixbux做规格化及消元运算1112132122233132331/1/23/21/21/1.52/511/2.54.61/12duuldulld(2)(1)2222(2)1(2)3332222T(2)/52/52525(4.62)482B=6248bbdbbldb（）规格化用因子表下三角第二列元素：故有(3)(2)3333T(3)1/48412B=624bbd规格化故有1.2.3.东南大学电气工程学院©版权所有()nnnxb1()niijjjiiixbux做回代运算1112132122233132331/1/23/21/21/1.52/511/2.54.61/12duuldulld222332(14)2xbux(2)(3)334xb1.2.3.T(3)B=6241112213331624122xbuxux(1)东南大学电气工程学院©版权所有稀疏因子表的利用如对原始方程，令：1234121314252322xxxxxxxxxx得到同解方程:1424341234223225yyyyyyyyyy14223341,,,xyxyxyxy1001010200111215相应因子表（LDU）是稀疏的:★相当于优化编号东南大学电气工程学院©版权所有求解：1001010200111215LDU因子表:(1)11112131(1)(1)22211112(1)(1)33311113(1)(1)4441111T(1)/2/123251123B=2323bbdllbbldbbbbldbbbbldb首先规格化用下三角第一列元素,,为零，以下计算可免：只需做：故有(2)(1)222232(2)1(2)4442222T(2)/3/133(213)3B=2323bbdlbbldb（）规格化用因子表下三角第二列元素,但为零，不算故有－(3)23333(3)(2)(3)4443333T(3)/2/123125B=2325bbdbbldb（）规格化用下三角第三列元素故有(4)(3)4444T(4)/5/51B=232bbd规格化有1T[2325]B以上完成全部消去(4)44121323(3)33344(2)22244(1)11144=10211132112111ybuuuybuyybuyybuy注意、、为以上完成全部回代东南大学电气工程学院©版权所有从例子中看出当线性方程组的稀疏性得到充分应用时形成因子表过程中减少了计算量更重要的是减少了求解方程组时前代和回代的计算量东南大学电气工程学院©版权所有电力网络特点决定了电网计算中的矩阵及矢量是稀疏的对m×n阶矩阵A的稀疏度定义：100%mnmn对稀疏矩阵二、稀疏技术1、概述如对节点导纳矩阵，如果每个节点的出线度是α，则对N维导纳阵1100%N东南大学电气工程学院©版权所有稀疏技术针对稀疏矩阵及稀疏矢量，进行排零存储及排零计算W.F.Tinney东南大学电气工程学院©版权所有2.稀疏技术对m×n阶稀疏矩阵A，其非零元素共有个，令aij是A中第i行第j列非零元素。可以定义三个数组，按下面的存储格式存储矩阵A中非零元素的信息：VA——存储A中非零元素aij的值，共个IA——存储A中非零元素aij的行指标i，共个JA——存储A中非零元素aij的列指标j，共个2.1.1散居格式2.1稀疏存储总共需要3个存储单元优点：A中非零元在数组中的位置可任意排列，修改灵活。缺点：其存储顺序无一定规律，检索起来不方便。最差的可能性要在整个数组中查找一遍。东南大学电气工程学院©版权所有如查找第i行的非零元素在VA中取出从k＝IA(i)到IA(i＋1)－1共IA(i＋1)－IA(i)个非零元就是A中第i行的全部非零元非零元的值是VA(k)，列号JA(k)2.1.2按行（列）存储格式按行(列)顺序依次存储A中的非零元，同一行(列)元素依次排在一起。以按行为例，其存储格式是：VA——按行存储矩阵A中非零元aij，共个；JA——按行存储矩阵A中非零元的列号，共个；IA——记录A中每行第一个非零元素在VA中的位置，共m个。如查找第i行第j列的元素aij在VA中的位置对k从IA(i)到IA(i＋1)－1，判断列号JA(k)是否等于j，如等，VA(k)就是要的非零元aij东南大学电气工程学院©版权所有U——存A的上三角部分的非零元的值，按行依次存储JU——存A的上三角部分的非零元的列号IU——存A中上三角部分每行第一个非零元在U中的位置(首地址)L——按列存储A中下三角非零元素的值IL——按列存储A中下三角非零元素的行号JL——存储A的下三角部分每列第一个非零元在L中的位置(首地址)D——存储A的对角元素的值，其检索下标不需要存储2.1.3三角检索存储格式特别适用于稀疏矩阵的三角分解。有几种不同的存储格式。以按行存储A的上三角部分非零元．按列存A的下三角部分非零元存储格式为例来说明。令A是n×n阶方阵：东南大学电气工程学院©版权所有U—存A的上三角部分的非零元的值，按行依次存储JU—存A的上三角部分的非零元的列号IU—存A中上三角部分每行第一个非零元在U中的位置(首地址)L—按列存储A中下三角非零元素的值IL—按列存储A中下三角非零元素的行号JL—存储A的下三角部分每列第一个非零元在L中的位置(首地址)D—存储A的对角元素的值，其检索下标不需要存储三角检索存储格式示例11121421222333424344aaaaaaAaaaa1234121423aaa1344243214243aaa24411223344aaaa东南大学电气工程学院©版权所有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)是该非零元素的值。对于按列存储的格式进行查找的情况类同。11121421222333424344aaaaaaAaaaa1344IUJU121423aaa243U东南大学电气工程学院©版权所有U—JU—IU—L—IL—JL—D—三角检索存储11121421222333424344aaaaaaAaaaa1234121423aaa1344243214243aaa24411223344aaaa占用的存储单元分析:对于数组U,L,D共需个存储单元，此例为10。对JU，IL共需－n个存储单元，此例中为6；对IU，JL，共需2n个存储单元，此例为8总计需占用2+n个存储单元。是矩阵A中的非零元素的数目。东南大学电气工程学院©版权所有三角检索存储格式在矩阵A的稀疏结构已确定的情况下使用是十分方便的。但在计算过程中，如果A的稀疏结构发生了变化，即其中的非零元素的分布位置发生变化，相应的检索信息也要随着变化，很不方便。