On the Recursive Structure of Multigrid Cycles

DOI10.1137/21M1433502MaRDI QIDQ6108144zbMATH OpenFDO

Authors Irad Yavneh

Publication date 29 June 2023

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

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

zbMATH Keywords

\(\kappa\)-cyclecycle countermultigrid cyclesrecursive multigrid algorithmsrotated diffusion

Mathematics Subject Classification ID

Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55)

Abstract: A new fixed (non-adaptive) recursive scheme for multigrid algorithms is introduced. Governed by a positive parameter $kappa$ called the cycle counter, this scheme generates a family of multigrid cycles dubbed $kappa$-cycles. The well-known $V$-cycle, $F$-cycle, and $W$-cycle are shown to be particular members of this rich $kappa$-cycle family, which satisfies the property that the total number of recursive calls in a single cycle is a polynomial of degree $kappa$ in the number of levels of the cycle. This broadening of the scope of fixed multigrid cycles is shown to be potentially significant for the solution of some large problems on platforms, such as GPU processors, where the overhead induced by numerous sequential calls to the coarser levels may be relatively significant. In cases of problems for which the convergence of standard $V$-cycles or $F$-cycles (corresponding to $kappa=1$ and $kappa=2$, respectively) is particularly slow, and yet the cost of $W$-cycles is very high due to the large number of coarse-level calls (which is exponential in the number of levels), intermediate values of $kappa$ may prove to yield significantly faster run-times. This is demonstrated in examples where $kappa$-cycles are used for the solution of rotated anisotropic diffusion problems, both as a stand-alone solver and as a preconditioner. Moreover, a simple model is presented for predicting the approximate run-time of the $kappa$-cycle, which is useful in pre-selecting an appropriate cycle counter for a given problem on a given platform. Implementing the $kappa$-cycle requires making just a small change in the classical multigrid cycle.

Recommendations

• Recursive Krylov-based multigrid cycles
• On the multigrid F-cycle
• A \(p\)-cycle analysis of multigrid method
• Note on the multigrid \(W\)-cycle
• A note on convergence of the multigrid V-cycle
• Multigrid Methods for Multilevel Circulant Matrices
• scientific article; zbMATH DE number 3970050
• scientific article; zbMATH DE number 713485
• Optimizing the number of multigrid cycles in the full multigrid algorithm
• Multigrid Bifurcation Iteration

Cites work

• A Multigrid Tutorial, Second Edition
• Coarse-Grid Correction for Nonelliptic and Singular Perturbation Problems
• Fully Adaptive Multigrid Methods
• scientific article; zbMATH DE number 3958638 (Why is no real title available?)
• scientific article; zbMATH DE number 1561761 (Why is no real title available?)
• scientific article; zbMATH DE number 3797119 (Why is no real title available?)
• scientific article; zbMATH DE number 1398115 (Why is no real title available?)
• scientific article; zbMATH DE number 3410718 (Why is no real title available?)
• Multi-Level Adaptive Solutions to Boundary-Value Problems
• Multigrid smoothing for symmetric nine-point stencils
• Non-Galerkin coarse grids for algebraic multigrid
• Non-Galerkin multigrid based on sparsified smoothed aggregation
• Reducing parallel communication in algebraic multigrid through sparsification
• Scaling Structured Multigrid to 500K+ Cores Through Coarse-Grid Redistribution

Cited in

(2)

• A \(p\)-cycle analysis of multigrid method
• Recursive Krylov-based multigrid cycles

This page was built for publication: On the Recursive Structure of Multigrid Cycles

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