1、大规模电力系统快速潮流计算方法研究概要第 40卷 第 9期 电 力 系 统 保 护 与 控 制 Vol.40 No.9 2012年 5月 1日 Power System Protection and Control May 1, 2012 大规模电力系统快速潮流计算方法研究夏 沛,汪芳宗(三峡大学电气与新能源学院,湖北 宜昌 443002摘要:直接法和迭代法是求解线性方程组的两类常见方法,比较了多波前算法(MA 、GMRES 算法、FGMRES 算法在大规模电 力系统潮流计算中的求解效率。经 IEEE 118节点、300节点和 Poland 共 7个算例仿真测试表明,基于 ILU 分解法预条件
2、子 的 FGMRES 算法的内迭代次数较 GMRES 算法明显减少,但整体求解时间较 GMRES 算法长;多波前算法的求解速度较二者快。 基于 PQ 分解法预条件子,提出一种 GMRES-MA 混合算法,在 GMRES 算法每步迭代过程生成 Krylov 子空间后,利用多波前算 法(MA直接求解辅助预处理方程组。算例测试结果表明,随着系统规模的增长,该方法的内迭代次数较 GMRES 算法有所减 少,并且计算时间较 GMRES 算法和多波前算法(MA均有所降低,适合于大规模电力系统潮流计算的快速求解。关键词:大规模电力系统;潮流计算;多波前算法(MA;GMRES 算法;FGMRES 算法;GMR
3、ES-MA 混合算法Study on fast power flow calculation methods of large-scale power systemsXIA Pei, WANG Fang-zong(School of Electrical Engineering & Renewable Energy, China Three Gorges University, Yichang 443002, ChinaAbstract : Direct and iterative methods are two common solution methods for linear equat
4、ions. Three methods for power flow calculation inlarge-scale power systems are compared, namely multifrontal algorithm (MA, GMRES method and FGMRES method. Numerical simulation tests on seven systems including IEEE 118, 300 buses and five Poland test systems indicate that the FGMRES method obviously
5、 has fewer inner iterative numbers than the GMRES method with ILU preconditioner, but it takes more computing time on the whole. Overall, MA is the fastest. Based on PQ preconditioning, this paper presents a combined GMRES-MA method. MA is used to solve the assisted preconditioning equations, after
6、the Krylov subspace is generated by the GMRES method for each step in the outer-iterations. The results show that, with the scale expanding, this new method has fewer inner iterative numbers than the GMRES method. Furthermore, compared with both MA and GMRES method, the computing time of the new met
7、hod is decreased. Therefore, this new method is applicable to the fast power flow calculation in large-scale power systems.Key words:large-scale power systems; power flow calculation; multifrontal algorithm(MA; GMRES method; FGMRES method; combined GMRES-MA method中图分类号: TM74 文献标识码:A 文章编号: 1674-3415(
8、201209-0038-050 引言基于牛顿法的电力系统潮流计算,其中 80%的 时间用于求解形如 =Ax b 的稀疏线性修正方程组, 随着方程组阶数的不断增长, 这一点是非常不利的。 针对大规模电网的快速潮流计算方法,目前的研究 主要分为两个方向:一是移植到高性能并行计算机 求解 1或应用集群系统并行处理的技术 2及其他并 行算法 3;二是结合大型稀疏矩阵特点寻找计算量 少、收敛性好、数值稳定性高的算法,这些方法主 要分为两类:直接法和迭代法。直接法通过对雅可比矩阵分块处理的基础上进 行三角分解、求逆等达到求解目的。对于稀疏线性 方程组的直接解法,目前备受关注的是多波前算法 (Multifr
9、ontal Algorithm , MA 4-6。 文献 7将其应 用于电力系统动态时域仿真计算。 文献 8将其应用 于电力系统潮流计算,研究发现,电力系统的规模 越大,多波前算法相对于稀疏三角分解法的加速比 也越明显。文献 9结合 AMD 排序,应用多波前方 法提高大规模稀疏线性修正方程组的求解效率,实 现快速求解最优协调电压控制问题。以广义极小残余算法(Generalized Minimal夏 沛,等 大规模电力系统快速潮流计算方法研究 - 39 -Residual Algorithm, GMRES 为代表的 Krylov 子 空间算法结合适当的预处理技术,已广泛应用于高 维稀疏线性方程组
10、的求解 10-14。近年来,基于可变 预处理技术的灵活广义极小残余算法(Flexible Generalized Minimal Residual Algorithm, FGMRES 也逐渐引起了国内外研究人员的注意。传统直接法在求解过程中需要前推回代的特 点,使其难以实现向量化并行求解,迭代法较直接 法更适合并行处理。文献 15将预处理共轭梯度法 与传统直接法进行了详细比较。数值结果表明,对 于大型系统 (几百个节点以上 , 此类迭代法结合适 当的预处理明显优于传统直接法。但是,共轭梯度 法只适用于雅可比矩阵为对称正定矩阵的情况, GMRES 类方法适合非对称问题的求解,为潮流计 算雅可比矩
11、阵选择合适的预条件子能提高算法的收 敛性能并加快迭代收敛的速度。1 理论基础1.1 多波前算法多波前算法(MA 于上世纪 80年代提出,在 波前法的基础上发展而来,最初用来求解有限元问 题。 Duff 随后引进了并行多波前法 4,随着并行计 算理论和并行计算机的发展,已扩展该算法实现有 限元并行数值分析 16。多波前法的基本思路是找出、构造稀疏矩阵中 的密集子块(即波前,指连续的相同结构的列所构 成的子矩阵 。 波前的构造相当于滤掉矩阵中大量的 零元素,使得大规模的稀疏矩阵集成为多个小规模 的密集阵,波前的分解直接调用高效的 BLAS 库。 相互独立的波前可以被同时分解,具有并行特性。 波前更
12、新矩阵由一系列特定的外积组成,这些外积 的结构用树状结构来表达。相对于传统的稀疏三角分解法直接求解大规模 稀疏线性方程组,多波前算法的一个优点是可以采 用分阶段的求解模式:即符号分析、数值分解和回 代求解。线性方程组系数矩阵的结构一旦确定并且 在以后的迭代求解过程中保持不变,那么通常只需 对该矩阵做一次符号分析,避免重复分析占用求解 时间。文献 8的潮流计算结果表明,分阶段求解模 式较直接求解模式更快更灵活。分阶段求解模式的基本过程是首先根据给定的 稀疏矩阵结构,确定填入元,然后生成相应的消去 树 (或集成树 , 完成符号分析。 在树的指导下不断 由子节点的更新阵集成形成父节点的波前阵,接着
13、通过对波前阵进行矩阵分解而得到相应的分解因子 阵及更新阵,直到完成对整个稀疏矩阵的分解(消 元 , 即数值分解。 最后, 对分解因子阵进行回代求 解。1.2 GMRES 算法Krylov 子空间法是上世纪 90 年代提出的一类 迭代法。考虑方程组 x =b ,式中:n n A R 为大 型 稀疏 非奇异 矩阵 ; nb R 为给 定的 向量 , 取 0nx R 为任一向量, 令=+x x z , 设00 =r b A x 为初始残量。 记 Km和mL 为两个 m 维空间 (m n 。1000, , , K r Ar A rmmspan = ,并称这个空间为由 A和r 生成的 Krylov 子空
14、间,m m=L AK 。 利用 Galerkin原理,在子空间mK 中寻找近似解mz ,使得残余向量0mr Az 和mL 中的所有向量正交。通过 Arnoldi迭代过程求出mK 的一组标准正交基12, , , v v v m 和 Hessenberg 矩阵m,记mV 是由12, , ,v v vm 组成的 n m矩 阵 , 满 足1m m m+=AV V ,m m m=z V y ,mmy R 。 GMRES 算法原理是通过使残量mAz b 最 小的矢量m mz K 来逼近 =Ax b 的精确解, 从而将问题转化为求1m m m=r y e 范数最小的问题,其中 0=Ax b , 11(1,0
15、,0e R m += 。 GMRES 算法 是求解大规模非对称线性方程组的常用算法,具有 收敛速度快、稳定性好等优点。关于 GMRES 算法 实施的具体细节可参考文献 17,本文不再赘述。 GMRES 算法广泛应用于工程计算,在电力系 统分析计算中,主要应用于潮流计算 10-11、暂态稳 定计算 12、无功优化 13、工频电磁场计算 14等。 GMRES 算法实施过程中涉及到大量的矩阵 -向量乘 积运算,适合于并行处理,算法的并行实现成为目 前研究的重点。1.3 迭代法的预处理技术Krylov 子空间方法求解大规模稀疏线性方程 组时,影响算法收敛性能的主要因素是系数矩阵 A 的谱分布情况(即特
16、征值的分布情况或条件数。 通过构造适当的预条件子矩阵对系数矩阵进行预处 理,使得系数矩阵的特征值分布变得集中或减少条 件数。对于高维稀疏线性方程组 =Ax b ,预条件子矩 阵 M 的选取原则是寻找合适的 1M A ,使得预处 理 后 1=A MA I 并 且 辅 助 预 处 理 方 程 组1j j=z M v 易 于 求 解 。 式 中 , I 为 单 位 阵 , 即 ( 1cond A , ( 1A 。迄今为止,潮流计算常用 的预处理方法主要包括 ILU 分解方法(Incomplete LU Factorization Method, ILU 18、 不完全 Cholesky 分解法(In
17、complete Cholesky Factorization Method, IC 19、 分块对角矩阵法 (Block Diagonal Method 20、- 40 - 电力系统保护与控制PQ 分解预处理方法 21等。研究表明,这几种预处 理矩阵没有绝对的好坏。目前,较为流行的带部分 填充量的 ILU 分解法预处理效果较好,但在进行 ILU 分解时必须处理好填充量和预处理效果的平 衡。 PQ 分解法预处理也是一种较好的方法,但随 着系统规模的扩大, PQ 分解法的雅可比矩阵完全求 逆的计算代价也是很大的。 1.4 FGMRES 算法相对 GMRES 的预处理矩阵在整个迭代过程中 保持不变
18、,为了进一步提高预处理效果, Saad 22提 出了基于内外迭代的 FGMRES 方法, 是一种更具灵 活性的 GMRES 算法。目前,主要应用于电力系统 分析和计算电磁学 23领域。在 GMRES 算法中,辅助预处理方程组为 1j j =z M v ,其中 1M 为一个不变的预处理子。并 且在每次迭代中,该式都需要求解一次。 FGMRES 方法中辅助预处理方程组变为 1j j j =z M v ,也就是 在每次迭代时, 采用一系列的预处理子 j M 来处理, 即内迭代过程, j M 可用任何方法求解。相应地, 保存 j z 以形成预处理之后的 Krylov 子空间 k Z , 即12, ,
19、, Z z z z k k = , 近 似 解 0k k k =+x x Z y 。 基 于FGMRES 法的牛顿潮流算法的关键在于每步迭代过程中生成 Krylov 子空间后,都要对预条件子进 行更新。 理论上, FGMRES 算法具有更好的收敛特 性,且对运行在重负荷、 B /X 比值较大等极限状态 的系统容忍度更高。2 GMRES-MA 混合潮流计算方法基 于 牛 顿 法 的 潮 流 计 算 方 程 组 为 :( k k =J X F X ,其中 J 为雅可比矩阵,是一个稀 疏不对称矩阵。本文提出的混合方法是在考虑 GMRES 迭代类方法和多波前方法求解的特点后, 选用 PQ 分解法预条件
20、子对 J 进行预处理,在 GMRES 算法每步迭代过程生成 Krylov 子空间后, 利用高效的多波前算法(MA 直接求解辅助预处 理方程组 1j j =z M v ,达到快速求解的目的。 PQ 分 解法预处理矩阵一旦形成,借助多波前算法灵活的 分阶段求解模式,只需进行一次符号分析和数值分 解运算,并记录分解因子阵,在求解辅助预处理方 程组时,可直接进行调用。3 算例仿真和分析本文基于 Visual Studio 2008编译环境,利用 C 语言设计实现了四种算法应用到大规模电力系统潮 流计算的情形,它们分别是多波前算法(MA 、基 于 ILU 预条件子的 GMRES 算法和 FGMRES 算
21、法以及基于 PQ 分解法预条件子的 GMRES-MA 混合算法。潮流计算模型均采用极坐标模型,多波前算法收敛精度为 10-6;对于 GMRES 和 FGMRES 算法, 内迭代收敛精度设为 10-6,牛顿法外迭代收敛精度 亦设为 10-6,对两类经典的算法进行了仿真比较。 考虑到牛顿法迭代过程中第 1步、第 2步求解结果 往往距精确解较远,进行 GMRES-MA 混合算法的 算例仿真时,第 1步、第 2步的内迭代收敛精度设 为 10-2, 外迭代精度仍设为 10-6。 所采用的算例模型 为 IEEE 118、 IEEE 300及 5个 Poland 互联大规模 电力系统模型,测试时间均为平均值
22、。表 1 给出了 7个算例系统的网络规模和雅可比 矩阵 J 条件数。由表 1可以看出,随着网络规模的 扩大,其初次形成的雅可比矩阵 J 的条件数往往是很大的( 103cond e +J ,接近极限运行状态。 表 1 测试系统的规模及其条件数Table 1 Scales of test systems and condition numbers测试系统节点数支路数J 条件数118 118 186 5.71e+03 300 300 411 2.55e+05 2 383 2 383 2 896 1.09e+06 2 746wp 2 746 3 514 4.61e+06 2 746wop 2 746
23、3 514 4.48e+06 2 736 2 736 3 504 1.41e+06 2 7372 7373 5061.27e+06表 2为基于 ILU 分解法预处理的 GMRES 及 FGMRES 算法进行潮流计算的结果。 同样的收敛精 度下, FGMRES 算法的内迭代次数较 GMRES 算法 明显减少, 但由于 FGMRES 算法每次外迭代开始前 对预处理矩阵进行的更新及其 ILU 分解占用了一定 的计算机时,导致整体求解时间并没有明显下降。 由表 3可知,采用多波前算法的潮流计算时间较 GMRES 类方法明显减少。表 2 测试系统的迭代次数 Table 2 Iteration numbe
24、rs of test systems外 /内迭代次数测试 系统MA GMRESFGMRES 118 5 5/4;7;7;6;6 5/4;4;4;4;4 300 5 5/7;9;8;9;9 5/7;7;7;7;7 2 383 3 3/20;20;20 3/20;19;19 2 746wp 5 5/16;23;23;24;23 5/16;15;17;18;18 2 746wop5 5/16;22;22;21;21 5/16;16;17;18;17 2 736 5 5/16;22;23;23;21 5/16;16;18;18;17 2 73766/16;21;24;23;22;216/16;15;1
25、7;17;17;16夏 沛,等 大规模电力系统快速潮流计算方法研究 - 41 -表 3 测试系统的计算时间Table 3 Computing time of test systems计算时间 /ms测试系统 MA GMRES FGMRES 118 56 57 63 300 603 593 733 2 383 12 866 14 162 14 3422 746wp 28 388 27 948 29 1052 746wop 28 839 28 869 29 7822 736 27 586 29 072 29 9202 737 36 647 37 521 37 842基于以上仿真分析结果,本文提出的
26、 GMRES- MA 混合算法选用定常的 PQ 分解法预条件子,利 用多波前算法灵活的分阶段求解模式加速预处理矩 阵的完全求逆。仿真结果见表 4,结果表明,随着 系统规模的增长,该方法的内迭代次数较 GMRES 算法有所减少,并且计算时间较 GMRES 算法和多 波前算法均有所降低。表 4 GMRES-MA混合算法潮流计算结果Table 4 Power flow calculations with combinedGMRES-MA method测试系统 外 /内迭代次数 计算时间 /ms118 5/4;5;10;10;10 62 300 5/5;4;18;18;19 676 2 383 3/3
27、;11;13 13 6472 746wp 5/6;6;19;19;19 27 8922 746wop 5/5;5;21;21;22 28 3462 736 5/5;5;18;17;18 28 6942 737 6/5;6;17;17;16;15 36 2224 结论多波前算法、 GMRES 算法、 FGMRES 算法是进 行大规模电力系统潮流计算的有效方法。在同样的 收敛精度下,基于 ILU 预条件子的 FGMRES 算法的 内迭代次数较 GMRES 算法明显减少, 但整体求解时 间较采用同一预处理矩阵的 GMRES 算法长; 多波前 算法的求解速度较基于 ILU 预条件子的 GMRES 类
28、算法要快。随着系统规模的增长,本文提出的 GMRES-MA 混合算法内迭代次数较 GMRES 算法有 所减少, 并且计算时间较 GMRES 算法和多波前算法 均有所降低,适合于大规模电力系统潮流计算的快 速求解。参考文献1 夏俊峰 , 杨帆 , 李静 , 等 . 基于 GPU 的电力系统并行潮 流 计 算 的 实 现 J. 电 力 系 统 保 护 与 控 制 , 2010, 38(18: 100-103.XIA Jun-feng, YANG Fan, LI Jing, et al. Implementation of parallel power flow calculation based
29、on GPUJ. Power System Protection and Control, 2010, 38(18: 100-103.2胡博 , 谢开贵 , 曹侃 . 基于 Beowulf 集群的大规模电力 系统牛顿法潮流求解的并行 GMRES 方法 J. 电工技 术学报 , 2011, 26(4: 145-152.HU Bo, XIE Kai-gui, CAO Kan. Parallel GMRES techniques for solving Newton power flow of large scale power systems on the Beowulf clusterJ. Tr
30、ansactions of China Electrotechnical Society, 2011, 26(4: 145-152. 3 黄靖 , 张晓锋 , 叶志浩 . 大型船舶电力系统分布式并 行潮流计算方法 J. 电力系统保护与控制 , 2011, 39(7: 50-55.HUANG Jing, ZHANG Xiao-feng, YE Zhi-hao. A distributed parallel load flow calculation method for large ship power systemJ. Power System Protection and Control,
31、2011, 39(7: 50-55.4Duff I S, Reid J K. The multifrontal solution of indefinite sparse symmetric linear systemsJ. ACM Transaction on Mathematical Software, 1983, 9: 302-335.5Duff I S, Reid J K. The multifrontal solution of unsymmetric sets of linear equationsJ. SIAM Journal of Scientific and Statistical Computing,1984, 5(3: 633-641. 6Orfanogianni T, Bacher R. Using automatic code differentiation in power flow algorithmsJ. IEEE Trans on Power Systems, 1999, 14(1: 138-144.7Khaitan
