More Web Proxy on the site http://driver.im/

Article

Multilevel algorithms for generating coarse grids for multigrid methods

Authors:

Irene Moulitsas,

George KarypisAuthors Info & Claims

SC '01: Proceedings of the 2001 ACM/IEEE conference on Supercomputing

Page 45

https://doi.org/10.1145/582034.582079

Published: 10 November 2001 Publication History

Abstract

Geometric Multigrid methods have gained widespread acceptance for solving large systems of linear equations, especially for structured grids. One of the challenges in successfully extending these methods to unstructured grids is the problem of generating an appropriate set of coarse grids. The focus of this paper is the development of robust algorithms, both serial and parallel, for generating a sequence of coarse grids from the original unstructured grid. Our algorithms treat the problem of coarse grid construction as an optimization problem that tries to optimize the overall quality of the resulting fused elements. We solve this problem using the multilevel paradigm that has been very successful in solving the related grid/graph partitioning problem. The parallel formulation of our algorithm incurs a very small communication overhead, achieves high degree of concurrency, and maintains the high quality of the coarse grids obtained by the serial algorithm.

References

[1]

T. N. Bui, S. Chaudhuri, F. T. Leighton, and M. Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, 7(2):171-191, 1987.

Digital Library

[2]

H. Guillard. Node-nested multigrid with delaunay coarsening. Technical Report No 1898, INRIA---Sophia Antipolis, France, 1993.

[3]

Bruce Hendrickson and Robert Leland. A multilevel algorithm for partitioning graphs. Technical Report SAND93-1301, Sandia National Laboratories, 1993.

[4]

G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96-129, 1998. Also available on WWW at URL http://www.cs.umn.edu/~karypis.

Digital Library

[5]

G. Karypis and V. Kumar. A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1), 1999. Also available on WWW at URL http://www.cs.umn.edu/~karypis. A short version appears in Intl. Conf. on Parallel Processing 1995.

Digital Library

[6]

G. Karypis and V. Kumar. Parallel multilevel k-way partitioning for irregular graphs. SIAM Review, 41(2):278-300, 1999.

Digital Library

[7]

G. Karypis, Kirk Schloegel, and V. Kumar. ParMeTiS 2.0: Parallel graph partitioning and sparse matrix ordering library. Technical report, Department of Computer Science, University of Minnesota, 1998. Available on the WWW at URL http://www.cs.umn.edu/~metis.

[8]

George Karypis and Vipin Kumar. A coarse-grain parallel multilevel k-way partitioning algorith m. In Proceedings of the eighth SIAM conference on Parallel Processing for Scientific Computing, 1997.

[9]

H. Steve M. Lallemand and A. Dervieux. Unstructured multigridding by volume agglomeration: Current status. Computers and Fluids, Volume 21, (3):397-433, 1992.

[10]

D.J. Mavriplis. Directional coarsening and smoothing for anisotropic navier-stokes problems. Electronic Transactions on Numerical Analysis, (6):182-197, 1997.

[11]

D.J. Mavriplis. Three-dimensional high-lift analysis using a parallel unstructured multigrid solver. Technical Report 98-20, Institute for Computer Applications in Science and Engineering NASA Langley Research Center, 1998.

Digital Library

[12]

D.J. Mavriplis and S. Pirzadeh. Large scale parallel unstructured mesh computations for 3d high-life analysis. Technical Report 99-9, Institute for Computer Applications in Science and Engineering NASA Langley Research Center, 1999.

Digital Library

[13]

V. Venkatakrishnan D.J. Mavriplis. Agglomeration multigrid for the three-dimensional euler equations. Technical Report 94-5, Institute for Computer Applications in Science and Engineering NASA Langley Research Center, 1994.

Digital Library

[14]

Kirk Schloegel, George Karypis, and Vipin Kumar. Multilevel diffusion algorithms for repartitioning of adaptive meshes. Journal of Parallel and Distributed Computing, 47(2):109-124, 1997. Also available on WWW at URL http://www.cs.umn.edu/~karypis.

Digital Library

[15]

Kirk Schloegel, George Karypis, and Vipin Kumar. Wavefront diffusion and lmsr: Algorithms for dynamic repartitioning of adaptoive meshes. IEEE Transactions on Parallel and Distributed Systems, 12(5):451-466, 2001.

Digital Library

[16]

C. Walshaw, M. Cross, and M. G. Everett. Dynamic load-balancing for parallel adaptive unstructured meshes. Parallel Processing for Scientific Computing, 1997.

Cited By

