MPI-based Parallel Solution of Sparse Linear Systems Using Chio's Condensation Algorithm and Test Data from Power Flow Analysis

Solving sparse systems of linear equations permeates power system analysis. Newton-Raphson, decoupled, and fast decoupled algorithms all require the repeated solving of sparse systems of linear equations in order to capture the steady state operational conditions of the power system under test. Solving these systems of equations is usually done using LU Factorization which has an order of complexity O(n3) where n represents the number of equations in the system. The Chio’s condensation algorithm is an alternative approach, which in general has a complexity of O(n4). However, it has a straightforward formulation that can be easily implemented in a parallel computing architecture. Previous research has not investigated the application of the Chio’s algorithm under sparse matrix, which is typical for power system analysis. This thesis presents a MPI-based parallel solution of sparse linear systems using Chio’s condensation algorithm and realistic test data from power flow analysis. Different sparse matrix techniques are discussed, and a reordering scheme is applied to further improve the efficiency for solving the sparse linear system.