next up previous
Next: Block-Diagonal-Bordered Direct Linear Up: Introduction Previous: The State of

Block-Diagonal-Bordered Power System Matrices

Power system distribution networks are generally hierarchical with limited numbers of high-voltage lines transmitting electricity to connected local networks that eventually distribute power to customers. In order to ensure reliability, highly interconnected local networks are fed electricity from multiple high-voltage sources. Electrical power grids have graph representations which in turn can be expressed as matrices --- electrical buses are graph nodes and matrix diagonal elements, while electrical transmission lines are graph edges which can be represented as non-zero off-diagonal matrix elements. We show that it is possible to identify the hierarchical structure within a power system matrix using only the knowledge of the interconnection pattern by tearing the matrix into multiple partitions and coupling equations that yield a block-diagonal-bordered matrix.

Diakoptics, or the tearing of systems into smaller subsystems then solving the subsystems in a piecewise manner before reconstructing the system, has offered promise to be used as the basis for parallel sparse linear solvers for power systems applications [12,26]. A specialized form of diakoptics, node-tearing nodal analysis, has been used to partition power systems network matrices into block-diagonal-bordered form [49]. The application of diakoptic techniques identifies inherent power systems network structure that in turn can be exploited to provide parallelism for sparse linear solvers embedded within power systems applications. Node-tearing diakoptic techniques are readily identified with methods to identify parallelism in general sparse linear solvers. In particular, node-tearing-based partitioning of power systems networks identifies block-diagonal-bordered form matrices, that are related to elimination trees, and supernodes within the network where there is inherent parallelism. Diakoptic node-tearing-based partitioning identifies the basic network structure that provides parallelism for the majority of calculations within both direct and iterative solutions of power systems network-based linear systems.

In this thesis, we examine the applicability of parallel block-diagonal-bordered sparse solvers for real power system applications that require either the solution of symmetric positive definite sparse matrices or location symmetric sparse matrices that result from solving problems relating to power systems networks. Variations of this technique could be used to solve other power system sparse linear systems such as those that result from solving linearized differential-algebraic equations from transient stability analysis applications or small-signal stability assessments. The implementations we describe in this paper work directly with the equations resulting from the power systems network, the smallest class of power system matrix.

The implementations we developed can be used to solve symmetric positive definite load flow analysis Jacobian matrices or position symmetric network matrices from transient stability analysis. In spite of only examining linear solver implementations that solve relatively small network-related matrices, we have been able to obtain good parallel speedups. We expect that even better performances would be possible for parallel implementations designed to solve a single system of linear equations that represent a combination of the generator dynamical equations and network equations from transient stability analysis or small-signal analysis. For these problems, there are additional parallel calculations with no additional parallel communications overhead.





next up previous
Next: Block-Diagonal-Bordered Direct Linear Up: Introduction Previous: The State of



David P. Koester
Sun Oct 22 17:27:14 EDT 1995