节点优化编号的改进最小度算法＊

颜 伟，黄正波，李佐君，余 娟，贾晓峰

(1.输配电装备及系统安全与新技术国家重点实验室，重庆大学电气工程学院，重庆 400030;2.重庆电力设计院，重庆 400030)

电力系统计算会进行大量的矩阵因子分解操作，通过节点优化编号减少矩阵因子分解过程中的注入元数量或矮化因子道路树可以提高因子分解速度［1～9］。在较常见的方法中，从减少注入元数量的角度出发，有静态方法(Tinney-1)，半动态方法(最小度编号方法，Tinney-2)，动态方法(Tinney-3)［10，11］，以及近似最小度 AMD(approximate minimum degree)［12，13］等方法。从矮化道路树的角度出发，在力求减少注入元的前提下，有基于MD和稀疏失量法的最小度最小深度算法MD-ML(minimum degree-minimum length)［14］和最小度最小前趋节点数算法MD-MNP(minimum degree-minimum number of predecessors)［15］以及将 MD和蚁群算法［16］与邻接表［17］等算法结合的编号算法。其中，MD算法是在电力系统中应用最为普遍的方法，也是AMD、MD-ML、MD-MNP以及其它一些算法的基础，因此，提高MD算法的计算效果与效率具有重要意义。

为此，本文提出了改进的最小度算法。首先，本文提出了量度的概念，指出MD编号过程中，在度最小的前提下，将量度最小的节点先行消去，可实现注入元更少，从而提高编号效果。另外，选取主元后，利用不换行不换列的直接符号高斯消元法用于实现MD算法，同时改进最小度节点的定位方式并利用稀疏技术提高计算效率。实验证明了本文提出的改进措施的有效性。

1 MD算法与量度

1.1 MD 算法

电力系统仿真计算中，MD方法是常用的节点优化编号方法，通过减少网络消元的新增注入元个数提高因子分解效率。该方法的核心思想是将网络中连接支路数最少的节点优先编号，然后消去该节点并修改剩余节点的连接关系。其中，节点的关联支路条数称为该节点的度。对于N节点网络，具体实现步骤如下:

1)统计原始网络所有节点的度，并记存各节点所连接支路对端的节点号。同时，初始化节点优化编号，令k=1，即开始进行第k个节点的编号。

2)在尚未编号的节点中，选择度最小的节点i，将其节点编号记为k。若同时有多个节点的度最小，则随机选取其中之一进行编号。

3)令k=k+1，若k大于N，则节点优化编号结束。否则，转至步骤4。

4)消去节点i，修正剩余节点的关联关系和度，然后转至步骤2)。其中节点i的消去方法如下:①消去节点i及其相连的所有支路，并使与i节点直接相连的所有节点的度减1，同时去掉支路对端的节点号i。②在与节点i相连的所有节点中，若存在两个节点间没有支路关联，则在这两个节点间增加一条新支路，并使相应节点的度增加1。该新增支路即为网络消元的注入元。比如若首先消去图1的节点5，则需在1-4和3-4之间都增加一条新支路，相应使节点1、3的度增加1，4的度增加2。

图1 无向网络图Fig.1 Undirected network

1.2 量度的提出与应用

实际电网MD编号过程中存在大量度相同的节点。在度相同的节点中选择不同的节点优先编号，分别从道路树长短或注入元数量的角度分析，会产生不同的编号效果。因此，在MD方法的基础上，为尽量矮化道路树，产生了MD-ML和MD-MNP等方法:MD-ML方法在度最小的基础之上进一步选择"深度"最小的节点优先编号;MD-MNP则选择"前趋节点数"最小的节点。从进一步减少注入元的角度出发，本文定义了节点的“量度”概念，并提出了在度相同的前提下，以量度最小的节点优先编号判据。

量度的定义:与某节点相连的所有节点的度的总和称为该节点的量度。量度的计算公式可表示为

其中:D(k)(j)表示节点j在第k次编号时的度;Q(k)(i)表示节点i在第k次编号时的量度;j∈i表示节点j属于与节点i相连的节点集。如图1的原始网络中，k=1，对于i=1 的节点，存在j∈{2，3，5，6}，则有 Q(1)(1)=D(1)(2)+D(1)(3)+D(1)(5)+D(1)(6)=2+3+3+1=9。

