Segmental refinement: a multigrid technique for data locality

DOI10.1137/140975127MaRDI QIDQ3186115zbMATH OpenOpenAlexFDO

Authors Mark F. Adams, Jed Brown, Matthew G. Knepley, R. Samtaney

Publication date 8 August 2016

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.7808

zbMATH Keywords

communication complexitydistributed memory multigridmultigridnonlinear elliptic boundary value problemsparallel multigridsegmental refinement

Mathematics Subject Classification ID

Nonlinear elliptic equations (35J60) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20)

Abstract: We investigate a domain decomposed multigrid technique, segmental refinement, for solving general nonlinear elliptic boundary value problems. Brandt and Diskin first proposed this method in 1994; we continue this work by analytically and experimentally investigating its complexity. We confirm that communication of traditional parallel multigrid can be eliminated on fine grids with modest amounts of extra work and storage while maintaining the asymptotic exactness of full multigrid, although we observe a dependence on an additional parameter not considered in the original analysis. We present a communication complexity analysis that quantifies the communication costs ameliorated by segmental refinement and report performance results with up to 64K cores of a Cray XC30.

Recommendations

• Parallel Multilevel Tetrahedral Grid Refinement
• Parallel multigrid technique: reduction to independent problems
• On the parallelization of multi-grid methods using a non-overlapping domain decomposition data structure
• scientific article; zbMATH DE number 554618
• Parallel multigrid on locally refined meshes

Cites work

• A relaxation method for solving elliptic difference equations
• An Optimal Order Process for Solving Finite Element Equations
• scientific article; zbMATH DE number 3930566 (Why is no real title available?)
• scientific article; zbMATH DE number 1355107 (Why is no real title available?)
• scientific article; zbMATH DE number 554618 (Why is no real title available?)
• scientific article; zbMATH DE number 1561761 (Why is no real title available?)
• scientific article; zbMATH DE number 3410718 (Why is no real title available?)
• scientific article; zbMATH DE number 3043879 (Why is no real title available?)
• Multi-Level Adaptive Solutions to Boundary-Value Problems
• Multigrid techniques. 1984 guide with applications to fluid dynamics
• Textbook multigrid efficiency for the incompressible Navier-Stokes equations: High Reynolds number wakes and boundary layers
• Toward textbook multigrid efficiency for fully implicit resistive magnetohydrodynamics

Cited in

(3)

• Fast multipole preconditioners for sparse matrices arising from elliptic equations
• Resilience for massively parallel multigrid solvers
• Exploiting spatial symmetries for solving Poisson's equation

Describes a project that uses

Uses Software

• SRGMG

This page was built for publication: Segmental refinement: a multigrid technique for data locality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3186115)