Space-time concurrent multigrid waveform relaxation (WRMG)

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. LubichOstermann1987

   BibTeX

   Abstract

   C. Lubich and A. Ostermann, “Multi-grid dynamic iteration for parabolic equations,” BIT Numerical Mathematics, vol. 27, no. 2, pp. 216–234, 1987 [Online]. Available at: http://dx.doi.org/10.1007/BF01934186

   @article{LubichOstermann1987,
     author = {Lubich, Ch. and Ostermann, A.},
     doi = {10.1007/BF01934186},
     journal = {BIT Numerical Mathematics},
     number = {2},
     pages = {216--234},
     title = {{Multi-grid dynamic iteration for parabolic equations}},
     url = {http://dx.doi.org/10.1007/BF01934186},
     volume = {27},
     year = {1987}
   }
   

2. VandewalleVandeVelde1994

   BibTeX

   Abstract

   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 [Online]. Available at: http://dx.doi.org/10.13140/2.1.1146.1761

   @article{VandewalleVandeVelde1994,
     author = {Vandewalle, {Stefan G.} and {Van de Velde}, {Eric F.}},
     doi = {10.13140/2.1.1146.1761},
     journal = {Annals of Numerical Mathematics},
     number = {1-4},
     pages = {347--360},
     title = {{Space-time concurrent multigrid waveform relaxation}},
     url = {http://dx.doi.org/10.13140/2.1.1146.1761},
     volume = {1},
     year = {1994}
   }
   

3. HortonEtAl1995

   BibTeX

   Abstract

   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 [Online]. Available at: http://dx.doi.org/10.1137/0916034

   @article{HortonEtAl1995,
     author = {Horton, Graham and Vandewalle, Stefan and Worley, P.},
     doi = {10.1137/0916034},
     journal = {SIAM Journal on Scientific Computing},
     number = {3},
     pages = {531--541},
     title = {{An Algorithm with Polylog Parallel Complexity for Solving Parabolic Partial Differential Equations}},
     url = {http://dx.doi.org/10.1137/0916034},
     volume = {16},
     year = {1995}
   }
   

4. VandewalleHorton1995

   BibTeX

   Abstract

   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 [Online]. Available at: http://dx.doi.org/10.1007/BF02238230

   @article{VandewalleHorton1995,
     author = {Vandewalle, Stefan and Horton, Graham},
     doi = {10.1007/BF02238230},
     journal = {Computing},
     number = {4},
     pages = {317--330},
     title = {{Fourier mode analysis of the multigrid waveform relaxation and time-parallel multigrid methods}},
     url = {http://dx.doi.org/10.1007/BF02238230},
     volume = {54},
     year = {1995}
   }