Parallel one-step methods with minimal parallel stages. (English) Zbl 0840.65079

Suppose that sufficiently many processors are available, so that embedded methods do not need to be considered. Then, for certain types of method, lower bounds for the number of (parallel) stages, \(s_p\), required to achieve a given order, \(p\), are derived. For the general explicit one step method it is shown that \(s_p \geq p\). Results of this type are obtained for implicit Runge-Kutta methods, (singly) diagonally implicit Runge-Kutta methods, semi-implicit Runge-Kutta methods and Rosenbrock-Wanner methods.


65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
65L05 Numerical methods for initial value problems involving ordinary differential equations
34A34 Nonlinear ordinary differential equations and systems
65Y05 Parallel numerical computation
Full Text: DOI


[1] Abramowitz, M.; Stegun, I.A., Handbook of mathematical functions, (1964), Dover New York · Zbl 0515.33001
[2] Bader, G.; Deuflhard, P., A semi-implicit mid-point rule for stiff systems of ordinary differential equations, Numer. math., 41, 373-398, (1983) · Zbl 0522.65050
[3] Bellen, A.; Vermiglio, R.; Zennaro, M., Parallel ODE-solver with stepsize control, J. comput. appl. math., 31, 277-293, (1990) · Zbl 0707.65051
[4] Burrage, K., A special family of Runge-Kutta methods for solving stiff differential equations, Bit, 18, 22-41, (1978) · Zbl 0384.65034
[5] Butcher, J.J., Integration processes based on radau quadrature formulas, Math. comp., 18, 233-244, (1964) · Zbl 0123.11702
[6] Chipman, F.H., A-stable Runge-Kutta processes, Bit, 11, 384-388, (1971) · Zbl 0265.65035
[7] Denk, G., A new numerical method for integration of highly oscillatory second-order ordinary differential equations, Appl. numer. math., 13, 57-67, (1993) · Zbl 0808.65081
[8] in: Proceedings ECMI-94 (Teubner-Verlag, Leipzig, to appear).
[9] Deuflhard, P., Recent progress in extrapolation methods for ordinary differential equations, SIAM rev., 27, 505-535, (1985) · Zbl 0602.65047
[10] Ehle, B.L., On Padé approximations to the exponential function and A-stable methods for the numerical solution of initial value problems, () · Zbl 0176.14604
[11] Hairer, E.; Nørsett, S.P.; Wanner, G., Solving ODE I, (1987), Springer Berlin
[12] Hairer, E.; Wanner, G., Solving ODE II, (1991), Springer Berlin
[13] Iserles, A.; Nørsett, S.P., On the theory of parallel Runge-Kutta methods, IMA J. numer. anal., 10, 463-488, (1990) · Zbl 0712.65071
[14] Jackson, K.R.; Nørsett, S.P., The potential for parallelism in Runge-Kutta methods. part 1: RK formulas in standard form, SIAM J. numer. anal., 32, 1, 49-82, (1995) · Zbl 0826.65073
[15] Kappeller, M.; Kiehl, M., Parallel extrapolation methods for stiff and non-stiff initial-value problems, (), 71-77
[16] also: Appl. Math. Comput. (submitted). · Zbl 0859.65070
[17] Kaps, P.; Rentrop, P., Generalized Runge-Kutta methods of order four with stepsize control for stiff ordinary differential equations, Numer. math., 33, 55-68, (1979) · Zbl 0436.65047
[18] Kiehl, M.; Zenger, C., An improved starting step of the G-B-S-method for the solution of ordinary differential equations, Computing, 41, 131-136, (1989) · Zbl 0662.65065
[19] Kiehl, M., Parallel multiple shooting for the solution of initial value problems, Parallel comput., 20, 275-295, (1994) · Zbl 0798.65079
[20] Nørsett, S.P.; Simonsen, H.H., Aspects of parallel Runge-Kutta methods, (), 103-117 · Zbl 0683.65057
[21] Runge, C., Über die numerische auflösung von differentialgleichungen, Math. ann., 44, 167-178, (1895) · JFM 26.0341.01
[22] Skeel, R.D.; Tam, H.W., Limits of parallelism in explicit ODE methods, Numer. algorithms, 2, 3-4, 337-349, (1992) · Zbl 0772.65046
[23] van der Houwen, P.J.; Sommeijer, B.P., Parallel iteration of high-order Runge-Kutta methods with stepsize control, J. comput. appl. math., 29, 111-127, (1990) · Zbl 0682.65039
[24] van der Houwen, P.J.; Sommeijer, B.P., Iterated Runge-Kutta methods on parallel computers, SIAM J. sci. statist. comput., 12, 5, 1000-1028, (1991) · Zbl 0732.65065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.