Parallel Implementations of Iterated Runge-Kutta Methods

Abstract

We investigate different parallel algorithms for the iter ated Runge-Kutta method on distributed memory mul tiprocessors for the solution of systems of ordinary differential equations (ODEs). The iterated Runge-Kutta method is an iteration scheme for the numerical solu tion of initial-value problems of nonstiff ODEs; embed ded approximation formulae are used to control the step size. The parallel algorithms realize potential par allelism across the method and the system in a group- SPMD (single-program, multiple-data) programming style, using an appropriate set of communication prim itives that can be implemented on all common topolo gies. A theoretical performance analysis with run-time formulae and a run-time simulation show the value of the algorithms. The implementation on the Intel iPSC/ 860 confirms the predicted run times. The speedup values depend strongly on the particular system of ODEs to be solved. The parallel iterated Runge-Kutta method is applied to a typical discretization problem, the discretized Brusselator equation. Application-spe cific modifications of the general parallel ODE solver are developed, which result in a considerable reduc tion in the parallel execution time.

Get full access to this article

View all access options for this article.

References

Bellen, A. , Vermiglio, R. , and Zennaro, M. 1990. Parallel ODE-solvers with stepsize control. J. Comp. Appl. Math. 31:277-293.

Bertsekas, D.P. , and Tsitsiklis, J.N. , 1989. Parallel and distributed computing. New York, NY: Prentice Hall.

Bingert, A. , Formella, A. , Müller, S.M. , and Paul, W.J. , 1994. Isolating the reasons for the performance of parallel machines on numerical programs I. In Automatic parallelization. Wiesbaden: Vieweg, pp. 45-77.

Brankin, R.W. , Gladwell, I. , and Shampine, L.F. , 1991. RKSUITE 1.0 Amsterdam: North-Holland.

Burrage, K. , 1993. Parallel methods for initial value problems. Appl . Num. Math. 11:5-25.

Fehlberg, E. , 1969. Classical-fifth-, sixth-, seventh-and eighth-order Runge-Kutta formulas with step size control. Computing 4:93-106.

Franklin, M.A. , 1978. Parallel solution of ordinary differential equations . IEEE Trans. Comp. C-27(5):413-420.

Gear, C.W. , 1987. Parallel methods for ordinary differential equations. Technical report UIUCDCS-R-87-1369. Illinois: University of Illinois at Urbana-Champaign, Department of Computer Science .

Hairer, E. , Nørsett, S.P. , and Wanner, G. , 1993. Solving ordinary differential equations I: nonstiff problems . Berlin: Springer-Verlag .

10.

Hairer, E. , and Wanner, G. , 1991. Solving ordinary differential equations II. Berlin: Springer-Verlag.

11.

Hutchinson, D. , and Khalaf, B.M.S. , 1991. Parallel algorithms for solving initial value problems: front broadening and embedded parallelism. Parallel Computing 17:957-968.

12.

Johnsson, S.L. , and Ho, C.T. , 1989. Optimum broadcasting and personalized communication in hypercubes. IEEE Trans. Comp. 38(9): 1249-1268.

13.

Knirsch, R. , 1993. Parallele Algorithmen zur numerischen Lösung von Systemen gewöhnlicher Differentialgleichungen. Ph.D. thesis, University of Erlangen.

14.

Lefever, R. , and Nicolis, G. , 1971. Chemical instabilities and sustained oscillations . J. Theor. Biol. 30:267-284.

15.

Miranker, W.L. , and Liniger, W. , 1967. Parallel methods for the numerical integration of ordinary differential equations. Mathematics of Computation 21(99):303-320.

16.

NØrsett, S.P. , and Simonsen, H.H. , 1989. Aspects of parallel Runge-Kutta methods. In Numerical methods for ordinary differential equations, volume 1386 of Lecture notes in mathematics. Berlin: Springer-Verlag , pp. 103-117.

17.

Prince, P.J. , and Dormand, J.R. , 1981. High order embedded Runge-Kutta formulae. J. Comp . Appl. Math. 7(1):67-75.

18.

Rauber, T. , and Rünger, G. , 1994a. Hypercube implementation and performance analysis for extrapolation methods. In Proceedings of the CONPAR'94, LNCS854 Berlin: Springer-Verlag, pp.265-276.

19.

Rauber, T. , and Rünger, G. , 1994b. Load balancing for extrapolation methods on distributed memory multiprocessors. In Proceedings of the PARLE'94, LNCS 817 Berlin: Springer-Verlag, pp. 277-288.

20.

Rauber, T. , and Rünger, G. , 1995. Parallel solution of a Schrödinger-Poisson system. In Proceedings of HPCN'95, LNCS 919. Berlin: Springer-Verlag, pp. 697-702.

21.

Rünger, G. , 1989. Über ein Schrödinger-Poisson-System. Ph.D. thesis. University of Cologne.

22.

Tam, H.W. , 1989. Parallel methods, for the numerical solution of ordinary differential equations. Technical report UIUCDCS-R-89-1516. Illinois: University of Illinois at Urbana-Champaign, Department of Computer Science.

23.

van der Houwen, P.J. , and Sommeijer, B.P. , 1990a. Parallel iteration of high-order Runge-Kutta methods with stepsize control. J. Comp. Appl. Math. 29:111-127.

24.

van der Houwen, P.J. , and Sommeijer, B.P. , 1990a. Parallel ODE solvers. In Proceedings of the ACM international conference on supercomputing, pp. 71-81.

25.

Worland, P.B. , 1976. Parallel methods for the numerical solution of ordinary differential equations. IEEE Trans. Comp. 25(10):1045-1048.

26.

Worland, P.B. , 1993. Parallel methods for ODEs with improved absolute stability boundaries. J. Parallel Distrib. Comp. 18(1):25-32.