电力网络计算中的稀疏技术课件

电力网络计算中的稀疏技术

2025/4/1稀疏矩阵：只有少量非零元素稀疏度：对m*n阶矩阵A，其中有τ个非零元素，则可定义稀疏度线性方程组的求解主要涉及大量的四则运算，而0的四则运算相当特殊稀疏计算亦可称作“排零”计算2025/4/1稀疏矩阵以求解节点电流-电压线性方程为例：非线性的潮流方程本质相同，且也需在迭代过程中求解线性方程系数矩阵为节点导纳矩阵对角元：与相应节点相连的所有支路导纳之和，称自导纳非对角元：与相应行列对应的节点间所有支路导纳之和的相反数，称互导纳节点导纳矩阵为对称矩阵只有电力网络中存在支路，相应非对角元才不为02025/4/1电力网络的稀疏性设有1000条母线的电力系统，母线出线度平均为10，其稀疏度为实际电网仅有非常少量的枢纽变电站存在出线度为10左右的母线大量母线出线度仅为1~2发电机机端母线终端负荷母线联络母线……算法是否采用排零操作可影响计算速度几十上百倍2025/4/1电力网络的稀疏性核心：不存储零元素

仅保留非零元素在原矩阵中的数值及位置信息

应在必要时轻易恢复成满阵存储格式上世纪六七十年代提出当前计算机硬件速度和容量已发生了翻天覆地的变化，还要考虑稀疏存储吗？需要分析的电力系统规模也显著扩大要求计算的速度也更快（如在线分析）节省计算机内存占有量尽量减少检索矩阵元素所耗时间2025/4/1稀疏存储技术a11a12a14a21a22a23a33a42a43a442025/4/1散居存储11122234441241233234原矩阵中有τ个非零元素，则需3τ个存储空间本例中τ=10，需30个存储空间，原矩阵只需16个存储空间？a11a12a14a21a22a23a33a42a43a442025/4/1按行（列）存储14781241233234如何检索到a23？节省存储空间的原因：第二个数组中元素在数组中的位置信息也被利用起来。检索非零元素的程序变复杂——没有免费的午餐原矩阵中每行第一个非零元素在列索引数组中的位置2025/4/1三角检索存储任一方阵B均可分解成B=LDU的形式L——单位下三角矩阵D——对角线矩阵U——单位上三角矩阵可用同样阶数方阵同时存储三个矩阵的信息，如上面矩阵A可表示有时也表示成B=L’U，此时L’=LD不是单位下三角矩阵，则只需两个矩阵相乘来表示a12a14a232025/4/11344243三个数组存储L（按列）：1234244a21a42a43一个数组存储D：三个数组存储U（按行）：a11a22a33a44矩阵化为上三角矩阵的初等变换过程等价的矩阵计算图论解释2025/4/1稀疏矩阵的因子表分解2025/4/1矩阵化为上三角矩阵的初等变换过程（假设在求解YV=I）可表示为2025/4/1（续）2025/4/1初等变换过程等价的矩阵计算其中2025/4/1同理其中2025/4/1最终故可证明L为下三角矩阵，此处略此过程称为因子表分解因子表分解的过程即为高斯消去的过程只介绍对称矩阵的因子表分解2025/4/1图论解释2025/4/1A图4121110586293172025/4/1有向A图4121110586293172025/4/1赋权有向A图412111058629317**************ΔΔΔΔΔΔΔΔΔΔΔΔ节点号从小到大依次操作对每个节点分为两步：规格化运算消去运算2025/4/1因子表分解plkjappajjakkallapjapkaplajkaklappapjapkaplajpajjajkakpakjakkaklalpalkall用对角元去除各非零非对角元图上的操作：修正由p发出的互边新边权为原边权除以p自边边权2025/4/1节点p的规格化运算plkjappajjakkallapjapkaplajkakl1apj/appapk/appapl/appajpajjajkakpakjakkaklalpalkallapp正下方若有非零元素，则相应行需做消去运算消去某行时app右方非零元素对应列对本行有影响2025/4/1节点p的消去运算plkjappajjakkallapjapkaplajkakl1apj/appapk/appapl/appajpajjajkakpakjakkaklalpalkall2025/4/11apj/appapk/appapl/appajpajjajkakpakjakkaklalpalkall1apjapkaplapj*appajjajkajlapk*appakjakkaklapl*appaljalkallplkj任选两条p点发出边，其末端节点间的边受到影响（例：ajk，akl）原位置若没有边，则应出现一条新的边（例：ajl）所选两条边可以重合，则受影响的是末端节点的自边（例：ajj，akk，all）2025/4/112节点算例中的新增非零元412111058629317**************ΔΔΔΔΔΔΔΔΔΔΔΔ2025/4/112节点算例中的新增非零元412111058629317**************ΔΔΔΔΔΔΔΔΔΔΔΔ2025/4/112节点算例中的新增非零元412111058629317**************ΔΔΔΔΔΔΔΔΔΔΔΔ2025/4/112节点算例中的新增非零元412111058629317**************ΔΔΔΔΔΔΔΔΔΔΔΔ2025/4/112节点算例中的新增非零元412111058629317**************ΔΔΔΔΔΔΔΔΔΔΔΔ2025/4/112节点算例中的新增非零元412111058629317**************ΔΔΔΔΔΔΔΔΔΔΔΔ2025/4/112节点算例中的新增非零元412111058629317**************ΔΔΔΔΔΔΔΔΔΔΔΔ2025/4/112节点算例中的新增非零元**412111058629317************ΔΔΔΔΔΔΔΔΔΔΔΔ2025/4/1具体算例42312-1-1-12-1-12-1-1-14-1-1-1-122242025/4/1节点1的计算4231-0.5-1-0.5-121.523.5规格化计算消去计算新增非零元-0.52025/4/1节点2的计算4231-0.5-0.667-0.5-1.33321.51.3333.333规格化计算消去计算-0.3332025/4/1节点3的计算4231-0.5-0.667-0.5-121.51.3332规格化计算消去计算-0.333节点4为最后一个节点，不需计算2025/4/1因子表分解结果4231-0.5-0.667-0.5-121.51.3332-0.333只对图中的节点和边进行操作，故为稀疏技术对更大规模的网络道理相同2025/4/1利用因子表求解线性方程组前代计算规格化计算回代计算2025/4/1前代计算2025/4/1以节点编号顺序从小到大计算某变量只影响比其编号大的变量，故称前代仅当L中相应元素不为0时才影响计算结果亦可用图解释2025/4/1前代的图论解释4231-0.5-0.667-0.5-121.51.3332-0.333求解依前分析，应先做前代计算2025/4/1等号右边对应各节点，其值称为节点的点位（电位？）方程组的计算过程即为求取最终点位的过程某节点点位只直接影响此节点发出边终点点位4231-0.5-0.667-0.5-121.51.3332-0.3330100节点1的点位为0，对相关节点电位无影响2025/4/1节点1的前代计算4231-0.5-0.667-0.5-121.51.3332-0.33301002025/4/1节点2的前代计算4231-0.5-0.667-0.5-121.51.3332-0.333010.6670.3332025/4/1节点3的前代计算4231-0.5-0.667-0.5-121.51.3332-0.333010.6671节点4为最后一个节点，不需再做前代计算，前代计算结束。2025/4/1规格化计算新点位为当前各点点位除以相应自边边权4231-0.5-0.667-0.5-121.51.3332-0.333010.66714231-0.5-0.667-0.5-121.51.3332-0.33300.6670.50.52025/4/1回代计算2025/4/1以节点编号顺序从大到小计算某变量只影响比其编号小的变量，故称回代仅当U中相应元素不为0时才影响计算结果亦可用图解释2025/4/1回代的图论解释4231-0.5-0.667-0.5-121.51.3332-0.33300.6670.50.52025/4/1节点4的回代计算4231-0.5-0.667-0.5-121.51.3332-0.3330.250.83410.52025/4/1节点3的回代计算4231-0.5-0.667-0.5-121.51.3332-0.3330.251.510.52025/4/1节点2的回代计算4231-0.5-0.667-0.5-121.51.3332-0.33311.510.5节点1为第一个节点，不需再做回代计算，回代计算结束最终点位即为方程组的解，即仅图中有边时才有计算，故为稀疏技术前述内容研究的是A稀疏时的排零技术若b中也只有少量非零元素，如何提高计算速度？若只需计算少数的x，如何提高计算速度？核心内容：分析出前代回代过程中那些计算步是必不可少的，哪些是可以忽略的2025/4/1稀疏矢量技术（Ax=b）定义：有向因子图上，每个节点发出边中对侧节点编号最小的边构成的子图为何一定是树？连通图节点数比支路数多12025/4/1几个概念——道路树412111058629317定义：有向因子图上，每个节点发出边中对侧节点编号最小的边构成的子图为何一定是树？连通图节点数比支路数多12025/4/1几个概念——道路树412111058629317定义：有向因子图上，每个节点发出边中对侧节点编号最小的边构成的子图为何一定是树？连通图节点数比支路数多12025/4/1几个概念——道路树412111058629317定义：道路树上点沿道路树到树根的路径右边分别为节点2和节点4的道路树相关性质：原有向因子图上任一点发出的边的终点必在该点的道路上树支连支2025/4/1几个概念——点的路41211107121110529点集中所有点的道路的并集右边为点集{2,4}的路集相关性质有向因子图上任一边两个端点的路集即为小号节点的道路若任一点集中节点对之间都有边，则点集的路集即为最小号节点的道路……2025/4/1几个概念——点集的路集41211105297前代只在非零元素对应点集的路集上进行（前代只直接影响该边的终点）设b中只有2号、4号两个元素非零2025/4/1稀疏独立矢量（b）的前代计算412111058629317路集上任一点的前代必须在路集上比该点编号小且其道路经过该点的点的前代完成后才能进行以10号节点为例2025/4/1稀疏独立矢量（b）的前代计算412111058629317回代只在待解元素对应点集的路集上进行（回代只直接影响该边的起点）设x中只有2号、4号两个元素需求解2025/4/1稀疏解矢量（x）的回代计算412111058629317路集上任一点的回代必须在路集上比该点编号大的点的回代完成后才能进行以10号节点为例2025/4/1稀疏解矢量（x）的回代计算412111058629317改善稀疏矩阵计算的性能改善稀疏矢量计算的性能2025/4/1节点优化编号目标：因子表分解过程中尽可能少出现新的非零元素Tinney-1Tinney-2Tinney-32025/4/1改善稀疏矩阵计算的性能2025/4/112345***************节点编号顺序12025/4/112345未出现新的非零元***************消去节点12025/4/112345出现新的非零元*********△***△*消去节点22025/4/112345出现新的非零元********△**△△*消去节点32025/4/112345节点4对应的对角元下方已不存在非零元，本步不用计算********△*△*消去节点4按当前编号顺序，消去过程中上三角中出现了两个新的非零元2025/4/131254原始网络中支路数不变，故起初矩阵中非零元个数不变***************节点编号顺序22025/4/131254出现新的非零元*******△****△*△△***消去节点12025/4/131254出现新的非零元******△***△△△△*△*△△*消去节点22025/4/131254******△**△△△*△△△*消去节点32025/4/131254******△**△△*△△*消去节点4按当前编号顺序，消去过程中上三角中出现了四个新的非零元2025/4/153412原始网络中支路数不变，故起初矩阵中非零元个数不变***************节点编号顺序32025/4/153412未新增非零元。******