Modular Analysis of Sequential Solution Methods for Almost Block Diagonal Systems of Equations

Almost block diagonal linear systems of equations can be exemplified by two modules. This makes it possible to construct all sequential forms of band and/or block elimination methods. It also allows easy assessment of the methods on the basis of their operation counts, storage needs, and admissibility of partial pivoting. The outcome of the analysis and implementation is to discover new methods that outperform a well-known method, a modification of which is, therefore, advocated. 1. Introduction Systems of equations with almost block diagonal (ABD) matrix of coefficients are frequently encountered in numerical solutions of sets of ordinary or partial differential equations. Several such situations were described by Amodio et al. [1], who also reviewed sequential and parallel solvers to ABD systems and came to the conclusion that sequential solution methods needed little further study. Traditionally, sequential solution methods of ABD systems performed decompositions of the matrix of coefficients through either band (scalar) elimination or block tridiagonal elimination. The famous COLROW algorithm [2], which is highly regarded for its performance, was incorporated in several applications [3–7]. It utilizes Lam’s alternating column/row pivoting [8] and Varah’s correspondingly alternating column/row scalar elimination [9]. The efficient block tridiagonal methods included Keller’s Block Tridiagonal Row (BTDR) elimination method [10, Section 5, case i] and El-Mistikawy’s Block Tridiagonal Column (BTDC) elimination method [11]. Both methods could apply a suitable form of Keller’s mixed pivoting strategy [10], which is more expensive than Lam’s. The present paper is intended to explore other variants of the decomposition of . It does not follow the traditional approaches of treating the matrix of coefficients as a banded matrix or casting it into a block tridiagonal form. It, rather, adopts a new approach, modular analysis, which offers a simple and unified way of expressing and assessing solution methods for ABD systems. The matrix of coefficients (or, more specifically, its significant part containing the nonzero blocks) is disassembled into an ordered set of modules. (In fact, two different sets of modules are identified.) Each module is an entity that has a head and a tail. By arranging the modules in such a way that the head of a module is added to the tail of the next, the significant part of can be reassembled. The module exemplifies the matrix, but is much easier to analyze. All possible methods of decomposition of could be formulated as decompositions