Article

Free access

Parallel smoothed aggregation multigrid: aggregation strategies on massively parallel machines

Author:

Ray S. TuminaroAuthors Info & Claims

SC '00: Proceedings of the 2000 ACM/IEEE conference on Supercomputing

Pages 5 - es

Published: 01 November 2000 Publication History

PDF eReader

Abstract

Algebraic multigrid methods offer the hope that multigrid convergence can be achieved (for at least some important applications) without a great deal of effort from engineers and scientists wishing to solve linear systems. In this paper we consider parallelization of the smoothed aggregation multigrid method. Smoothed aggregation is one of the most promising algebraic multigrid methods. Therefore, developing parallel variants with both good convergence and efficiency properties is of great importance. However, parallelization is nontrivial due to the somewhat sequential aggregation (or grid coarsening) phase. In this paper, we discuss three different parallel aggregation algorithms and illustrate the advantages and disadvantages of each variant in terms of parallelism and convergence. Numerical results will be shown on the Intel Teraflop computer for some large problems coming from nontrivial codes: quasi-static electric potential simulation and a fluid flow calculation.

References

[1]

M. Adams Evaluation of Geometric and an Algebraic Multigrid Method on 3D Finite Element Problems in Solid Mechanics Talk at the Copper Mountain Conference on Iterative Methods,Copper Mtn,Co,4/2000.

Google Scholar

[2]

M. F. Adams A parallel maximal independent set algorithm inProceedings 5th copper mountain conference on iterative metho s,1998. Best student paper award winner.

Google Scholar

[3]

J. Bramble, J. Pasciak, J. Wang, and J. Xu Convergence Estimates for Multigrid Algorithms without Regularity Assumptions Math Comp.,57 (1991),pp.23-45.

Crossref

Google Scholar

[4]

A. Brandt Multi-level Adaptive Solutions to Boundary-Value Problems Math.Comp.,31 (1977),pp.333-390.

Crossref

Google Scholar

[5]

W. Hackbusch Multi-grid Methods and Applications Springer-Verlag, Berlin,1985.

Google Scholar

[6]

,Iterative Solution of Large Sparse Linear Systems of Equations Springer-Verlag,Berlin,1994.

Google Scholar

[7]

V. Henson and U. Yang Coarse Grid Selection of Algebraic Multigrid Tech.Rep.UCRL-MI-13089,Lawrence Livermore National Laboratory,Livermore,CA,1999.

Google Scholar

[8]

E. Jenkins, R. Berger, J. Hallberg, S. Howington, C. T. Kelley, J. Schmidt, A. Stagg, and M. Tocci A Two-Level Aggregation-Based Newton-Krylov-Schwarz Method for Hydrology in Parallel Computational Fluid Dynamics 1999,D.Keyes,A.Ecer,J.Periaux,an N.Satofuka,e s.,North Hollan,2000,pp.257-264.

Google Scholar

[9]

M. T. Jones and P. E. Plassman A Parallel Graph Coloring Heuristic SIAM J.Sci.Comput.,14 (1993),pp.654-669.

Digital Library

Google Scholar

[10]

C. Tong, R. Tuminaro, K. Devine, and J. Shadid Design of a Multilevel Preconditioning Module for Unstructured Calculations Tech. Rep.in preparaion,San ia National Laboratories,Albuquerque NM, 87185,2000.

Google Scholar

[11]

P. Vanek Acceleration of Convergence of a Two Level Algorithm by Smooth Transfer Operators Appl.Math.,37 (1992),pp.265 -274.

Google Scholar

[12]

P. Vanek, M. Brezina, and J. Mandel Convergence of Algebraic Multigrid Based on Smoothed Aggregation Tech.Rep.report 126, UCD/CCM,Denver,CO,1998.

Digital Library

Google Scholar

[13]

P. Vanek, J. Mandel, and M. Brezina Algebraic Multigrid Based on Smoothed Aggregation for Second and Fourth Order Problems Computing,56 (1996),pp.179 -196.

Google Scholar

Cited By

View all

Kronbichler MDiagne AHolmgren H(2018)A fast massively parallel two-phase flow solver for microfluidic chip simulationInternational Journal of High Performance Computing Applications10.5555/3195466.319547232:2(266-287)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.5555/3195466.3195472
Turcksin BKronbichler MBangerth W(2016)WorkStream -- A Design Pattern for Multicore-Enabled Finite Element ComputationsACM Transactions on Mathematical Software10.1145/285148843:1(1-29)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.1145/2851488
Berger-Vergiat LMcAuliffe CWaisman H(2016)Parallel preconditioners for monolithic solution of shear bandsJournal of Computational Physics10.1016/j.jcp.2015.09.028304:C(359-379)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.jcp.2015.09.028
Show More Cited By

