Algorithm 859: BABDCR—a Fortran 90 package for the solution of bordered ABD linear systems

ABSTRACT

BABDCR is a package of Fortran 90 subroutines for the solution of linear systems with bordered almost block diagonal coefficient matrices. It is designed to handle matrices with blocks of the same size, that is, having a block upper bidiagonal structure with an additional block in the right upper corner. The algorithm implemented in the package performs cyclic reduction of the coefficient matrix in order to reduce the fill-in due to the corner block.

REFERENCES

• 1: Amodio, P., Cash, J. R., Roussos, G., Wright, R. W., Fairweather, G., Gladwell, I., Kraut, G. L., and Paprzycki, M. 2000. Almost block diagonal linear systems: Sequential and parallel solution techniques, and applications. Numer. Linear Algebra Appl. 7, 275--317.
• 2: Pierluigi Amodio , Marcin Paprzycki, A Cyclic Reduction Approach to the Numerical Solution of Boundary Value ODEs, SIAM Journal on Scientific Computing, v.18 n.1, p.56-68, January. 1997 [doi>10.1137/S1064827595287225]
• 3: Ascher, U. M., Mattheij, R. M., and Russell, R. D. 1995. Numerical Solution of Boundary Value Problems for Ordinary Differential Equations. Classics in Applied Mathematics 13. SIAM Press, Philadelphia, PA.
• 4: Brankin, R. and Gladwell, I. 1990. Codes for almost block diagonal systems. Comput. Math. Appl. 19, 7, 1--6.
• 5: Carl de Boor , Richard Weiss, SOLVEBLOK: A Package for Solving Almost Block Diagonal Linear Systems, ACM Transactions on Mathematical Software (TOMS), v.6 n.1, p.80-87, March 1980 [doi>10.1145/355873.355880]
• 6: J. C. Díaz , G. and P. Keast, Algorithm 603: COLROW and ARCECO: FORTRAN Packages for Solving Certain Almost Block Diagonal Linear Systems by Modified Alternate Row and Column Elimination, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.376-380, Sept. 1983 [doi>10.1145/356044.356054]
• 7: J. C. Diaz , G. Fairweather , P. Keast, FORTRAN Packages for Solving Certain Almost Block Diagonal Linear Systems by Modified Alternate Row and Column Elimination, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.358-375, Sept. 1983 [doi>10.1145/356044.356053]
• 8: Fairweather, G. and Gladwell, I. 2004. Algorithms for almost block diagonal linear systems. SIAM Rev. 46, 1, 49--58.
• 9: Garrett, B. and Gladwell, I. 2001. Solving bordered almost block diagonal systems stably and efficiently. J. Comput. Meth. Sci. Eng. 1, 75--98.
• 10: Nicholas J. Higham, ALGORITHM 674: Fortran codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation, ACM Transactions on Mathematical Software (TOMS), v.15 n.2, p.168, June 1989 [doi>10.1145/63522.214391]
• 11: Lam, D. 1974. Implemantation of the box scheme and model analysis of diffusion---convenction equations. Ph.D. thesis, University of Waterloo, Waterloo, Canada.
• 12: Lentini, M. and Pereyra, V. 1977. An adaptive finite difference solver for nonlinear two-point boundary problems with mild boundary layers. SIAM J. Numer. Anal. 14, 91--111.
• 13: Fouad Majaess , Patrick Keast , Graeme Fairweather , Karin R. Bennett, Algorithm 704; ABDPACK and ABBPACK-FORTRAN programs for the solution of almost block diagonal linear systems arising in spline collocation at Gaussian points with monomial basis functions, ACM Transactions on Mathematical Software (TOMS), v.18 n.2, p.205-210, June 1992 [doi>10.1145/146847.146927]
• 14: Gouad Majaess , Patrick Keast , Graeme Fairweather , Karin R. Bennett, The solution of almost block diagonal linear systems arising in spline collocation at Gaussian points with monomial basis functions, ACM Transactions on Mathematical Software (TOMS), v.18 n.2, p.193-204, June 1992 [doi>10.1145/146847.146926]
• 15: P. H. Muir , R. N. Pancer , K. R. Jackson, PMIRKDC: a parallel mono-implicit Runge--Kutta code with defect control for boundary value ODEs, Parallel Computing, v.29 n.6, p.711-741, June 2003 [doi>10.1016/S0167-8191(03)00038-3]
• 16: Varah, J. 1976. Alternate row and column elimination for solving certain linear systems. SIAM J. Numer. Anal. 13, 71--75.
• 17: Stephen J. Wright, Stable parallel algorithms for two-point boundary value problems, SIAM Journal on Scientific and Statistical Computing, v.13 n.3, p.742-764, May 1992 [doi>10.1137/0913044]
• 18: Stephen J. Wright, A collection of problems for which Gaussian elimination with partial pivoting is unstable, SIAM Journal on Scientific Computing, v.14 n.1, p.231-238, Jan. 1993 [doi>10.1137/0914013]
• 19: Wright, S. 1994. Stable parallel elimination for boundary value odes. Numer. Math. 67, 4, 521--535.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis; Documentation

Keywords:
Linear systems, bordered almost block diagonal matrices, cyclic reduction, numerical solution