Sparsity in diakoptic algorithms

Abstract

Algorithms for network analysis by tearing are studied by determining their orders of computational complexity and comparing it to the computational complexity of the solution of the untorn network. Results indicate that sparsity exploitation is essential. Diakoptic algorithms that exploit sparsity partially are shown to be very restrictive. A classical diakoptic approach that exploits sparsity fully is presented and shown to be comparatively efficient. Its efficiency is partly based on the recognition of a new "interarea cut impedance matrix", which is defined and proven to be sparse. The use of parallel computation by means of diakoptics is shown to be most promising. Results also indicate that diakoptics can be used to reduce fill-in due to large loops. The overall conclusion is that properly programmed diakoptics can indeed be useful for the solution of large systems in a larger class of systems than previously thought possible by many, while not as broad a class as hoped by some.