Systematic construction of efficient six-stage fifth-order explicit Runge-Kutta embedded pairs without standard simplifying assumptions
Date
2019-01-28
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
ORCID
0000-0002-4992-965X
Type
Thesis
Degree Level
Doctoral
Abstract
This thesis examines methodologies and software to construct explicit
Runge-Kutta (ERK) pairs for solving initial value problems (IVPs) by
constructing efficient six-stage fifth-order ERK pairs without
standard simplifying assumptions. The problem of whether efficient
higher-order ERK pairs can be constructed algebraically without the
standard simplifying assumptions dates back to at least the 1960s,
with Cassity's complete solution of the six-stage fifth-order order
conditions. Although RK methods based on the six-stage fifth-order
order conditions have been widely studied and have continuing
practical importance, prior to this thesis, the aforementioned
complete solution to these order conditions has no published usage
beyond the original series of publications by Cassity in the 1960s.
The complete solution of six-stage fifth-order ERK order conditions
published by Cassity in 1969 is not in a formulation that can easily
be used for practical purposes, such as a software implementation.
However, it is shown in this thesis that when the order conditions are
solved and formulated appropriately using a computer algebra system
(CAS), the generated code can be used for practical purposes and the
complete solution is readily extended to ERK pairs. The condensed
matrix form of the order conditions introduced by Cassity in 1969 is
shown to be an ideal methodology, which probably has wider
applicability, for solving order conditions using a CAS. The software
package OCSage developed for this thesis, in order to solve the order
conditions and study the properties of the resulting methods, is built
on top of the Sage CAS.
However, in order to effectively determine that the constructed ERK
pairs without standard simplifying assumptions are in fact efficient
by some well-defined criteria, the process of selecting the
coefficients of ERK pairs is re-examined in conjunction with a
sufficient amount of performance data. The pythODE software package
developed for this thesis is used to generate a large amount of
performance data from a large selection of candidate ERK pairs found
using OCSage. In particular, it is shown that there is unlikely to be
a well-defined methodology for selecting optimal pairs for
general-purpose use, other than avoiding poor choices of certain
properties and ensuring the error coefficients are as small as
possible. However, for IVPs from celestial mechanics, there are
obvious optimal pairs that have specific values of a small subset of
the principal error coefficients (PECs). Statements seen in the
literature that the best that can be done is treating all PECs equally
do not necessarily apply to at least some broad classes of IVPs. By
choosing ERK pairs based on specific values of individual PECs, not
only are ERK pairs that are 20-30% more efficient than comparable
published pairs found for test sets of IVPs from celestial mechanics,
but the variation in performance between the best and worst ERK pairs
that otherwise would seem to have similar properties is reduced from a
factor of 2 down to as low as 15%. Based on observations of the small
number of IVPs of other classes in common IVP test sets, there are
other classes of IVPs that have different optimal values of the PECs.
A more general contribution of this thesis is that it specifically
demonstrates how specialized software tools and a larger amount of
performance data than is typical can support novel empirical insights
into numerical methods.
Description
Keywords
numerical methods, ordinary differential equations, explicit Runge-Kutta, simplifying assumptions, computer algebra, numerical experimentation, Python, Sage, software
Citation
Degree
Doctor of Philosophy (Ph.D.)
Department
Computer Science
Program
Computer Science