Multilevel Iterative Methods for Implicit Runge-Kutta and Boundary-Value-Method Time-Stepping Schemes

Stefan Vandewalle

Katholieke Universiteit Leuven
Department of Computerscience
Celestijnenlaan 200A
B-3001 Leuven, Belgium


The spatial discretization of time-dependent partial differential equations (PDEs) by means of finite differences, finite elements or finite volumes leads to systems of ordinary differential equations (ODEs) of very large dimension. Such ODE systems can no longer be solved efficiently by classical ODE software. Their solution requires specialized solvers that take the structure of the semi-discrete PDE problems into account.

We will first consider the use of implicit Runge-Kutta time-stepping schemes. Such methods require the solution of very large linear or nonlinear algebraic systems in every single time-step. The size of these systems equals the product of the number of stages of the Runge-Kutta formula with the number of ODEs. Because of the apparent complexity of the required linear algebra, the use of implicit Runge-Kutta schemes for semi-discrete PDEs has been strongly discouraged in the classical ODE literature. We will show in this lecture, however, that these problems can be solved efficiently, i.e., with a complexity that is linear in the number of unknowns, when multilevel PDE algorithms are used.

Next we consider time-stepping schemes where the solution is advanced time-window by time-window. A special class of such methods is based on the so-called boundary-value-method discretization technique, which has attracted substantial attention in recent years in the ODE community [1]. This time-discretization scheme has superior convergence and stability characteristics, but leads to linear algebra problems with a size that is a (very large) multiple of that of standard time-stepping schemes. It will be shown that a suitable modification of the multilevel method, very similar to the one developed in our earlier work [2], can once more tackle these problems very efficiently.


[1] L.Brugnano, D.Trigiante, Solving Differential Problems by Multistep Initial and Boundary Value Methods, Gordon & Breach Publ., Amsterdam, 1998.

[2] S. Vandewalle, Parallel multigrid waveform relaxation for parabolic problems, B.G. Teubner Publ., Stuttgart, 1993.