Abstract
How can small-scale parallelism best be exploited in the solution of nonstiff initial value problems? It is generally accepted that only modest gains inefficiency are possible, and it is often the case that “fast” parallel algorithms have quite crude error control and stepsize selection components. In this paper we consider the possibility of using parallelism to improvereliability andfunctionality rather than efficiency. We present an algorithm that can be used with any explicit Runge-Kutta formula. The basic idea is to take several smaller substeps in parallel with the main step. The substeps provide an interpolation facility that is essentially free, and the error control strategy can then be based on a defect (residual) sample. If the number of processors exceeds (p − 1)/2, wherep is the order of the Runge-Kutta formula, then the interpolant and the error control scheme satisfy very strong reliability conditions. Further, for a given orderp, the asymptotically optimal values for the substep lengths are independent of the problem and formula and hence can be computed a priori. Theoretical comparisons between the parallel algorithm and optimal sequential algorithms at various orders are given. We also report on numerical tests of the reliability and efficiency of the new algorithm, and give some parallel timing statistics from a 4-processor machine.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bryant, P. J.:Nonlinear wave groups in deep water, Studies in Applied Mathematics (1979), 1–30.
Burrage, K.:Solving nonstiff IVPs in a transputer environment, Manuscript (1990), CMSR, University of Liverpool, U.K.
Cash, J. R.:A block 6(4) Runge-Kutta formula for nonstiff initial value problems, ACM Trans. Math. Soft. 15 (1989), 15–28.
Davis, P. J.:Interpolation and Approximation, Dover, New York, 1975.
Dormand, J. R. and Prince, P. J.:Runge-Kutta triples, Comp. and Maths. with Appls. 12 (1986), 1007–1017.
Enright, W. H.:A new error-control for initial value solvers, Applied Maths. and Computation 31 (1989), 288–301.
Enright, W. H.:Analysis of error control strategies for continuous Runge-Kutta methods, SIAM J. Numer. Anal. 26 (1989), 588–599.
Enright, W. H., Jackson, K. R., Nørsett, S. P. and Thomsen, P. G.:Interpolants for Runge-Kutta formulas, ACM Trans. Math. Soft. 12 (1986), 193–218.
Enright, W. H. and Pryce, J. D.:Two FORTRAN packages for assessing initial value methods, ACM Trans. Math. Soft. 13 (1987), 1–27.
Enright, W. H. and Higham, D. J.:Parallel defect control, Technical Report No. 237/90, Department of Computer Science, University of Toronto, Canada (1990).
Gladwell, I.:Initial value routines in the NAG library, ACM Trans. Math. Soft. 5 (1979), 386–400.
Gladwell, I., Shampine, L. F., Baca, L. S. and Brankin, R. W.:Practical aspects of interpolation in Runge-Kutta codes, SIAM J. Sci. Stat. Comput. 8 (1987), 322–341.
Hairer, E., Nørsett, S. P. and Wanner, G.:Solving Ordinary Differential Equations I, Springer-Verlag, Berlin, 1987.
Higham, D. J.:Robust defect control with Runge-Kutta schemes, SIAM J. Numer. Anal. 26 (1989), 1175–1183.
Higham, D. J.:Highly continuous Runge-Kutta interpolants, Technical Report No. 220/89, Department of Computer Science, University of Toronto, Canada (1989); to appear in ACM Trans. Math. Softw.
Higham, D. J.:Runge-Kutta defect control using Hermite-Birkhoff interpolation, Technical Report No. 221/89, Department of Computer Science, University of Toronto (1989); to appear in SIAM J. Sci. Stat. Comput.
Higham, D. J.:Global error versus tolerance for explicit Runge-Kutta methods, Technical Report No. 233/90, Department of Computer Science, University of Toronto, Canada (1990); to appear in IMA J. Numer. Anal.
Houwen, P. J. van der and Sommeijer, B. P.:Variable step iteration of high-order Runge-Kutta methods on parallel computers, Report NM-R8817, Centre for Mathematics and Computer science, Amsterdam, 1988.
Houwen, P. J. van der and Sommeijer, B.P.:Block Runge-Kutta methods on parallel computers, Report NM-R8906, Centre for Mathematics and Computer science, Amsterdam, 1989.
Jackson, K. R. and Nørsett, S. P.:The potential for parallelism in Runge-Kutta methods. Part 1:RK formulas in standard form, Technical Report No. 239/90, Department of Computer Science, University of Toronto, Canada (1990).
Owren, B. and Zennaro, M.:Derivation of efficient continuous explicit Runge-Kutta methods, Technical Report No. 240/90, Department of Computer Science, University of Toronto, Canada (1990).
Shampine, L. F.:Interpolation for Runge-Kutta methods, SIAM J. Numer. Anal. 22 (1985), 1014–1027.
Shampine, L. F.:Some practical Runge-Kutta formulas, Math. Comp. 46 (1986), 135–150.
Sharp, P. W. and Smart, E.: Private communication, (1990).
Skeel, R. D. and Tam, H.-W.:Potential for parallelism in explicit linear methods, Working Document, Department of Computer Science, University of Illinois at Urbana-Champaign (1989).
Stetter, H. J.:Considerations concerning a theory for ODE-solvers, inNumerical Treatment of Differential Equations: Proc. Oberwolfach, 1976 (Eds. R. Bulirsch, R. D. Grigorieff and J. Schröder), Lecture Notes in Mathematics 631, Springer, Berlin, (1978) 188–200.
Stetter, H. J.:Global error estimation in Adams PC-codes, ACM Trans. Math. Soft. 5 (1979), 415–430.
Stewart, N. F.:Certain equivalent requirements of approximate solutions of x′(t, x), SIAM J. Numer. Anal. 7 (1970), 256–270.
Tam, H.-W.:Parallel methods for the numerical solution of ordinary differential equations, Report No. UIUCDCS-R-89-1516, Department of Computer Science, University of Illinois at Urbana-Champaign (1989).
Verner, J. H.:On the derivation of higher order interpolants, Seminar presented at “The 1990 Conference on the Numerical Solution of ODEs”, Helsinki, Finland, June 1990.
Author information
Authors and Affiliations
Additional information
Both authors were supported by the Information Technology Research Centre of Ontario, and the Natural Sciences and Engineering Research Council of Canada. Second author's current address: Department of Mathematics and Computer Science, University of Dundee, Dundee DD1 4HN, Scotland.
Rights and permissions
About this article
Cite this article
Enright, W.H., Higham, D.J. Parallel defect control. BIT 31, 647–663 (1991). https://doi.org/10.1007/BF01933179
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01933179