Menon AKerstein AOevermann M(2024)Investigation of coarse-graining parameters for super-grid LEM closure applied to LES of practical bluff-body flamesCombustion Theory and Modelling10.1080/13647830.2024.2428156(1-22)Online publication date: 16-Nov-2024
https://doi.org/10.1080/13647830.2024.2428156
Heaney CLi YMatar OPain C(2024)Applying Convolutional Neural Networks to data on unstructured meshes with space-filling curvesNeural Networks10.1016/j.neunet.2024.106198175(106198)Online publication date: Jul-2024
https://doi.org/10.1016/j.neunet.2024.106198
Menon AKerstein AOevermann M(2024)Assessing the Multi-Regime Capability of the Super-Grid Linear Eddy Model (SG-LEM) Using the Darmstadt Multi-Regime BurnerFlow, Turbulence and Combustion10.1007/s10494-024-00602-xOnline publication date: 29-Nov-2024
https://doi.org/10.1007/s10494-024-00602-x
Show More Cited By

Index Terms

Multilevel algorithms for generating coarse grids for multigrid methods

Recommendations

Non-Galerkin Coarse Grids for Algebraic Multigrid

Algebraic multigrid (AMG) is a popular and effective solver for systems of linear equations that arise from discretized partial differential equations. While AMG has been effectively implemented on large scale parallel machines, challenges remain, especially ...
Multigrid Methods on Adaptively Refined Grids

Using multigrid solvers in the adaptive finite element method yields a powerful tool for solving large-scale partial differential equations that exhibit localized features such as singularities or shocks. In addition to describing the basic method and ...
Fourier Analysis of Multigrid Methods on Hexagonal Grids

This paper applies local Fourier analysis to multigrid methods on hexagonal grids. Using oblique coordinates to express the grids and a dual basis for the Fourier modes, the analysis proceeds essentially the same as for rectangular grids. The framework ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '01: Proceedings of the 2001 ACM/IEEE conference on Supercomputing

November 2001

756 pages

ISBN:158113293X

DOI:10.1145/582034

Conference Chair:
Charles Slocomb
Los Alamos National Laboratory

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 November 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SC '01

Sponsor:

SIGARCH
IEEE-CS

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

November 10 - 16, 2001

Colorado, Denver

Acceptance Rates

SC '01 Paper Acceptance Rate 60 of 240 submissions, 25%;

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

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
455
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Menon AKerstein AOevermann M(2024)Investigation of coarse-graining parameters for super-grid LEM closure applied to LES of practical bluff-body flamesCombustion Theory and Modelling10.1080/13647830.2024.2428156(1-22)Online publication date: 16-Nov-2024
https://doi.org/10.1080/13647830.2024.2428156
Heaney CLi YMatar OPain C(2024)Applying Convolutional Neural Networks to data on unstructured meshes with space-filling curvesNeural Networks10.1016/j.neunet.2024.106198175(106198)Online publication date: Jul-2024
https://doi.org/10.1016/j.neunet.2024.106198
Menon AKerstein AOevermann M(2024)Assessing the Multi-Regime Capability of the Super-Grid Linear Eddy Model (SG-LEM) Using the Darmstadt Multi-Regime BurnerFlow, Turbulence and Combustion10.1007/s10494-024-00602-xOnline publication date: 29-Nov-2024
https://doi.org/10.1007/s10494-024-00602-x
Nagy B(2023)A digital geometry on the tetrakis square tiling—Distance and coarseningTransactions in GIS10.1111/tgis.13029Online publication date: 13-Feb-2023
https://doi.org/10.1111/tgis.13029
Menon AOevermann MKerstein A(2023)A super-grid approach for LES combustion closure using the Linear Eddy ModelCombustion Theory and Modelling10.1080/13647830.2023.226035128:1(99-126)Online publication date: 20-Sep-2023
https://doi.org/10.1080/13647830.2023.2260351
Kedward LAllen CRendall T(2020)Comparing Matrix-based and Matrix-free Discrete Adjoint Approaches to the Euler EquationsAIAA Scitech 2020 Forum10.2514/6.2020-1294Online publication date: 5-Jan-2020
https://doi.org/10.2514/6.2020-1294
Luo GZhang Z(2020)Mesh Coarsening for Fast Simulation on Low Resource MachineIOP Conference Series: Materials Science and Engineering10.1088/1757-899X/790/1/012128790:1(012128)Online publication date: 1-Mar-2020
https://doi.org/10.1088/1757-899X/790/1/012128
Antonio Pietro DDroniou JDi Pietro DDroniou J(2020)Complements on Pure DiffusionThe Hybrid High-Order Method for Polytopal Meshes10.1007/978-3-030-37203-3_4(147-184)Online publication date: 4-Apr-2020
https://doi.org/10.1007/978-3-030-37203-3_4
Karcher NWallraff M(2020)Accelerating CFD solver computation time with reduced‐order modeling in a multigrid environmentInternational Journal for Numerical Methods in Fluids10.1002/fld.489293:2(462-480)Online publication date: 27-Aug-2020
https://doi.org/10.1002/fld.4892
Antonietti PHouston PHu XSarti MVerani M(2017)Multigrid algorithms for $$\varvec{hp}$$hp-version interior penalty discontinuous Galerkin methods on polygonal and polyhedral meshesCalcolo: a quarterly on numerical analysis and theory of computation10.5555/3169140.316916154:4(1169-1198)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.5555/3169140.3169161
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents