Multigrid methods for implicit Runge-Kutta and boundary value method discretizations of parabolic PDEs

Advanced time discretization schemes for stiff systems of ordinary differential equations (ODEs), such as implicit Runge-Kutta and boundary value methods, have many appealing properties. However, the resulting systems of equations can be quite large and expensive to solve. Many techniques, exploiting the structure of these systems, have been developed for general ODEs. For spatial discretizations of time-dependent partial differential equations (PDEs) these techniques are in general not sufficient and also the structure arising from spatial discretization has to be taken into consideration. We show here that for time-dependent parabolic problems, this can be done by multigrid methods, as in the stationary elliptic case. The key to this approach is the use of a smoother that updates several unknowns at a spatial grid point simultaneously. The overall cost is essentially proportional to the cost of integrating a scalar ODE for each grid point. Combination of the multigrid principle with both time stepping and waveform relaxation techniques is described, together with a convergence analysis. Numerical results are presented for the isotropic heat equation and a general diffusion equation with variable coefficients.