稀疏技术

null 潮流计算中的稀疏技术 潮流计算中的稀疏技术概述概述线性方程组的求解方法有：直接法：高斯消去法、三角分解法 迭代法 矩阵求逆法 电力系统中常见的大型线性方程组的系数矩阵十分稀疏，直接法解法的计算速度很快。与迭代法相比，没有收敛性问题。概述概述矩阵的稀疏度为矩阵中的零元素与矩阵总元素之比 电力网络特点决定了电网的导纳矩阵是稀疏的 例如：对于节点数为10、100、1000的网络，节点导纳矩阵的稀疏度分别为： 50%—60%，95%—96%，99.5%—99.6%修正方程式中的雅克比矩阵与导纳矩阵有同样的结构，也必将高度稀疏 稀疏技术稀疏技术 所谓稀疏技术，是指选择算法和编制程序时，尽可能避免存储稀疏矩阵中的零元素和避免对这些零元素进行运算的技术。具体而言，包括以下几方面：稀疏存储:对于稀疏矩阵只存储其非零元素 采用按行消元的方式进行消元。 网络节点编号优化技术 因子技术 null对m×n阶稀疏矩阵A，其非零元素共有个，令aij是A中第i行第j列非零元素。可以定义三个数组，按下面的存储格式存储矩阵A中非零元素的信息： VA——存储A中非零元素aij的值，共 个 IA——存储A中非零元素aij的行指标i，共 个 JA——存储A中非零元素aij的列指标j，共 个 1.1 散居格式1 稀疏存储总共需要3 个存储单元 优点：A中非零元在数组中的位置可任意排列，修改灵活。 缺点：其存储顺序无一定规律，检索起来不方便。最差的可能性要在整个数组中查找一遍。null如查找第i行的非零元素 在VA中取出从k＝IA(i)到IA(i＋1)－1共IA(i＋1)－IA(i)个非零元就是A中第i行的全部非零元 非零元的值是VA(k)，列号JA(k) 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) 就是 要的非零元aijnullU——存A的上三角部分的非零元的值，按行依次存储 JU——存A的上三角部分的非零元的列号 IU——存A中上三角部分每行第一个非零元在U中的位置(首地址) L——按列存储A中下三角非零元素的值 IL——按列存储A中下三角非零元素的行号 JL——存储A的下三角部分每列第一个非零元在L中的位置(首地址) D——存储A的对角元素的值，其检索下标不需要存储1.3 三角检索存储格式特别适用于稀疏矩阵的三角分解。有几种不同的存储格式。 以按行存储A的上三角部分非零元．按列存A的下三角部分非零元存储格式为例来。令A是n ×n阶方阵：nullU—存A的上三角部分的非零元的值，按行依次存储 JU—存A的上三角部分的非零元的列号 IU—存A中上三角部分每行第一个非零元在U中的位置(首地址) L—按列存储A中下三角非零元素的值 IL—按列存储A中下三角非零元素的行号 JL—存储A的下三角部分每列第一个非零元在L中的位置(首地址) D—存储A的对角元素的值，其检索下标不需要存储三角检索存储格式示例nullIU（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)是该非零元素的值。 对于按列存储的格式进行查找的情况类同。IUJUUnull U— JU— IU— L— IL— JL— D—三角检索存储 占用的存储单元: 对于数组U,L,D共需 个存储单元，此例为10。 对JU，IL共需－n个存储单元，此例中为6； 对IU，JL，共需2n个存储单元，此例为8 总计需占用2 +n个存储单元。  是矩阵A中的非零元素的数目。null三角检索存储格式在矩阵A的稀疏结构已确定的情况下使用是十分方便的。 但在计算过程中，如果A的稀疏结构发生了变化，即其中的非零元素的分布位置发生变化，相应的检索信息也要随着变化，很不方便。 有两种办法处理 事先估计注入，符号分解。 链表格式null1.4 链表存储格式以按行存储的格式为例来说明。这时除了需要按行存储格式中的三个数组外还需要增加下列数组： LINK——下一个非零元素在VA中的位置，对每行最后一个非零元素，该值置为0。 NA——每行非零元素的个数。null当新增加一个非零元素时，可把它排在最后，并根据该非零元素在该行中的位置的不同来修改其相邻元素的LINK值。 例如，新增a13，把a13排在第11个位置，把a12的LINK值由3改为11， a13本身的LINK值置为3，NA(1)增加1，变为4。链表存储格式重现第i行的所有元素：所以，只要用IA把该行第一个非零元素找到，就可以按LINK的指示找下一个非零元素。 直到把该行中所有非零元素都找出来为止。当找到第i行最后一个非零元素时LINK(A)＝0，这时do循环结束。2.按行消元逐行规格化的高斯消去法2.按行消元逐行规格化的高斯消去法S1. 规格化第一行S2. 一、二行相消S3. 规格化第二行S4.一、三行相消S5. 二、三行相消S6. 第三行规格化最后得到：最后得到：其中，依次取1/2，3，2/5，5，-23/2，-1/12为运算因子。 由后向前取虚线上三角中元素进行回代运算S1. 取－1S2. 取1/2S3. 取3/23、节点编号顺序的优化 3.1、节点编号顺序与稀疏度的关系 3、节点编号顺序的优化 3.1、节点编号顺序与稀疏度的关系 设四节点网络的节点编号分别如图（a）(b)所示。（a）（b）null对应这两种编号的节点方程分别为： 分别进行三次、一次消元运算消去系数矩阵中第一列后，这两个系数矩阵中非零元素的分布将如下式所示。 “*”表示原非零元：“Δ”表示消元后新出现的非零元，称注入元。 null再分别进行三次、两次消元运算，消去其中第二、第三列，得上三角矩阵中的非零元素分布如下式所： 按方案一编号时，需经六次消元进入回代； 按方案二编号时，仅需三次消元就可进入回代。 方案二回代过程也较简单。 差别关键在于消元过程中是否会出现注入元，取决于网络节点编号的顺序 为保持节点导纳矩阵的稀疏度，降低对存贮空间的需求、减少运算量，必须尽可能优化节点编号的顺序。 null3.2 高斯消元与消去节点的关系 以高斯消元法逐列消元，对应于以消去节点法逐个消去节点 消元过程中的注入元，在物理意义上对应于由于消去某节点而出现新的互联支路导纳。3.3三种节点优化编号方法3.3三种节点优化编号方法静态优化法－按静态联结支路数的多少编号 半动态优化法－按动态联结支路数的多少编号 最常用 动态优化法－按动态增加支路数的多少编号三种节点优化编号方法编号结果不同静态优化法－按静态联结支路数的多少编号静态优化法－按静态联结支路数的多少编号如果编号为消去1，2，3后，如果继续消去4，则出现新支路BD，出现注入元：缺点是在连接支路一样时，有编号顺序问题。如果编号如右则无问题：半动态优化法－按各节点动态联结支路数的多少编号半动态优化法－按各节点动态联结支路数的多少编号先编号F，然后消去F取E，并消去：缺点是对环网，可能出现注入元对放射型网络，保证不会产生注入元。再取A，然后消去A重复。。。例题：如下图例题：如下图按静态法编号为1，2消去后，不产生注入元 3消去后，产生注入元（B，F）－（6，4） 4消去后，产生注入元（B，D）－（6，7） 产生两个注入元如果按半动态编号：如果按半动态编号： 先取A（＃1），再取G（＃2）再取C，可见仍然是两个注入元 取F(#3)，产生注入(E,D) 取B(#4)，产生注入(E,C)动态优化法－按动态增加支路数的多少编号动态优化法－按动态增加支路数的多少编号其中：Jn表示与节点n相连的节点数。 Dn表示与节点n相连的Jn个节点间原来有的支路数消去某节点时，可能增加的支路数 等于：如消去f时，增加的支路为10－2＝8个：