The spatial discretisation of time-dependent partial differential equations by means of finite differences, finite elements or finite volumes leads to systems of ordinary differential equations of very large dimension. Such ODE-systems can no longer be solved efficiently by classical ODE-software. Their solution requires specialised 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 Runge-Kutta formula with the number of ODEs. Because of the apparant complexity of the required linear algebra, the use of implicit Runge-Kutta schemes for large-scale problems 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 discretisation technique, which has attracted substantial attention in recent years in the ODE-community [1]. This time-discretisation scheme has superior convergence and stability characteristics, but leads to a sequence linear algebra problems whose size is a (very large) multiple of that of standard time-stepping schemes. It will be shown that a suitable modification of the multi-level method, can once more tackle these problems very efficiently.