Summary
Multigrid methods are among the fastest numerical algorithms for the solution of large sparse systems of linear equations. While these algorithms exhibit asymptotically optimal computational complexity, their efficient parallelisation is hampered by the poor computation-to-communication ratio on the coarse grids. Our contribution discusses parallelisation techniques for geometric multigrid methods. It covers both theoretical approaches as well as practical implementation issues that may guide code development.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
R. E. Alcouffe, A. Brandt, J. E. Dendy, and J. W. Painter. The multi-grid methods for the diffusion equation with strongly discontinuous coefficients. SIAM J. Sci. Stat. Comput., 2:430–454, 1981.
R. Allen and K. Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann Publishers, San Francisco, California, USA, 2001.
R. E. Bank and M. Holst. A new paradigm for parallel adaptive meshing algorithms. SIAM J. Sci. Comput., 22(4):1411–1443, 2000.
P. Bastian, W. Hackbusch, and G. Wittum. Additive and multiplicative multi-grid — a comparison. Computing, 60(4):345–364, 1998.
B. Bergen and F. Hülsemann. Hierarchical hybrid grids: data structures and core algorithms for multigrid. Numerical Linear Algebra with Applications, 11:279–291, 2004.
J. H. Bramble, J. E. Pasciak, and J. Xu. Parallel multilevel preconditioners. Math. Comp., 55:1–22, 1990.
A. Brandt. Multi-level adaptive solutions to boundary-value problems. Math. Comp., 31:333–390, 1977.
A. Brandt. Multigrid techniques: 1984 guide with applications to fluid dynamics. GMD-Studien Nr. 85. Gesellschaft für Mathematik und Datenverarbeitung, St. Augustin, 1984.
A. Brandt and B. Diskin. Multigrid solvers on decomposed domains. In Domain Decomposition Methods in Science and Engineering: The Sixth International Conference on Domain Decomposition, volume 157 of Contemporary Mathematics, pp. 135–155, Providence, Rhode Island, 1994. American Mathematical Society.
W. Briggs, V. Henson, and S. McCormick. A Multigrid Tutorial. SIAM, 2. edition, 2000.
T. F. Chan and R. S. Tuminaro. Analysis of a parallel multigrid algorithm. In J. Mandel, S. F. McCormick, J. E. Dendy, C. Farhat, G. Lonsdale, S. V. Parter, J. W. Ruge, and K. Stüben, editors, Proceedings of the Fourth Copper Mountain Conference on Multigrid Methods, pp. 66–86, Philadelphia, 1989. SIAM.
R. Chandra, L. Dagum, D. Kohr, D. Maydan, J. McDonald, and R. Menon. Parallel Programming in OpenMP. Morgan Kaufmann, 2001.
L. Dagum and R. Menon. OpenMP: An industry-standard API for shared-memory programming. IEEE Comp. Science and Engineering, 5(1):46–55, 1998.
B. Diskin. Multigrid Solvers on Decomposed Domains. Master’s thesis, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, 1993.
C. C. Douglas. A review of numerous parallel multigrid methods. In G. Astfalk, editor, Applications on Advanced Architecture Computers, pp. 187–202. SIAM, Philadelphia, 1996.
C. C. Douglas and M. B. Douglas. MGNet Bibliography. Department of Computer Science and the Center for Computational Sciences, University of Kentucky, Lexington, KY, USA and Department of Computer Science, Yale University, New Haven, CT, USA, 1991–2002 (last modified on September 28, 2002); see http://www.mgnet.org/mgnet-bib.html.
C. C. Douglas, G. Haase, and U. Langer. A Tutorial on Elliptic PDE Solvers and their Parallelization. SIAM, 2003.
C. C. Douglas, J. Hu, M. Kowarschik, U. Rüde, and C. Weiß. Weimization for structured and unstructured grid multigrid. Elect. Trans. Numer. Anal., 10:21–40, 2000.
L. Formaggia, M. Sala, and F. Saleri. Domain decomposition techniques. In A. M. Bruaset and A. Tveito, editors, Numerical Solution of Partial Differential Equations on Parallel Computers, volume 51 of Lecture Notes in Computational Science and Engineering, pp. 135–163. Springer-Verlag, 2005.
P. O. Frederickson and O. A. McBryan. Parallel superconvergent multigrid. In S. F. Mc-Cormick, editor, Multigrid Methods: Theory, Applications, and Supercomputing, volume 110 of Lecture Notes in Pure and Applied Mathematics, pp. 195–210. Marcel Dekker, New York, 1988.
T. L. Freeman and C. Phillips. Parallel numerical algorithms. Prentice Hall, New York, 1992.
D. B. Gannon and J. R. Rosendale. On the structure of parallelism in a highly concurrent pde solver. J. Parallel Distrib. Comput., 3:106–135, 1986.
A. Greenbaum. Iterative Methods for Solving Linear Systems. SIAM, 1997.
M. Griebel. Grid-and point-oriented multilevel algorithms. In W. Hackbusch and G. Wittum, editors, Incomplete Decompositions (ILU) — Algorithms, Theory, and Applications, Notes on Numerical Fluid Mechanics, pp. 32–46. Vieweg, Braunschweig, 1993.
M. Griebel. Multilevel algorithms considered as iterative methods on semidefinite systems. SIAM J. Sci. Stat. Comput., 15:547–565, 1994.
M. Griebel. Parallel point-oriented multilevel methods. In Multigrid Methods IV, Proceedings of the Fourth European Multigrid Conference, Amsterdam, July 6–9, 1993, volume 116 of ISNM, pp. 215–232, Basel, 1994. Birkhäuser.
M. Griebel and P. Oswald. On the abstract theory of additive and multiplicative Schwarz algorithms. Numer. Math., 70:163–180, 1995.
M. Griebel and G.W. Zumbusch. Hash-storage techniques for adaptive multilevel solvers and their domain decomposition parallelization. In J. Mandel, C. Farhat, and X.-C. Cai, editors, Proceedings of Domain Decomposition Methods 10, DD10, number 218 in Contemporary Mathematics, pp. 279–286, Providence, 1998. AMS.
W. Gropp, E. Lusk, N. Doss, and A. Skjellum. A high-performance, portable implementation of the MPI message passing interface standard. Parallel Computing, 22(6):789–828, Sept. 1996.
W. Gropp, E. Lusk, and A. Skjellum. Using MPI, Portable Parallel Programming with the Mesage-Passing Interface. MIT Press, second edition, 1999.
G. Haase. Parallelisierung numerischer Algorithmen für partielle Differentialgleichungen. B. G. Teubner Stuttgart — Leipzig, 1999.
W. Hackbusch. Multigrid Methods and Applications, volume 4 of Computational Mathematics. Springer-Verlag, Berlin, 1985.
W. Hackbusch. Iterative Solution of Large Sparse Systems of Equations, volume 95 of Applied Mathematical Sciences. Springer, 1993.
J. Hennessy and D. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publisher, Inc., San Francisco, California, USA, 3. edition, 2003.
F. Hülsemann, B. Bergen, and U. Rüde. Hierarchical hybrid grids as basis for parallel numerical solution of PDE. In H. Kosch, L. Böszörményi, and H. Hellwagner, editors, Euro-Par 2003 Parallel Processing, volume 2790 of Lecture Notes in Computer Science, pp. 840–843, Berlin, 2003. Springer.
F. Hülsemann, S. Meinlschmidt, B. Bergen, G. Greiner, and U. Rüde. gridlib — a parallel, object-oriented framework for hierarchical-hybrid grid structures in technical simulation and scientific visualization. In High Performance Computing in Science and Engineering, Munich 2004. Transactions of the Second Joint HLRB and KONWIHR Result and Reviewing Workshop, pp. 37–50, Berlin, 2004. Springer.
M. Jung. On the parallelization of multi-grid methods using a non-overlapping domain decomposition data structure. Appl. Numer. Math., 23(1):119–137, 1997.
M. Jung. Parallel multiplicative and additive multilevel methods for elliptic problems in three-dimensional domains. In B. H. V. Topping, editor, Advances in Computational Mechanics with Parallel and Distributed Processing, pp. 171–177, Edinburgh, 1997. Civil-Comp Press. Proceedings of the EURO-CM-PAR97, Lochinver, April 28–May 1, 1997.
G. Karypis and V. Kumar. A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1):359–392, 1999.
G. Karypis and V. Kumar. Parallel multilevel k-way partition scheme for irregular graphs. SIAM Review, 41(2):278–300, 1999.
C. Körner, T. Pohl, U. Rüde, N. Thürey, and T. Zeiser. Parallel lattice boltzmann methods for cfd applications. In A. M. Bruaset and A. Tveito, editors, Numerical Solution. of Partial Differential Equations on Parallel Computers, volume 51 of Lecture Notes in Computational Science and Engineering, pp. 439–466. Springer-Verlag, 2005.
M. Kowarschik. Data Locality Optimizations for Iterative Numerical Algorithms and Cellular Automata on Hierarchical Memory Architectures. PhD thesis, Lehrstuhl für Informatik 10 (Systemsimulation), Institut für Informatik, Universität Erlangen-Nürnberg, Erlangen, Germany, July 2004. SCS Publishing House.
H. Lötzbeyer and U. Rüde. Patch-adaptive multilevel iteration. BIT, 37:739–758, 1997.
L. R. Matheson and R. E. Tarjan. Parallelism in multigrid methods: how much is too much? Int. J. Paral. Prog., 24:397–432, 1996.
O. A. McBryan, P. O. Frederickson, J. Linden, A. Schuller, K. Solchenbach, K. Stuben, C.-A. Thole, and U. Trottenberg. Multigrid methods on parallel computers — a survey of recent developments. Impact Comput. Sci. Eng., 3:1–75, 1991.
W. F. Mitchell. A parallel multigrid method using the full domain partition. Elect. Trans Numer. Anal., 6:224–233, 1997.
W. F. Mitchell. The full domain partition approach to distributing adaptive grids. Appl Numer. Math., 26:265–275, 1998.
W. F. Mitchell. Parallel adaptive multilevel methods with full domain partitions. App Num. Anal. and Comp. Math., 1:36–48, 2004.
M. Mohr. Low Communication Parallel Multigrid: A Fine Level Approach. In A. Bode, T. Ludwig, W. Karl, and R. Wismüller, editors, Proceedings of Euro-Par 2000: Parallel. Processing, volume 1900 of Lecture Notes in Computer Science, pp. 806–814. Springer, 2000.
M. Mohr and U. Rüde. Communication Reduced Parallel Multigrid: Analysis and Experiments. Technical Report 394, Institut für Mathematik, Universität Augsburg, 1998.
P. Oswald. Multilevel Finite Element Approximation, Theory and Applications. Teubner Skripten zur Numerik. Teubner Verlag, Stuttgart, 1994.
A. Pothen. Graph partitioning algorithms with applications to scientific computing. In D. E. Keyes, A. H. Sameh, and V. Venkatakrishnan, editors, Parallel Numerical Algorithms, volume 4 of ICASE/LaRC Interdisciplinary Series in Science and Engineering. Kluwer Academic Press, 1997.
M. Prieto, I. Llorente, and F. Tirado. A Review of Regular Domain Partitioning. SIAM News, 33(1), 2000.
G. Rivera and C.-W. Tseng. Data Transformations for Eliminating Conflict Misses. In Proc. of the ACM SIGPLAN Conf. on Programming Language Design and Implementation, Montreal, Canada, 1998.
U. Rüde. Mathematical and Computational Techniques for Multilevel Adaptive Methods, volume 13 of Frontiers in Applied Mathematics. SIAM, Philadelphia, 1993.
Y. Saad. Iterative Methods for Sparse Linear Systems. SIAM, 2nd edition, 2003.
J. Stoer and R. Bulirsch. Numerische Mathematik 2. Springer, 4. edition, 2000.
J. D. Teresco, K. D. Devine, and J. E. Flaherty. Partitioning and dynamic load balancing for the numerical solution of partial differential equations. In A. M. Bruaset and A. Tveito, editors, Numerical Solution of Partial Differential Equations on Parallel Computers, volume 51 of Lecture Notes in Computational Science and Engineering, pp. 55–88. Springer-Verlag, 2005.
C.-A. Thole and U. Trottenberg. Basic smoothing procedures for the multigrid treatment of elliptic 3D-operators. Appl. Math. Comput., 19:333–345, 1986.
U. Trottenberg, C. W. Oosterlee, and A. Schüller. Multigrid. Academic Press, London, 2000.
C. Weiß Data Locality Optimizations for Multigrid Methods on Structured Grids. PhD thesis, Lehrstuhl für Rechnertechnik und Rechnerorganisation, Institut für Informatik, Technische Universität München, Munich, Germany, Dec. 2001.
R. Wienands and C. W. Oosterlee. On three-grid fourier analysis for multigrid. SIAM J Sci. Comput., 23(2):651–671, 2001.
G. Wittum. On the robustness of ILU-smoothing. SIAM J. Sci. Stat. Comput., 10:699–717, 1989.
D. Xie and L. Scott. The Parallel U-Cycle Multigrid Method. In Virtual Proceedings. of the 8th Copper Mountain Conference on Multigrid Methods, 1997. Available at http://www.mgnet.org.
U. M. Yang. Parallel algebraic multigrid methods-high performance preconditioners. In A. M. Bruaset and A. Tveito, editors, Numerical Solution of Partial Differential Equations on Parallel Computers, volume 51 of Lecture Notes in Computational Science and Engineering, pp. 209–236. Springer-Verlag, 2005.
I. Yavneh. On red-black SOR smoothing in multigrid. SIAM J. Sci. Comput., 17:180–192, 1996.
G. Zumbusch. Parallel Multilevel Methods — Adaptive Mesh Refinement and Loadbalancing. Advances in Numerical Mathematics. Teubner, 2003.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hülsemann, F., Kowarschik, M., Mohr, M., Rüde, U. (2006). Parallel Geometric Multigrid. In: Bruaset, A.M., Tveito, A. (eds) Numerical Solution of Partial Differential Equations on Parallel Computers. Lecture Notes in Computational Science and Engineering, vol 51. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-31619-1_5
Download citation
DOI: https://doi.org/10.1007/3-540-31619-1_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29076-6
Online ISBN: 978-3-540-31619-0
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)