由MD算法的步骤4的注入元增加方法②可推知，若与某节点相连的节点个数越少，即度越小，当消去该节点时，可能增加新支路的机率就越小，注入元也就越少。对于度相同的节点，若其量度越小，那么消去该节点后，与其相联的节点的度在更新后也可能会更小。因此，对节点编号流程而言，在度相同的前提下选择量度最小的节点优先编号，当该节点消去后，可更快构造度更小的节点，由此减少注入元数量。考虑量度的MD算法步骤如下:

1)同MD算法的第1步。

2)在未编号节点中，选择度最小的节点i，令其节点编号为k。若同时存在多个节点的度最小并相同，则选择量度最小的节点;若其中还存在多个节点，则随机选取其中之一对其编号。

3)同MD算法的第3步。

4)同MD算法的第4步。

以上方法中，每消去一个节点都需要统计相关节点度与量度的大小，计算量较大。下面提出两个办法以供参考:一是统计原始网络每一个节点的量度，近似作为编号过程中的节点量度;二是仅统计所有度最小并相同的节点的量度的大小并比较。

2 MD算法与行列不变换符号高斯消元法

由于网络图的节点消去过程与高斯符号消元一一对应［5］，因此，网络图的节点消去可以用对应节点关联矩阵的高斯符号消元法实现。其中，网络中的节点对应着矩阵中的主对角元素，支路两端关联的节点编号对应矩阵非对角元素的行号和列号，节点的消去对应以主对角元素为主元的高斯符号消元。但是，传统高斯消元法主要用于线性方程组求解，消元后需要形成上三角非零结构，便于线性方程组求解的回代操作。这就要求在选取对角主元素后首先进行换行换列操作，将所选主元调换到左上角，然后进行高斯消元操作，十分耗时。因此，一般不采用高斯消元法进行MD编号计算。本文提出了一种行列不变换的符号高斯消元法，该方法在不进行换行换列操作的前提下直接以所选主元为中心进行消去操作，将该方法用于MD算法，从而提高编号的效率。

2.1 行列不变换符号高斯消元方法

传统的高斯消元法详见文献［18］。

行列不变换的高斯消元法解释如下。对于普通N维矩阵A，高斯消元需要进行N－1次循环消元。对k=1，2，…，N －1，表示第k步循环消元前的第i行、第j列的元素。在第k步循环消元之前，将选取第m行、第m列对角元素为主元，令所有待选用的m∈M(M是第k步循环消元之前所有待选对角主元的行(列)值的集合)，第k步消元之前所有已选用的m∈M，有M∪M={1，2，3，…，n}。对 k=1 到 n － 1，迭代进行。

容易证明，进行行列不换的高斯消元后再进行一定次序的换行换列操作，可以得到传统高斯消元法形成的上三角结构，也就是行列不换的高斯消元法与传统方法是等效的。符号高斯消元法只考虑零与非零计算，根据公式(2)，对于行列不变换的符号高斯消元法，当k=1到n－1，迭代进行。

图2展示了图1网络对应的节点关联矩阵的行列不变换的符号高斯消去过程。图中，“·”表示非零元，“×”表示已选择的主元。第一个图为原始网络关联图。当k=1时，选取第4行、第4列对角元素为主元，消去第4列中除去当前主元的所有非零元素，即第5行、第4列的非零单元。当k=2时，选取第6行、第6列对角元素为主元，消去第6列中所有非零元素，但不消去已选择过的主元的行中的元素，此步中不能消去第4行中的元素。以此类推，完成操作。可以看出，上述操作并没有进行任何的换行换列操作。

图2 特殊符号高斯消元流程图Fig.2 Flow chart of special symbolic Gauss elimination

2.2 基于特殊高斯消元法的MD算法

