Multigrid waveform relaxation [1] is an algorithm for solving parabolic partial differential equations on multicomputers. The method is based on applying standard iterative methods to systems of ordinary differential equations and using multigrid techniques for accelerating this process. Some time parallelism was introduced in the method described in [2] by using pipelining or the partition method. However, a small sequential component remained. In [3], it was shown that when using cyclic reduction instead of the partition method major classes of parabolic problems can be solved in polylog parallel time without giving up linear serial complexity. In [4], the method was analyzed bz means of local Fourier analysis and compared to similar results for a time-parallel multigrid method.

  1. C. Lubich and A. Ostermann, “Multi-grid dynamic iteration for parabolic equations,” BIT Numerical Mathematics, vol. 27, no. 2, pp. 216–234, 1987, doi: 10.1007/BF01934186. [Online]. Available at:
  2. S. G. Vandewalle and E. F. Van de Velde, “Space-time concurrent multigrid waveform relaxation,” Annals of Numerical Mathematics, vol. 1, no. 1-4, pp. 347–360, 1994, doi: 10.13140/2.1.1146.1761. [Online]. Available at:
  3. G. Horton, S. Vandewalle, and P. Worley, “An Algorithm with Polylog Parallel Complexity for Solving Parabolic Partial Differential Equations,” SIAM Journal on Scientific Computing, vol. 16, no. 3, pp. 531–541, 1995, doi: 10.1137/0916034. [Online]. Available at:
  4. S. Vandewalle and G. Horton, “Fourier mode analysis of the multigrid waveform relaxation and time-parallel multigrid methods,” Computing, vol. 54, no. 4, pp. 317–330, 1995, doi: 10.1007/BF02238230. [Online]. Available at: