The solution of almost block diagonal linear systems arising in spline collocation at Gaussian points with monomial basis functions

ABSTRACT

Numerical techniques based on piecewise polynomial (that is, spline) collation at Gaussian points are exceedingly effective for the approximate solution of boundary value problems, both for ordinary differential equations and for time dependent partial differential equations. There are several widely available computer codes based on this approach, all of which have at their core a particular choice of basis representation for the piecewise polynomials used to approximate the solutions. Until recently, the most popular approach was to use a B-spline representation, but it has been shown that the B-spline basis is inferior, both in operation counts and conditioning, to a certain monomial basis, and the latter has come more into favor. In this paper, we describe a linear algebraic equations which arise in spline collocation at Gaussian points with such a monomial basis. It is shown that the new package, which implements an alternate column and row pivoting algorithm, is a distinct improvement over existing packages from the points of view of speed and storage requirements. In addition, we describe a second package, an important special case of the first, for solving the almost block diagonal systems which arise when condensation is applied to the systems arising in spline collocation at Gaussian points, and also in other methods for solving two-point boundary value problems, such as implicit Runge-Kutta methods and multiple shooting.

REFERENCES

• 1: U. Ascher , J. Christiansen , R. D. Russell, Collocation Software for Boundary-Value ODEs, ACM Transactions on Mathematical Software (TOMS), v.7 n.2, p.209-222, June 1981 [doi>10.1145/355945.355950]
• 2: ASCH~R, U., PRUESS, S., AND RUSSELL, R.D. On spline basis selection for solving differential equations. SIAM J. Numer. Anal. 20, I (1983), 121-142.
• 3: 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]
• 4: DE BOOR, C. A Practical Guide to Splines. Springer-Verlag, 1978.
• 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. 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]
• 7: 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]
• 8: DONGARRA, J. J., MOLER, C. B., BUNCH, J. R., AND STEWART, G. W. LINPACK User's Guide. Society for Industrial and Applied Mathematics, Philadelphia, 1979.
• 9: LENTINI, M, OSBORNE, M. R., AND RUSSELL, R.D. The close relationship between methods for solving two-point boundary value problems SIAM J. Numer. Anal. 22, 2 (1985), 280-309.
• 10: MAJAESS, F , AND KEAST, P. Algorithms for the solution of linear systems arising from monomial spline barns functions. Tech. Rep. 1987CS-11, Dept. of Mathematics, Statistics and Computing Science, Dalhousie Univ., Halifax~ Canada
• 11: MAJAESS, F., KEAST, P., FAIRWEATHER, G., AND BENNETT, K. R Fortran packages for the solution of almost block diagonal hnear systems arising in spline collocation at Gaussian points with monomial basis functions Tech. Rep. CCS-90-3, Center for Computational Sciences, Univ. of Kentucky, Lexington, Kentucky.
• 12: 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]
• 13: Mum, P.J. Implicit Runge-Kutta methods for two-point boundary value problems. Ph D. Thesm, Univ of Toronto, Tech. Rep. 175/84, Dept. of Computer Science, Univ. of Toronto, Toronto, Ontario, Canada, M5S 4A7.
• 14: STOER, J_ AND BULmSCH, R. Introduction to Numerical Analysis, Springer-Verlag, 1980.
• 15: VARAH, J. M Alternate row and column elimination for solving certain hnear systems. SIAM J. Numer. Anal. 13, L (1976), 71-75.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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

General Terms:
Algorithms

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