A Matlab package for automatically generating Runge-Kutta trees, order conditions, and truncation error coefficients

ABSTRACT

In designing parts of Runge-Kutta methods, order conditions and truncation error coefficients (TECs) are needed. Order conditions and TECs are typically presented as a set of trees combined with rules for producing algebraic expressions from the trees. The tree sets are defined recursively and can be generated by hand only for low orders. This article describes a package of Matlab routines for automatically generating Runge-Kutta trees, order conditions, and TECs. The routines are capable of generating Maple code, Matlab code, or LaTeX expressions for ODEs or DAEs of index 1 and 2. In producing the package, two theoretical problems are tackled: (a) avoiding the repeated generation of the same tree and (b) the efficient storage of TECs.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: A. Aubry , P. Chartier, On Improving the Convergence of Radau IIA Methods Applied to Index 2 DAEs, SIAM Journal on Numerical Analysis, v.35 n.4, p.1347-1367, Aug. 1, 1998 [doi>10.1137/S0036142995296539]
• 3: Bogacki, P. and Shampine, L. F. 1989. A 3(2) pair of Runge-Kutta formulas. Appl. Math. Lett. 2, 321--325.
• 4: Cameron, F. 1999. Low-order Runge-Kutta methods for differential-algebraic equations. Ph.D. thesis, Tampere University of Technology, Tampere, Finland.
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: Famelis, I. T., Papakostas, S., and Tsitouras, C. 2004. Symbolic derivation of Runge-Kutta order conditions. J. Symbol. Comp. 37, 311--327.
• 7: Hairer, E., Lubich, C., and Roche, M. 1989. The Numerical Solution of Differential-Algebraic Systems by Runge-Kutta Methods. Lecture Notes in Mathematics, 1409, Springer, Berlin, Germany.
• 8: E. Hairer , S. P. Nørsett , G. Wanner, Solving ordinary differential equations I (2nd revised. ed.): nonstiff problems, Springer-Verlag New York, Inc., New York, NY, 1993
• 9: Inmaculada Higueras, Coefficients of the Taylor expansion for the solution of differential-algebraic systems, Applied Numerical Mathematics, v.12 n.6, p.497-501, Aug. 1993 [doi>10.1016/0168-9274(93)90066-Z ]
• 10: M. E. Hosea, A new recurrence for computing Runge-Kutta truncation error coefficients, SIAM Journal on Numerical Analysis, v.32 n.6, p.1989-2001, Dec. 1995 [doi>10.1137/0732089]
• 11: Kværnø, A. 1990. Runge-Kutta methods applied to fully implicit differential-algebraic equations of index 1. Math. Comput. 54, 583--625.
• 12: Murua, A. 1999a. Formal series and numerical integrators, part i: Systems of odes and symplectic integrators. Appl. Numer. Math. 29, 221--251.
• 13: A. Murua, Formal series and numerical integrators, Part II: application to index-2 differential-algebraic systems, Applied Numerical Mathematics, v.29 n.1, p.99-113, Jan. 1999
• 14: Hans Olsson , Gustaf Söderlind, Stage Value Predictors and Efficient Newton Iterations in Implicit Runge--Kutta Methods, SIAM Journal on Scientific Computing, v.20 n.1, p.185-202, Aug. 1998 [doi>10.1137/S1064827596306963]
• 15: Michel Roche, Implicit Runge-Kutta methods for differential algebraic equations, SIAM Journal on Numerical Analysis, v.26 n.4, p.963-975, August 1989 [doi>10.1137/0726053]
• 16: Teo Roldán , Inmaculada Higueras, IRK methods for DAE: starting algorithms, Journal of Computational and Applied Mathematics, v.111 n.1-2, p.77-92, Nov. 15, 1999
• 17: M. Sofroniou, Symbolic derivation of Runge-Kutta methods, Journal of Symbolic Computation, v.18 n.3, p.265-296, Sept. 1994 [doi>10.1006/jsco.1994.1048 ]
• 18: Sofroniou, M. and Spaletta, G. 2003. On the construction of a new generalization of Runge-Kutta methods. Electron. Notes in Theor. Comp. Sci. 74, 1--18.
• 19: The Math Works Inc. 1999. Using Matlab, Version 5. The Math Works Inc.
• 20: Verner, J. H. 1978. Explicit Runge-Kutta methods with estimates of the local truncation error. SIAM J. Numer. Anal. 15, 772--790.
• 21: J. H. Verner, High-order explicit Runge-Kutta pairs with low stage order, Applied Numerical Mathematics, v.22 n.1-3, p.345-357, Nov. 1996 [doi>10.1016/S0168-9274(96)00041-4 ]
• 22: Wright, W. 2002. General linear methods with inherent Runge-Kutta stability. Ph.D. thesis, Univ. of Auckland, Auckland, New Zealand.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Differential-algebraic equations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Error analysis; One-step (single step) methods; Initial value problems
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design

Keywords:
Automatic code generation, Runge-Kutta methods, order conditions, truncation error coefficients