矩阵法网络拓扑论文范文

1矩阵法

邻接矩阵自乘公式如下：式中，A为邻接矩阵；T为连通矩阵；上标（k）表示该矩阵为k级连通矩阵。邻接矩阵表示节点间一级连接，因此邻接矩阵是一级连通矩阵，即T（k）=A。重复式（1）直到邻接矩阵的n-1次方，可得到全连通矩阵。通过对连通矩阵平方法可以快速得到全连通矩阵，由此得到平方法公式如下。实际上求全连通矩阵需要的矩阵乘法次数要少于n-2次乘法运算。如果相邻2次求得的连通矩阵相同，即连通矩阵的元素不再发生变化，就已经得到全连通矩阵了。通过矩阵相乘得到的连通矩阵是一个稠密矩阵，并且其稠密的程度随着矩阵相乘的次数增加而增加。式（1）中2个相乘的矩阵之一是稠密矩阵，计算速度很慢。式（2）则需要log2（n-1）次矩阵乘法运算。实际上求全连通矩阵需要的矩阵乘法次数要少于上述次数。如果相邻2次求得的连通矩阵相同，即连通矩阵的元素不再发生变化，就已经得到全连通矩阵了。

2稀疏矩阵法网络拓扑结构

矩阵法求全连通矩阵时一般不采用稀疏技术，而2个满阵存储的矩阵相乘是很浪费时间的，所以矩阵法的运算时间长，很难满足实时性的要求。为解决这一问题，本文利用了基于稀疏矩阵技术的矩阵法。式（1）2个相乘的矩阵中，连通矩阵是稠密矩阵，而邻接矩阵则是稀疏矩阵，可以对它应用稀疏矩阵技术。

2.1布尔矩阵存储邻接矩阵就是布尔矩阵，矩阵中的元素只有“0”和“1”，对非零元素存储时，不需要存储元素的值，只需要记录值为1的元素的行号和列号即可。对邻接矩阵的存储，可以使用下列2个数组：1）IA用来记录每个非零元素的列号；2）JA用来记录每个非零元素的行号。

2.2连通矩阵的计算采用式（1）求连通矩阵时，连通矩阵元素的计算如式（3）所示。

2.3矩阵的对称性邻接矩阵和连通矩阵都是对称阵，计算连通矩阵时，可以只计算矩阵的上三角元素，根据对称性可以直接写出下三角对称元素。

2.4节点优化编号稀疏技术在实施时有2个关键点，一是排零存储和排零运算，二是节点优化编号。排零存储和排零运算能够有效避免对计算结果没有影响的元素的存储和计算，大大提高程序的计算速度。节点优化编号顺序会直接影响到矩阵A的因子表矩阵的系数度，也对计算效率有直接影响。本文采用Tinney-2编号方法[12]。这种方法为半动态节点优化编号法或最小度算法。这种方法按最小出线度编号，不同点是在编号过程中及时排除已经被编号的节点发出的边对未编号节点的出线度的影响。选出某个出线度小的节点参与编号，按图上因子分解的办法模拟消去该节点，只进行网络结构变化的处理，而不进行真实的边权计算，这个已编号的节点及其发出的边不再参与后面的模拟消去运算。在剩下的未消去的子图上重复进行上述编号的过程。

2.5全连通矩阵流程图形成全连通矩阵的流程图见图1。连通矩阵计算时，仅需要对原连通矩阵中值为0的元素进行计算，值为1的元素无需计算。

2.6稀疏矩阵的网络分析本文在网络拓扑结构分析的过程中采用行扫描法分析全联通矩阵。由于可以通过全联通矩阵中一行的元素得知一个联通块中所包含的所有节点，即元素相应位置是1就意味着对应的2个节点向联通，所以只需要联通矩阵中属于同一个联通块的某一行矩阵元素即可判断出联通块的节点组成。

3算例分析

本文算例为某一地区的电力系统，系统规模为：厂站156个，母线段752个，开关7529个，输电线路302条，变压器225台，其中双绕组变压器122台，三绕组变压器103台，串联电抗器支路8条，无功补偿电容204个，无功补偿电抗21个。图2表示网络的部分示意图。本文采用C语言进行编程来实现算法，开发环境采用的是VisualC++6.0。并且在主频2.13GHz的PC机上进行的，通过不同的矩阵算法计算都得到了正确的网络拓扑分析结果，只是在需要进行的乘法次数和计算时间上有显著的差别。

3.1矩阵乘法次数比较本文算法与2种传统算法进行比较，几种算法电气岛分析时矩阵乘法次数表见表1。由表1可见，邻接矩阵自乘算法的矩阵乘法次数较多，连通平方算法可以明显减少矩阵乘法次数。而优化稀疏矩阵法的矩阵乘法次数也比邻接矩阵自乘法要少，与原稀疏矩阵算法相同，但是多于连通矩阵平方算法。

3.2几种矩阵法计算时间比较下面比较上述几种矩阵法在对算例进行拓扑分析时的计算时间，如表2所示。由表2可知，连通矩阵平方算法比邻接矩阵自乘算法的计算速度明显要快，优化稀疏矩阵比邻接矩阵和连通矩阵平方算法都要快，而优化稀疏矩阵算法比原来稀疏矩阵算法运行的时间短。这是因为电气岛分析消耗了矩阵法的大部分计算时间。电气岛分析时，矩阵阶数很大，乘法运算时间长；而母线分析时在各个电压等级内进行，涉及的矩阵阶数较小。

4结论

通过表1，表2数据对比，可得出优化稀疏矩阵法的乘法次数比邻接矩阵自乘少，与原稀疏矩阵算法相同；并且优化稀疏矩阵算法比邻接矩阵法，连通矩阵平方法和原来稀疏矩阵算法计算速度快。同时，还利用邻接矩阵的对称性，采用节点优化编号等手段来提高计算速度，效果比较明显，能够有效解决矩阵法的实用性问题。

作者：王惠中朱宏毅张荧何英单位：兰州理工大学永登县供电公司