%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.