由高斯消元法与图的消去操作的对应关系可知，对于一个普通N维矩阵A，第k步消元之前，对任意m∈M，m行中除对角元素的所有的非零元个数为D(k)(m)。如图2对应的原始矩阵，当m=1，第1行除对角元的非零元个数为4，即D(1)(1)=4，与先前的分析一致。因此，只需要通过待消元矩阵整理出D(k)(m)，在每一步中选择满足最小度的节点，然后按照特殊的高斯消元法便可逐步进行MD消去操作。其它的操作，可参见1.2的MD算法流程。另外，高斯消元之前，m列除对角元的非零元素所对应的行中，除对角元的所有的非零元个数之和为Q(m)。如图2中对应的原始矩阵，当m=1时，第1列除对角元外，在第2、3、5和6行中存在非零元素，这些行除对角元素外，分别有2，3，3和1个非零元素，将其相加得Q(1)=9，与前面的分析相符合。因此，不换行不换列的符号高斯消元算法也可应用于考虑量度的MD改进算法。

2.3 最小度选择方式的改进与稀疏技术的应用

由1.1节MD算法步骤第5步的第①部分可以看出，消去任意节点时，与该节点相连的所有节点的度都会减1，同时，若与该节点相连的某节点本身的度已为最小度并且不用进行第②部分的操作，则此节点所形成的度必定为－1。另外，没有与被消去节点相连的所有节点的度都不会发生变化。因此，若某节点的度在第k步编号后变为1，则必定为第k+1步编号的最小的度，即－1。例如图1的4，5，6节点编号并消去后，可形成图3的a网络，“()”内的编号为新节点编号，虚线为消去的支路。如图3的a网络中，D(4)min=D(4)(1)=D(4)(2)=D(4)(3)=2，然后选择第2节点进行消去，消去后的节点1，3的度均有=－1=1，为当前的最小度，如图3的b。因此，MD算法第k+1步搜寻最小度编号时，可优先在与第k次被编号的节点所关联的节点群中查寻，提高效率。

图3 网络消去中间图Fig.3 Intermediate network elimination

另外，本文利用稀疏技术、矩阵的对称性等特点进一步提高符号高斯消元法的效率。首先，利用十字链表存储待编号的矩阵，只存储并操作矩阵的非零元部分，可降低存储空间，提高高斯消元的效率。同时，文献［19］指出:对称矩阵高斯消元中的待消元矩阵仍然具有对称性，利用此性质，仅计算矩阵的上三角或下三角部分便可完成对整个矩阵的计算，由此降低近一半的消元计算时间。由于本文涉及的节点编号的符号矩阵具有对称性，所以，可利用上述性质提高计算效率。

3 实验与分析

计算机硬件配置为:Intel(R)Core(TM)2 CPU 1.8GHz，内存 0.99GB，操作系统 Windows XP，仿真环境VC 6.0。表1、2中的改进方法是考虑量度的MD方法，并且利用不换行列的符号高斯消元法实现。MD方法是基于图论的解析，按照1.1的算法步骤实现。算例分别是IEEE300与波兰2746节点(P2746)网络。

表1统计了两种方法的注入元数量。可以看出，改进方法的编号效果优于传统MD算法。效果提高率(计算公式为(QMD－ Q改进)/QMD。其中，QMD为MD注入元数量;Q改进为改进方法注入元数量)分别为8.33% 与4.01%。

表1 编号的效果Tab.1 Effectiveness of the ordering

表2统计了两种方法的编号时间。可以看出，改进方法的编号效率优于传统MD算法。耗时减少率(计算公式为(T改进－TMD)/TMD。其中，TMD为MD方法计算时间;T改进为改进方法计算时间)分别为24.44% 与 33.72%。

表2 编号的效率Tab.2 Efficiency of the ordering

4 结论

文中提出了MD算法的两个改进措施，分别用于提高MD算法的效果与速度。

(1)提出了最小量度的概念，基于MD算法，通过优先处理具有最小量度的节点从而构造出度更小的节点，从整体上减少注入元数量。

(2)提出了用于MD算法的行列不变换符号高斯消元方法，该算法直接利用高斯消元法实现节点优化编号，提高计算效率。另外，分别从最小度节点的选择以及稀疏技术的应用两个方面提高算法计算效率。

IEEE300与波兰2746阶的节点导纳矩阵的编号效果证明，本文提出的方法的效率与效果均优于MD算法。并且，量度的选择方法与行列不变换符号高斯消元法还可用于改进 AMD、MD-ML和MD-MNP等算法。

