Algorithms for Almost Block Diagonal Linear Systems

Codes for solving systems of ordinary differential equations for use in the method of lines for partial differential equations (PDEs) usually provide only a banded system solver. In this context, a frequently occurring structure is almost block diagonal (ABD). Solving ABD systems by imposing banded structure introduces fill-in and is inefficient. Though robust, efficient ABD software has been developed and used in packages for solving boundary value problems with separated boundary conditions for ordinary differential equations (BVODEs), it has not been generally exploited in PDE software. The situation with bordered almost block diagonal system software for BVODEs with nonseparated boundary conditions is less satisfactory. This survey draws on material from a variety of sources, particularly [P. Amodio et al., Numer. Linear Algebra Appl., {7} (2000), pp. 275--317] and [B. Garrett and I. Gladwell, J. Comput. Methods Sci. Engrg., {1} (2001), pp. 75--98] and the references therein.