Index Terms

Parallel smoothed aggregation multigrid: aggregation strategies on massively parallel machines

Recommendations

Smoothed Aggregation Multigrid for the Discontinuous Galerkin Method

The aim of this paper is to investigate theoretically as well as experimentally an algebraic multilevel algorithm for the solution of the linear systems that arise from the discontinuous Galerkin method. The smoothed aggregation multigrid, introduced by ...
Adaptive Smoothed Aggregation ($\alpha$SA) Multigrid

Substantial effort has been focused over the last two decades on developing multilevel iterative methods capable of solving the large linear systems encountered in engineering practice. These systems often arise from discretizing partial differential ...
Multigrid algorithms for massively parallel machines

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SC '00: Proceedings of the 2000 ACM/IEEE conference on Supercomputing

November 2000

889 pages

ISBN:0780398025

Conference Chair:
Louis Turcotte
Rose-Hulman Institute of Technology

In-Cooperation

SIAM: Society for Industrial and Applied Mathematics

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 November 2000

Check for updates

Qualifiers

Article

Conference

SC '00

Sponsor:

SIGARCH
IEEE-CS

SC '00: International Conference for High Performance Computing, Networking, Storage and Analysis

November 4 - 10, 2000

Texas, Dallas, USA

Acceptance Rates

SC '00 Paper Acceptance Rate 62 of 179 submissions, 35%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
496
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)11

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kronbichler MDiagne AHolmgren H(2018)A fast massively parallel two-phase flow solver for microfluidic chip simulationInternational Journal of High Performance Computing Applications10.5555/3195466.319547232:2(266-287)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.5555/3195466.3195472
Turcksin BKronbichler MBangerth W(2016)WorkStream -- A Design Pattern for Multicore-Enabled Finite Element ComputationsACM Transactions on Mathematical Software10.1145/285148843:1(1-29)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.1145/2851488
Berger-Vergiat LMcAuliffe CWaisman H(2016)Parallel preconditioners for monolithic solution of shear bandsJournal of Computational Physics10.1016/j.jcp.2015.09.028304:C(359-379)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.jcp.2015.09.028
Notay YNapov A(2015)A massively parallel solver for discrete Poisson-like problemsJournal of Computational Physics10.1016/j.jcp.2014.10.043281:C(237-250)Online publication date: 15-Jan-2015
https://dl.acm.org/doi/10.1016/j.jcp.2014.10.043
Plunkett PHu JSiefert CAtzberger P(2014)Spatially adaptive stochastic methods for fluid-structure interactions subject to thermal fluctuations in domains with complex geometriesJournal of Computational Physics10.1016/j.jcp.2014.07.051277:C(121-137)Online publication date: 15-Nov-2014
https://dl.acm.org/doi/10.1016/j.jcp.2014.07.051
D’Ambra PSerafino DFilippone S(2010)MLD2P4ACM Transactions on Mathematical Software10.1145/1824801.182480837:3(7-23)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1145/1824801.1824808
Adelmann AArbenz PIneichen Y(2010)A fast parallel Poisson solver on irregular domains applied to beam dynamics simulationsJournal of Computational Physics10.1016/j.jcp.2010.02.022229:12(4554-4566)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1016/j.jcp.2010.02.022
Adelmann AArbenz PIneichen Y(2010)Improvements of a fast parallel poisson solver on irregular domainsProceedings of the 10th international conference on Applied Parallel and Scientific Computing - Volume Part I10.1007/978-3-642-28151-8_7(65-74)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-28151-8_7
Emans M(2009)AMG for linear systems in engine flow simulationsProceedings of the 8th international conference on Parallel processing and applied mathematics: Part II10.5555/1893586.1893630(350-359)Online publication date: 13-Sep-2009
https://dl.acm.org/doi/10.5555/1893586.1893630
Liu FSosonkina MBramley RWainer GShaffer CMcGraw RChinni M(2009)A HPC sparse solver interface for scalable multilevel methodsProceedings of the 2009 Spring Simulation Multiconference10.5555/1639809.1639923(1-6)Online publication date: 22-Mar-2009
https://dl.acm.org/doi/10.5555/1639809.1639923
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Smoothed Aggregation Multigrid for the Discontinuous Galerkin Method

Adaptive Smoothed Aggregation ($\alpha$SA) Multigrid

Multigrid algorithms for massively parallel machines