%A Hull, T. E.
%A Enright, Wayne H.
%A Jackson, K. R.
%T Runge-Kutta Research at Toronto
%D March 1, 1996
%R CS-NA-96
%I University of Toronto, DCS - Numerical Analysis group.
%U ftp://ftp.cs.toronto.edu/pub/reports/na/rk.survey.96.ps.Z
%X The main purpose of this paper is to summarize the work on Runge-Kutta
methods at the University of Toronto during the period 1963 to the
present. To provide some background, brief mention is also made of
related work on the numerical solution of ordinary differential
equations, but, with just a few exceptions, specific references are
given only if the referenced material has a direct bearing on
Runge-Kutta methods and their application to a variety of problem
areas.
There are several main themes. New Runge-Kutta formulas and new error
control strategies are developed, leading for example to continuous
methods and to new application areas such as delay, differential-
algebraic and boundary value problems. Software design and
implementation are also emphasized. And so is the importance of careful
testing and comparing. Other topics, such as the notion of
effectiveness, taking advantage of parallelism, and handling
discontinuities are also discussed.
%Z Fri, Apr 26 1996 09:16:53 EDT
%A Plexousakis, Dimitris
%T On the Efficient Enforcement of Temporal Integrity in Knowledge Bases
%D August 1, 1996
%R DKBS-TR-96-1
%I University of Toronto DCS - Data and Knowledge Base Systems (DKBS)
%K temporal integrity constraints, transaction specification, process analysis and redesign
%Y H.2.1; I.2.4
%X The maintenance of semantic integrity has been recognized as a
cornerstone issue for the development of databases and knowledge bases
alike. Despite the extensive research conducted during the last two
decades, semantic integrity maintenance has yet to become a practical
technology. Furthermore, the need for modeling evolving domains has
given rise to challenging research issues relating to the incorporation
of time in knowledge bases. In this thesis, we study the problem of
maintaining the integrity of temporal deductive knowledge bases. We
argue that existing approaches in either temporal or deductive databases
do not address the problem in a satisfactory manner, nor do they deal
with all the issues involved in a unified framework. At first, we propose
an assertion language that permits us to express different types of
temporal assertions that are not expressible in other formalisms. We
define the notion of temporal constraint satisfaction in a bitemporal
context. We also show that a syntactic classification of constraints
permits us to exploit structure for deriving simplified forms of
constraints.
We then follow two orthogonal approaches to integrity
maintenance, both using a combination of compile-time and run-time
optimization steps. The former, termed "temporal integrity monitoring",
operates in two phases: compilation and evaluation. The result of the
compilation phase is the derivation of simplified forms of constraints
that suffice to be evaluated at run-time. The evaluation phase performs
additional simplifications with respect to the transactions taking
place at run-time, by combining the previously generated simplified
forms. The latter of the proposals, termed "transaction modification",
delegates the task of integrity maintenance to determinate transactions
specified in terms of precondition/postcondition pairs. It suggests
additions to the transaction's postcondition whose effect is to maintain the
constraints. Both approaches demonstrate that considerable savings can be
incurred by performing compile-time simplifications. The latter approach, in
particular, establishes the theoretical foundations for the development of
a tool that assists the database designer by providing valuable feedback
concerning the safety of transactions. We show how this technique can also
be applied to business process analysis and redesign. Our results
show that these tasks can be assisted by analysis techniques
that possess a firm theoretical basis and are aimed at proving the
design correct according to the designer's intention.
%U ftp://ftp.cs.toronto.edu/pub/dkbs/DKBS-TR-96-1.ps.Z
%Z Tues, Aug 20 1996 09:16:53 GMT
%U ftp://ftp.cs.toronto.edu/pub/reports/na/rk.survey.96.ps.Z
%T Runge-Kutta Research at Toronto
%A Hull T. E.
%A Enright Wayne H.
%A Jackson K. R.
%D March 1, 1996
%X The main purpose of this paper is to summarize the work on Runge-Kutta
methods at the University of Toronto during the period 1963 to the
present. To provide some background, brief mention is also made of
related work on the numerical solution of ordinary differential
equations, but, with just a few exceptions, specific references are
given only if the referenced material has a direct bearing on
Runge-Kutta methods and their application to a variety of problem
areas.
There are several main themes. New Runge-Kutta formulas and new error
control strategies are developed, leading for example to continuous
methods and to new application areas such as delay, differential-
algebraic and boundary value problems. Software design and
implementation are also emphasized. And so is the importance of careful
testing and comparing. Other topics, such as the notion of
effectiveness, taking advantage of parallelism, and handling
discontinuities are also discussed.
%U ftp://ftp.cs.toronto.edu/pub/reports/na/zuberi-96-msc.ps.Z
%T Improving the Efficiency of Runge-Kutta Methods for the Solution of BVPs for Higher-Order ODEs
%A Khalid Zuberi
%D January 1996
%X
Runge-Kutta methods are often used to solve two-point boundary value
problems (BVPs) for ordinary differential equations (ODEs.) These
methods are usually applied directly to first-order systems; to solve
problems for higher-order ODEs, the differential equations are often
reduced to an equivalent first-order system. We exploit the structure
of the reduced system to construct an approximate Jacobian matrix that
is significantly cheaper to construct for general higher order BVPs.
Second-order ODEs are examined in detail, and a specialised linear
system solver is suggested to provide additional computational savings.
Numerical results on sample BVPs for second-order ODEs show significant
computational savings with no loss of solution accuracy.
%U ftp://ftp.cs.toronto.edu/pub/reports/na/hayashi-96-phd.ps.Z
%T Numerical Solution of Retarded and Neutral Delay Differential Equations using Continuous Runge-Kutta Methods
%A Hiroshi Hayashi
%D 1996
%X
In this thesis, we present a numerical method for solving delay
differential equations (DDEs) and analysis for the numerical solution.
We have developed the method by adapting recently developed techniques
for initial value ordinary differential equations and developing a new
approach to handle vanishing delays. We determine convergence
properties for the numerical solution associated with our method. We
first analyze such properties for retarded type DDEs and then the
analysis is extended to the case of neutral type DDEs. We have
developed an experimental Fortran code as a modified version of DVERK
based on a 6th order continuous Runge-Kutta formula. An implementation
of our method is described and numerical results for various kinds of
DDEs are presented.
%U ftp://ftp.cs.toronto.edu/pub/reports/na/nguyen-95-phd.ps.Z
%T Interpolation and Error Control Schemes for Algebraic Differential Equations Using Continuous Implicit Runge-Kutta Methods
%A Hung Nguyen
%D 1995
%X
This thesis presents alternative interpolation and error control schemes for
index 1, index 2 and index 3 algebraic differential equations. We develop
three corresponding schemes with interpolants based on the "bootstrapping"
procedure and error controls based on the defect and algebraic residual of an
underlying perturbed initial value problem. The test problems we use to
illustrate our approach are the classical pendulum problem, the seven body
problem and the driven cavity problem. The three implicit continuous
Runge-Kutta formulas used as examples in our investigation are SDIRK(2),
Gauss(2) and Gauss(3).
%U ftp://ftp.cs.toronto.edu/pub/reports/na/mol.95.ps.Z
%T The numerical solution of large systems of stiff IVPs for ODEs
%A K. R. Jackson
%D Sept. 1995
%X
The application of the method of lines to a system of time-dependent
partial differential equations gives rise to a system of initial-value
problems (IVPs) for ordinary differential equations (ODEs). Such
systems are often stiff and very large. The need to solve problems of
this kind has affected the development of both formulas and codes for
IVPs for ODEs. We survey some of these developments in this article.
%U ftp://ftp.cs.toronto.edu/pub/reports/na/high-order-BVP.ps.Z
%T Improving performance when solving high order and mixed order boundary value problems in ODEs
%A Wayne H. Enright
%A Min Hu
%D March 1995
%X
Solving high order or mixed order boundary value problems by general
purpose software often requires the system to be first converted to
a larger equivalent first order system. The cost of solving such
problems is generally $O(m^3)$ where $m$ is the dimension of the
equivalent first order system. In this paper, we show how to reduce
this cost by exploiting the special structure the `equivalent' first
order system inherits from the original associated mixed-order
system. This technique applies to a broad class of boundary value methods.
We illustrate the potential benefits by considering in detail a general
purpose Runge-Kutta method and a multiple shooting method.
%U ftp://ftp.cs.toronto.edu/pub/reports/na/hayes-95-msc/thesis.ps.Z
%T Efficient Shadowing of High Dimensional Chaotic Systems with the Large Astrophysical N-body Problem as an Example
%A Wayne Hayes
%D January 1995
%X N-body systems are chaotic. This means that numerical errors in their
solution are magnified exponentially with time, perhaps making the
solutions useless. Shadowing tries to show that numerical solutions of
chaotic systems still have some validity. A previously published
shadowing refinement algorithm is optimized to give speedups of order
60 for small problems and asymptotic speedups of O(N) on large
problems. This optimized algorithm is used to shadow N-body systems
with up to 25 moving particles. Preliminary results suggest that
average shadow length scales roughly as 1/N, i.e., shadow lengths
decrease rapidly as the number of phase-space dimensions of the system
is increased. Some measures of simulation error for N-body systems are
discussed that are less stringent than shadowing. Many areas of
further research are discussed both for high-dimensional shadowing, and
for N-body measures of error.
%U ftp://ftp.cs.toronto.edu/pub/reports/na/hayes-95-msc/errata.ps.Z
%T Erratta: Efficient Shadowing of High Dimensional Chaotic Systems with the Large Astrophysical N-body Problem as an Example
%A Wayne Hayes
%D January 1995
%X Errata for thesis: ftp://ftp.cs.toronto.edu/pub/reports/na/hayses-95-msc/thesis.ps.Z
%U ftp://ftp.cs.toronto.edu/pub/reports/na/dimsem.prelim.ps.Z
%T DIMSEMs --- Diagonally Implicit Single-Eigenvalue Methods for the Numerical Solution of Stiff ODEs on Parallel Computers: A Preliminary Report
%A Enenkel R. F.
%A Jackson K. R.
%D January 1995
%X
We describe a new class of General Linear Methods (GLMs) with the
following properties: the methods are strictly diagonally implicit,
allowing efficient parallel implementation; the stability matrix has no
spurious eigenvalues (i.e., only one eigenvalue of the stability matrix
is non-zero); the methods have high stage order, allowing them to
retain their order on problems for which order reduction might
otherwise be a problem; the methods are L-stable, making them suitable
for the solution of stiff problems. As well as presenting some order
barriers, we derive and test methods of orders 2-6.
%U ftp://ftp.cs.toronto.edu/pub/reports/na/prec.except.ps.Z
%T Precision Control and Exception Handling in Scientific Computing
%A K. R. Jackson
%A N. S. Nedialkov
%D 1995
%X
This paper describes convenient language facilities for precision
control and exception handling. Nedialkov has developed a
variable-precision and exception handling library, SciLib, implemented
as a numerical class library in C++. A new scalar data type, real, is
introduced, consisting of variable-precision floating-point numbers.
Arithmetic, relational, and input and output operators of the language
are overloaded for reals, so that mathematical expressions can be
written without explicit function calls. Precision of computations can
be changed during program execution. The exception handling mechanism
treats only numerical exceptions and does not distinguish between
different types of exceptions.
The proposed precision control and exception handling facilities are
illustrated by sample SciLib programs.
%U na/ned-94-msc.ps.Z
%T Precision Control and Exception Handling in Scientific Computing
%A Nedialko Stoyanov Nedialkov
%D Sept. 1994
%X We describe language facilities for precision control and
exception handling and show how they can help to construct better
numerical algorithms.
Precision of computations can be changed during program execution. The
first two precisions are IEEE single and double. Increasing the
precision provides at least two times more significant digits while the
exponent range is significantly larger than double the exponent range
of the previous precision.
The exception handling mechanism treats only numerical exceptions and
does not distinguish between different types of numerical exceptions.
A variable-precision and exception handling library, SciLib, has been
implemented in C++. A new scalar data type real is introduced
consisting of variable-precision floating-point numbers. Arithmetic,
relational, input and output operators of the language are overloaded
for the real data type, so it can be used like any other scalar data
type of C++.
The proposed precision control and exception handling are illustrated
using SciLib. The examples show the benefits of using precision control
to handle exceptions and to avoid catastrophic cancelations.
%U na/cs-94-292.ps.Z
%T Interpolating Runge-Kutta methods for vanishing delay differential equations.
%R Technical report 292/94, Dept. Computer Science, Univ. of Toronto
%A Wayne H. Enright and Min Hu
%A Wayne H. Enright and Min Hu
%D 1994
%X In the numerical solution of delay differential equations by a continuous
explicit Runge-Kutta method a difficulty arises when the delay vanishes
or becomes smaller than the stepsize the method would like to use. In
this situation the standard explicit sequential process of computing the
Runge-Kutta stages become an implicit process and an iteration scheme
must be adopted. We will consider several alternative iteration schemes
and investigate their order.
%U na/imacs.94.ps.Z
%T An Application of Runge-Kutta Predictor-Corrector Methods To Two System of Hyperbolic Equations Arising in Optics
%A K. R. Jackson
%D July 1994
%X none
%U na/cs-94-291.ps.Z
%T A Survey of the Explicit Runge-Kutta Method.
%R Technical report 291/94, Dept. Computer Science, Univ. of Toronto
%A Wayne H. Enright,
%A Desmond J. Higham,
%A Brynjulf Owren
%A Philip W. Sharp
%D April 1995
%X Research in explicit Runge-Kutta methods is producing continual improvements to
the original algorithms, and the aim of this survey is to relate the current
state-of-the-art. In drawing attention to recent advances, we hope to provide
useful information for those who apply numerical methods.
We describe recent work in the derivation of Runge-Kutta coefficients:
``classical'' general-purpose formulas, ``special'' formulas for high order and
Hamiltonian problems, and ``continuous'' formulas for dense output. We also
give a thorough review of implementation details. Modern techniques are
described for the tasks of controlling the local error in a step-by-step
integration, computing reliable estimates of the global error, detecting
stiffness, and detecting and handling discontinuities and singularities. We
also discuss some important software issues.
%U na/tr-94-1.ps.Z
%T An Analysis of the Order of Runge-Kutta Methods That Use an Iterative Scheme To Compute Their Internal Stage Values
%A K. R. Jackson, A. Kvaerno and S. P. Norsett
%A K. R. Jackson, A. Kvaerno and S. P. Norsett
%A K. R. Jackson, A. Kvaerno and S. P. Norsett
%D May 1994
%X
We employ B-series to analyze the order of Runge-Kutta (RK) methods
that use simple iteration, modified Newton iteration or full Newton
iteration to compute their internal stage values. Our assumptions
about the initial guess for the internal stage values cover a wide
range of practical schemes. Moreover, the analytical techniques
developed in this paper can be applied in many other similar contexts.
%U na/hull-mathon-math-basis.ps.Z
%T The Mathematical Basis for a New Polynomial Rootfinder with Quadratic Convergence
%D 1994
%A T. E. Hull and R. Mathon
%A T. E. Hull and R. Mathon
%X
Formulas developed originally by Weierstrass have been used since the
1960's by many others for the simultaneous determination of all the
roots of a polynomial. Convergence to simple roots is quadratic, but
individual approximations to a multiple root converge only linearly.
However, it is shown here that the mean of such individual
approximations converges quadratically to that root. This result,
along with some detail about the behavior of such approximations in the
neighborhood of the multiple root, suggests a new approach to the
design of a polynomial rootfinder.
This paper first provides the relevant mathematical results: a short
derivation of the formulas, convergence proofs, an indication of the
behavior near a multiple root, and finally some error bounds. It then
provides the outline of an algorithm based on these results, along with
some preliminary experimental results to illustrate the major points,
and to demonstrate some of the potential for a future software
package. It should also be noted that the method is well-suited to
take advantage of a parallel environment.
%U na/joqe-1.ps.Z
%T Coupled Mode Equations with Free Carrier Effects: A Numerical Solution,
%A N. G. R. Broderick, C. M. de Sterke and K. R. Jackson
%A N. G. R. Broderick, C. M. de Sterke and K. R. Jackson
%A N. G. R. Broderick, C. M. de Sterke and K. R. Jackson
%D May 1993
%X
We present a numerical method for solving a set of coupled mode
equations describing light propagation through a medium with a grating
and free carriers. The carriers, which are excited by the light and
decay exponentially, lower the refractive index, thus rendering the
system nonlinear. The method is fourth-order accurate, efficient,
stable, easy to implement and well suited for vector and parallel
computers. In addition, it can be extended to handle diffusive carrier
effects.
%U na/anm-1.ps.Z
%T The Use of Butcher Series in the Analysis of Newton-Like Iterations in Runge-Kutta Formulas
%A K. R. Jackson, A. Kvaerno and S. P. Norsett
%A K. R. Jackson, A. Kvaerno and S. P. Norsett
%A K. R. Jackson, A. Kvaerno and S. P. Norsett
%D April 1993
%X We consider the numerical solution of initial value problems for both
ordinary differential equations and differential-algebraic equations by
Runge-Kutta (RK) formulas. We assume that the internal stage values of
the RK formula are computed by some iterative scheme for solving
nonlinear equations, such as Newton's method. Using Butcher series and
rooted trees, we give a complete characterization of the local error in
the RK formula after k iterations of the scheme. Results are given
for three specific schemes: simple iteration, the modified Newton
iteration, and the full Newton iteration. The ideas developed in this
paper, however, are easily applied to other iterative schemes of this
kind.
%U na/cs-93-267.ps.Z
%T A Runge-Kutta Type Boundary Value ODE Solver with Defect Control
%A W.H. Enright and Paul Muir
%A W.H. Enright and Paul Muir
%D June 1993
%X A popular approach for the numerical solution of boundary value ODE problems
involves the use of collocation methods. Such methods can be naturally
implemented so as to provide a continuous approximation to the solution over
the entire problem interval. On the other hand, several authors have suggested
as an alternative, certain subclasses of the implicit Runge-Kutta formulas,
known as mono-implicit Runge-Kutta (MIRK) formulas, which can be implemented
substantially more efficiently than the collocation methods. These latter
formulas do not have a natural implementation that provides a continuous
approximation to the solution; rather only a discrete approximation at certain
points within the problem interval is obtained. However recent work in the
area of initial value problems has demonstrated the possibility of generating
inexpensive interpolants for any explicit Runge-Kutta formula. These ideas have
recently been extended to develop interpolants for the MIRK formulas. In this
paper, we describe our investigation of the use of continuous MIRK formulas in
a code for the numerical solution of boundary value ODE problems. A primary
thrust of this investigation is to consider defect control, based on these
interpolants, as an alternative to the standard use of global error estimates,
as the basis for termination and mesh redistribution criteria.
%U na/cmplx-elem-fcns.ps.Z
%T Implementing Complex Elementary Functions Using Exception Handling
%A T. E. Hull, Thomas F. Fairgrieve and Ping Tak Peter Tang
%A T. E. Hull, Thomas F. Fairgrieve and Ping Tak Peter Tang
%A T. E. Hull, Thomas F. Fairgrieve and Ping Tak Peter Tang
%X We develop algorithms for reliable and accurate evaluations of the complex
elementary functions required in Fortran 77 and Fortran 90, namely cabs, csqrt,
cexp, clog, csin and ccos. The algorithms are presented in a pseudo-code
which has convenient exception handling facilities. A tight error bound is
derived for each algorithm. Corresponding Fortran programs for an IEEE
environment have also been developed to illustrate the practicality of the
algorithms, and these programs have been tested very carefully to help confirm
the correctness of the algorithms and their error bounds --- the results of
these tests are included in the paper, but the Fortran programs are not.
%U na/cs-92-261.ps.Z
%T The Practical Implications of Order Reduction on the Solution of Stiff Initial Value Problems using Runge-Kutta Formulas.
%R Technical report 261/92, Dept. Computer Science, Univ. of Toronto
%A C. MacDonald and W. Enright
%A C. MacDonald and W. Enright
%D June 1993
%X
Stability analysis of Runge-Kutta (RK) formulas was originally limited
to linear ordinary differential equations (ODEs). More recently such
analysis has been extended to include the behaviour of solutions to
non-linear problems. This extension led to additional stability
requirements for RK methods. Although the class of problems has been
widened, the analysis is still restricted to a fixed stepsize. In the
case of differential algebraic equations (DAEs), additional order
conditions must be satisfied to achieve full classical ODE order and
avoid possible `order reduction'. In this case too, a fixed stepsize
analysis is employed. Such analysis may be of only limited use in
quantifying the effectiveness of adaptive methods on stiff problems.
In this paper we examine the phenomenon of `order reduction' and its
implications on variable-step algorithms. We introduce a global
measure of order referred to here as the `observed order' which is
based on the average stepsize over the region of integration. This
measure may be better suited to the study of stiff systems, where
the stepsize selection algorithm will vary the stepsize considerably
over the interval of integration. Observed order gives a better
indication of the relationship between accuracy and cost. Using
this measure, the `observed order reduction' will be seen to be less
severe than that predicted by fixed stepsize order analysis.
%U na/cs-91-255.ps.Z
%T The Parallel Solution of ABD Systems Arising in Numerical Methods for BVPs for ODEs
Ref: Technical report 255/91, Dept. Computer Science, Univ. of Toronto
%A K. R. Jackson and R. N. Pancer
%A K. R. Jackson and R. N. Pancer
%D May 1992
%X
Many commonly used numerical methods for the solution of Boundary Value
Problems (BVPs) for Ordinary Differential Equations (ODEs) contain
significant components that can be parallelized easily, and recent
investigations have shown that substantial speedups are attainable on
machines with a modest number of processors. However, a stage in most
of these methods is the numerical solution of an "Almost Block
Diagonal" (ABD) system of linear algebraic equations. Several authors
have proposed parallel algorithms for solving such systems;
unfortunately most are potentially unstable or offer only limited
parallelism. As a result, solving ABD systems has proven to be a
bottleneck in the overall execution time of parallel BVP codes.
In recent papers, Wright presents new stable parallel algorithms for
solving ABD systems. Each algorithm attains the theoretically optimal
speedup for the problem if enough processors are available, and each
can be adapted for use on architectures with fewer than the optimal
number of processors. The algorithms in Section 3 of this paper were
discovered independently and are similar to those investigated by
Wright. Extensions to the basic algorithm are described which make
better use of available processors during the decomposition stage in
order to increase parallelism in the back-solve stage.
A new algorithm based on "eigenvalue rescaling" is presented in Section 4
which can be up to twice as fast as the fastest algorithm in Section 3.
Numerical experiments show that this new algorithm does not exhibit the
instability inherent in some earlier schemes. In addition, some
insight supporting the numerical evidence is given.
%U na/imsl-9005.ps.Z
%T Using the IMSL MATH/LIBRARY in Numerical Methods Courses
Ref: IMSL Technical Report Series, No. 9005
%A K. R. Jackson and T. E. Hull
%A K. R. Jackson and T. E. Hull
%D 1990
%X This article describes our experience using the IMSL MATH/LIBRARY
in five numerical methods classes taught to engineering students at the
University of Toronto during the 1987-88 and 1988-89 academic years.
%U na/osa-1.ps.Z
%T Nonlinear coupled mode equations on a finite interval: a numerical procedure
%R J. Optical Society of America B, Vol 8, No 2, Feb 1991, pp. 403-412.
%A C. M. de Sterke, K. R. Jackson and B. D. Robert
%A C. M. de Sterke, K. R. Jackson and B. D. Robert
%A C. M. de Sterke, K. R. Jackson and B. D. Robert
%D 1991
%X
We present a numerical procedure to solve a set of nonlinear coupled
mode equations on a finite interval. These equations originally arose
in the study of the dynamics of gap solitons in nonlinear periodic
media. Our procedure, which makes use of an implicit fourth-order
Runge-Kutta method, is easy to implement, versatile, and very well
suited for vectorization or parallelization.
%U na/ieee-trans-mag-1.ps.Z
%T A Survey of Parallel Numerical Methods for Initial Value Problems for Ordinary Differential Equations
%R IEEE Transactions on Magnetics, 27 (1991), pp. 3792-3797.
%A K. R. Jackson
%D 1991
%X The parallel solution of Initial Value Problems for Ordinary
Differential Equations has become an active area of research during the
past few years. We briefly survey the recent developments in this
area, with particular emphasis on traditional forward-step methods that
offer the potential for effective small-scale parallelism on currently
existing machines.
%U na/cs-91-258.ps.Z
%T Order Barriers and Characterizations for Continuous Mono-Implicit Runge-Kutta Schemes
%R Technical report 258/91, Dept. Computer Science, Univ. of Toronto
%A Paul Muir
%A Brynjulf Owren
%D Dec. 1991
%X The mono-implicit Runge-Kutta (MIRK) schemes, a subset of the family of
implicit Runge-Kutta (IRK) schemes, were originally proposed for the
numerical solution of initial value ODE's more than fifteen years ago.
During the last decade, there has been considerable investigation of
the use of these schemes in the numerical solution of boundary value ODE
problems, where their efficient implementation suggests that they may
provide a worthwhile alternative to the widely used collocation schemes.
In fact, recent work in this area has seen the development of some
software packages for boundary value ODE's based on these schemes.
Unfortunately, these schemes lead to algorithms which provide only a
discrete solution approximation at a set of mesh points over the problem
interval, while the collocation schemes provide a natural continuous
solution approximation. The availability of a continuous solution is
important not only to the user of the software but also within the code
itself, for example, in estimation of errors, defect control, mesh
selection, and the provision of initial solution estimates for new meshes.
An approach for the construction of a continuous solution approximation
based on the MIRK schemes is suggested by recent work in the area of
continuous extensions for explicit Runge-Kutta schemes for initial value
ODE's. In this paper, we describe our work in the investigation of
continuous versions of the MIRK schemes:
(i) we give some lower bounds relating the stage order to the minimal
number of stages for general IRK schemes,
(ii) we establish lower bounds on the number of stages needed to derive
continuous MIRK schemes of orders 1 through 6,
(iii) we provide characterizations of such schemes having a minimal
number of stages for each of these orders.
%U na/uw-cs-91-33.ps.Z
%T Adaptive Linear Equation Solvers in Codes for Large Stiff Systems of ODEs
%R Research Report CS-91-33, Department of Computer Science,
%I University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1.
%A K. R. Jackson
%A W. L. Seward
%D July 1991
%X
Iterative linear equation solvers have been shown to be effective
in codes for large systems of stiff initial-value problems
for ordinary differential equations (ODEs).
While preconditioned iterative methods are required in general
for efficiency and robustness, unpreconditioned methods may
be cheaper over some ranges of the interval of integration.
In this paper,
we develop a strategy for switching between unpreconditioned
and preconditioned iterative methods depending on the amount
of work being done in the iterative solver and properties
of the matrix being solved.
This strategy is combined with a ``type-insensitive'' approach
to the choice of formula used in the ODE code to develop
a method that makes a smooth transition between nonstiff and
stiff regimes in the interval of integration.
We find that, as expected, for some large systems of ODEs, there may be a
considerable saving in execution time when the type-insensitive
approach is used.
If there is a region of the integration that is ``mildly'' stiff,
switching between unpreconditioned and preconditioned iterative
methods also increases the efficiency of the code significantly.
%U na/cs-90-240.ps.Z
%T Derivation of Efficient Continuous Explicit Runge-Kutta Methods. Technical report 240/90, Dept. Computer Science, Univ. of Toronto
%A Owren B.
%A Zennaro M.
%X Continuous Explicit Runge-Kutta methods with the minimal number of
stages are considered. These methods are continuously differentiable
if and only if one of the stages is the FSAL evaluation. A
characterization of a subclass of these methods is developed
for order 3,4 and 5. It is shown how the free parameters of these
methods can be used either to minimize the continuous truncation
error coefficients or to maximize the stability region. As a
representative for these methods the 5th order method with minimized
error coefficients is chosen, supplied with an error estimation method,
and analysed by using the DETEST software. The results are compared with
a similar implementation of the Dormand-Prince 5(4) pair with
interpolant, showing a significant advantage to the new method for the
chosen problems.
%U na/cs-90-239.ps.Z
%T The Potential for Parallelism in Runge-Kutta Methods. Part 1: RK Formulas in Standard Form.
%R Technical report 239/90, Dept. Computer Science, Univ. of Toronto
%A Jackson, K. R.
%A Norsett, S. P.
%D November 1990
%X We examine the potential for parallelism in Runge-Kutta (RK) methods
based on formulas in standard one-step form. Both negative and
positive results are presented. Many of the negative results are based
on a theorem that bounds the order of a RK formula in terms of the
minimum polynomial for its coefficient matrix. The positive results
are largely examples of prototypical formulas which offer a potential
for effective ``coarse-grain'' parallelism on machines with a few
processors.