［1］廖怀庆，单渊达，吴杰(Liao Huaiqing，Shan Yuanda，Wu Jie).基于拓扑扩展和矩阵增广的复杂配电网络三相不对称系统快速潮流算法(Topological extension and augmented matrix based method for solution of complicated distribution load flow)［J］.电网技术(Power System Technology)，2001，25(7):36 －40.

［2］朱凌志，安宁(Zhu Lingzhi，An Ning).基于二维链表的稀疏矩阵在潮流计算中的应用(Application of twodimensional chain table based sparse matrix in power flow calculation) ［J］.电网技术(Power System Technology)，2005，29(8):51 －55.

［3］何洋，洪潮，陈昆薇(He Yang，Hong Chao，Chen Kunwei).稀疏向量技术在静态安全分析中的应用(Study of sparse vector techniques applied to contingency analysis)［J］.中国电机工程学报(Proceedings of the CSEE)，2003，23(1):41 －44.

［4］Freris L L，Sasson A M.Investigation of the load flow problem ［J］.Proceeding of IEE，1968，115(10):1459－1470.

［5］Tinney W F，Brandwajn V，Chan S M.Sparse vector methods［J］.IEEE Trans on Power Apparatus and Systems，1985，104(2):295－301.

［6］张伯明，陈寿孙.高等电力网络分析［M］.北京:清华大学出版社，1996.

［7］Luo G X，Semlyen A.Efficient load flow for large weakly meshed networks［J］.IEEE Trans on Power Systems，1990，5(4):1309－1316.

［8］王守相，王成山(Wang Shouxiang，Wang Chengshan).配电系统节点优化编号方案比较(Comparative study of optimal node indexing schemes for distribution systems)［J］.电力系统自动化(Automation of Electric Power Systems)，2003，27(8):54 －58.

［9］蔡中勤，郭志忠，陈学允(Cai Zhongqin，Guo Zhizhong，Chen Xueyun).辐射状配电网的逆流编号法(Upstream bus－labeling technique for radial distribution networks)［J］.电力系统自动化(Automation of Electric Power Systems) ，1999，23(24):16－19.

［10］Tinney W，Walker J.Direct solutions of sparse network equations by optimally ordered triangular factorization［J］.Proceedings of the IEEE，1967，55(11):1801 －1809.

［11］Alsac O，Stott B，Tinney W F.Sparsity-oriented compensation methods for modified network solutions［J］.IEEE Trans on Power Apparatus and Systems，1983，102(5):1050－1060.

［12］Heggernes P，Eisenstat S C，Kumfert G，et al.The computational complexity of the minimum degree algorithm［R］.Virginia:Universities Space Research Association，2001.

［13］Davis Timothy A，Gilbert John R，Larimore Stefan I，et al.A column approximate minimum degree ordering algorithm［J］.ACM Trans on Mathematical Software，2004，30(3):357－376.

［14］Gomez A，Franquelo L G.An efficient ordering algorithm to improve sparse vector methods［J］.IEEE Trans on Power Systems，1988，3(4):1538 －1544.

［15］Betancourt Ramon.Efficient heuristic ordering algorithm for partial matrix refactorization［J］.IEEE Trans on Power Systems，1988，3(3):1181－1187.

［16］彭春华，徐雪松(Peng Chunhua，Xu Xuesong).基于蚁群算法的电力网络节点编号多方案优化(Electric power network node numbering multi-scheme optimization based on ant colony algorithm)［J］.电力系统及其自动化学报(Proceedings of the CSU-EPSA)，2007，19(2):60－65.

［17］赵强，董朝霞(Zhao Qiang，Dong Zhaoxia).用邻接多重表实现节点优化编号(An application of adjacency multilist in node optimizing code)［J］.电力系统及其自动化学报(Proceedings of the CSU-EPSA)，2002，14(4):13－15.

［18］杨大地，王开荣.数值分析［M］.北京:科学出版社，2006.

［19］胡圣荣，罗锡文，蒋炎坤(Hu Shengrong，Luo Xiwen，Jiang Yankun).对称线性方程组的一种实用对称三角分解法(A practical symmetric triangular factorization algorithm for symmetric linear systems)［J］.武汉工业大学学报(Journal of Wuhan University of Technology)，1999，21(1):92－94.