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

   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: http://dx.doi.org/10.1007/BF01934186

   BibTeX

   Abstract

   BibTeX entry LubichOstermann1987

   ×

   @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

   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: http://dx.doi.org/10.13140/2.1.1146.1761

   BibTeX

   Abstract

   BibTeX entry VandewalleVandeVelde1994

   ×

   @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

   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: http://dx.doi.org/10.1137/0916034

   BibTeX

   Abstract

   BibTeX entry HortonEtAl1995

   ×

   @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

   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: http://dx.doi.org/10.1007/BF02238230

   BibTeX

   Abstract

   BibTeX entry VandewalleHorton1995

   ×

   @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}
   }