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

ABSTRACT

ABDPACK is a package of FORTRAN programs for the solution of systems of linear equations with the almost block diagonal structure arising in spline collocation at Gaussian points with monomial spline basis functions, when applied to two-point boundary value problems with separated boundary conditions. The package ABBPACK is designed to handle a subclass of such linear systems which have what may be called an almost block bidiagonal structure. Such systems result, for example, when condensation is applied to the full spline collocation linear system. This package may also be used to solve the almost block bidiagonal systems arising in multiple shooting techniques and implicit Runge-Kutta methods for solving two-point boundary value problems. The algorithms implemented in the package are based on an alternate column and row pivoting scheme which avoids most of the fill-in introduced by more commonly used techniques.

REFERENCES

• 1: ASCHER, U , PRUESS, S., AND RUSSELL, R.D. On spline basis selection for solving differential equations. SlAM J. Numer. Anal. 20, 1 (June 1983), 121-142
• 2: G. Bader , U. Ascher, A new basis implementation for a mixed order boundary value ODE solver, SIAM Journal on Scientific and Statistical Computing, v.8 n.4, p.483-500, July 1, 1987 [doi>10.1137/0908047]
• 3: 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]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Standardization

Keywords:
almost block diagonal systems, alternate column and row pivoting, implicit Runge-Kutta methods, monomial spline basis, multiple shooting, spline collocation at Gaussian points