Matrix-Free Multigrid with Algebraically Consistent Coarsening on Adaptive Octrees
Pith reviewed 2026-05-10 03:15 UTC · model grok-4.3
The pith
A flux-consistent correction at T-junctions restores algebraic consistency for matrix-free multigrid on adaptive octrees.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that a flux-consistent coarse-grid correction at T-junctions between refinement levels restores cross-level consistency while preserving the compact matrix-free representation of the coarse operators, thereby enabling algebraically consistent multigrid on adaptive octree grids with irregular domains.
What carries the argument
The flux-consistent coarse-grid correction at T-junctions, which adjusts the coarse-grid correction to enforce flux matching across refinement boundaries while keeping operators in matrix-free form.
If this is right
- The method maintains second-order accuracy on irregular domains and cut-cell geometries.
- Convergence remains grid-independent when the multigrid is used as a PCG preconditioner.
- The compact matrix-free storage supports high-throughput execution on GPUs for large adaptive grids.
- The solver is suitable for pressure projection steps in fluid simulations.
Where Pith is reading between the lines
- The same flux-matching idea may apply to other elliptic operators on hierarchical grids beyond Poisson.
- Matrix-free storage could enable scaling to much larger three-dimensional adaptive simulations than assembled-matrix approaches allow.
- The approach could be combined with existing cut-cell fluid codes to improve solver robustness without increasing memory footprint.
Load-bearing premise
The flux-consistent coarse-grid correction at T-junctions preserves algebraic consistency, second-order accuracy, and grid-independent convergence for irregular domains and cut-cell geometries.
What would settle it
A numerical test on a cut-cell domain with many T-junctions that shows either a loss of second-order accuracy or a growth in iteration count with grid refinement would falsify the central claim.
Figures
read the original abstract
We present a matrix-free GPU multigrid preconditioner with algebraically consistent coarsening for solving Poisson equations on adaptive octree grids with irregular domains. Within uniform-resolution regions, the coarsening satisfies the Galerkin principle. At T-junctions between refinement levels, we propose a flux-consistent coarse-grid correction that restores cross-level consistency while preserving the compact matrix-free representation. The coarse operators are stored in a compact matrix-free form suitable for parallel execution on GPUs. Numerical experiments demonstrate second-order accuracy, grid-independent convergence when used with PCG, and robust performance on cut-cell problems arising in fluid simulation. On a single NVIDIA RTX 4090 GPU, the solver achieves full-solve throughputs above 200 million cells per second on analytical Poisson tests and above 70 million cells per second on pressure projection problems in fluid simulation.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents a matrix-free GPU multigrid preconditioner for the Poisson equation on adaptive octree grids with irregular domains and cut cells. Uniform-resolution regions employ standard Galerkin coarsening, while T-junctions between refinement levels use a proposed flux-consistent coarse-grid correction to restore cross-level algebraic consistency without sacrificing the compact matrix-free representation. The coarse operators remain suitable for parallel GPU execution. Numerical experiments on analytical Poisson problems and pressure-projection tasks from fluid simulation report second-order accuracy, grid-independent PCG convergence, and throughputs above 200 million cells per second on an RTX 4090 GPU.
Significance. If the flux-consistent correction achieves exact algebraic consistency, the work offers a practical contribution to efficient multigrid solvers for adaptive grids with hanging nodes and cut cells. The matrix-free formulation and GPU focus address key performance bottlenecks in large-scale CFD and similar applications. The reported convergence behavior and throughput metrics indicate potential utility for production-level simulations on irregular geometries.
major comments (2)
- [§4.2, Eq. (12)] §4.2, Eq. (12): The flux-consistent correction is asserted to restore algebraic consistency at T-junctions. However, the manuscript does not provide an explicit verification that the resulting coarse operator equals the Galerkin projection R A_h P exactly (as opposed to an approximate flux-matching stencil). A direct algebraic identity check or a numerical test confirming operator equality on a small adaptive patch would be required to support the central claim of algebraic consistency, which underpins the grid-independent convergence assertion.
- [§5.2, Figure 4 and Table 2] §5.2, Figure 4 and Table 2: The convergence plots and error tables demonstrate rates near 2 but lack direct comparisons against a standard Galerkin multigrid implementation without the T-junction correction or against other adaptive multigrid baselines. This omission makes it difficult to isolate the contribution of the proposed correction to the observed grid-independent PCG behavior.
minor comments (2)
- [§3.3] The notation for the restriction and prolongation operators at T-junctions (introduced in §3.3) could be clarified with an explicit stencil diagram to aid readers unfamiliar with hanging-node treatments.
- [Figure 3] Several figure captions (e.g., Figure 3) omit the specific norm used for the reported L2 errors; this should be stated explicitly.
Simulated Author's Rebuttal
We thank the referee for the constructive and detailed comments, which help clarify the presentation of our matrix-free multigrid approach. We address each major comment below and indicate the revisions we will make to strengthen the manuscript.
read point-by-point responses
-
Referee: [§4.2, Eq. (12)] §4.2, Eq. (12): The flux-consistent correction is asserted to restore algebraic consistency at T-junctions. However, the manuscript does not provide an explicit verification that the resulting coarse operator equals the Galerkin projection R A_h P exactly (as opposed to an approximate flux-matching stencil). A direct algebraic identity check or a numerical test confirming operator equality on a small adaptive patch would be required to support the central claim of algebraic consistency, which underpins the grid-independent convergence assertion.
Authors: We appreciate the referee's request for explicit verification of algebraic consistency. The flux-consistent correction in Eq. (12) is derived by enforcing exact flux matching across T-junctions, which for the discrete Poisson operator is algebraically equivalent to the Galerkin projection. To directly address the concern, we will add a numerical verification in the revised manuscript: on a small adaptive octree patch containing T-junctions, we will compute the coarse operator from our method and compare it entrywise to the explicitly formed Galerkin operator R A_h P, confirming equality to machine precision. This test will be placed in §4.2. revision: yes
-
Referee: [§5.2, Figure 4 and Table 2] §5.2, Figure 4 and Table 2: The convergence plots and error tables demonstrate rates near 2 but lack direct comparisons against a standard Galerkin multigrid implementation without the T-junction correction or against other adaptive multigrid baselines. This omission makes it difficult to isolate the contribution of the proposed correction to the observed grid-independent PCG behavior.
Authors: We agree that isolating the effect of the T-junction correction would improve the manuscript. In the revision we will add a direct comparison in §5.2 (new figure or table) showing PCG iteration counts on an adaptive grid both with and without the flux-consistent correction. This will demonstrate that omitting the correction leads to grid-dependent convergence, thereby highlighting its necessity for the reported behavior. For comparisons against other adaptive multigrid baselines, our focus is the matrix-free GPU realization; we will expand the related-work discussion to better situate the contribution but do not plan exhaustive runtime benchmarks against every existing method. revision: partial
Circularity Check
No significant circularity detected in derivation chain
full rationale
The paper's central contribution is the proposal of a new flux-consistent coarse-grid correction at T-junctions to restore cross-level consistency on adaptive octrees, while retaining standard Galerkin coarsening in uniform regions. This is presented as an explicit construction that preserves the matrix-free representation, with supporting claims of second-order accuracy and grid-independent PCG convergence backed by numerical experiments on analytical and cut-cell problems. No equations, parameters, or results in the abstract reduce by construction to fitted inputs, self-definitions, or self-citation chains; the correction is introduced as a distinct term rather than derived tautologically from the target consistency property itself. The derivation remains self-contained against standard multigrid principles and external benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Galerkin principle for coarsening holds inside uniform-resolution regions
Reference graph
Works this paper leans on
-
[1]
Mridul Aanjaneya, Chengguizi Han, Ryan Goldade, and Christopher Batty
-
[2]
An efficient geometric multigrid solver for viscous liquids.Proceedings of the ACM on Computer Graphics and Interactive Techniques2, 2 (2019), 1–21
work page 2019
-
[3]
Ann S Almgren, John B Bell, Phillip Colella, Louis H Howell, and Michael L Welcome. 1998. A conservative adaptive projection method for the variable den- sity incompressible Navier–Stokes equations.Journal of computational Physics 142, 1 (1998), 1–46. 30
work page 1998
-
[4]
Oscar Antepara, Samuel Williams, Hans Johansen, and Mary Hall. 2024. High- performance, scalable geometric multigrid via fine-grain data blocking for GPUs. InSC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 1177–1191
work page 2024
-
[5]
John B Bell, Phillip Colella, and Harland M Glaz. 1989. A second-order projec- tion method for the incompressible Navier-Stokes equations.Journal of compu- tational physics85, 2 (1989), 257–283
work page 1989
-
[6]
Nathan Bell, Steven Dalton, and Luke N Olson. 2012. Exposing fine-grained parallelism in algebraic multigrid methods.SIAM Journal on Scientific Com- puting34, 4 (2012), C123–C152
work page 2012
-
[7]
Marsha J Berger and Phillip Colella. 1989. Local adaptive mesh refinement for shock hydrodynamics.Journal of computational Physics82, 1 (1989), 64–84
work page 1989
-
[8]
Marsha J Berger and Joseph Oliger. 1984. Adaptive mesh refinement for hy- perbolic partial differential equations.Journal of computational Physics53, 3 (1984), 484–512
work page 1984
-
[9]
Lorenzo Botto. 2013. A geometric multigrid Poisson solver for domains contain- ing solid inclusions.Computer Physics Communications184, 3 (2013), 1033– 1044
work page 2013
-
[10]
Achi Brandt. 1977. Multi-level adaptive solutions to boundary-value problems. Mathematics of computation31, 138 (1977), 333–390
work page 1977
-
[11]
2015.Fluid simulation for computer graphics
Robert Bridson. 2015.Fluid simulation for computer graphics. AK Peters/CRC Press
work page 2015
-
[12]
Hanyu Chu, Yongzhong Song, Haifeng Ji, and Ying Cai. 2024. Multigrid Al- gorithm for Immersed Finite Element Discretizations of Elliptic Interface Prob- lems.Journal of Scientific Computing98, 1 (2024), 26
work page 2024
-
[13]
Armando Coco, Mariarosa Mazza, and Matteo Semplice. 2023. A ghost-point smoothing strategy for geometric multigrid on curved boundaries.J. Comput. Phys.478 (2023), 111982
work page 2023
-
[14]
cpf 99. 2021. Low poly TIE fighter.https://sketchfab.com/3d-models/ low-poly-tie-fighter-4f483252021c43e1968a54bb6c329e8aSketchfab, ac- cessed 2026. 31
work page 2021
-
[15]
Erwan Deriaz. 2023. High-order Adaptive Mesh Refinement multigrid Poisson solver in any dimension.J. Comput. Phys.480 (2023), 112012
work page 2023
-
[16]
Doug Enright and Ron Fedkiw. 2003. Robust treatment of interfaces for fluid flows and computer graphics. InHyperbolic Problems: Theory, Numerics, Appli- cations: Proceedings of the Ninth International Conference on Hyperbolic Prob- lems held in CalTech, Pasadena, March 25–29, 2002. Springer, 153–164
work page 2003
-
[17]
Wenqiang Feng, Zhenlin Guo, John S Lowengrub, and Steven M Wise. 2018. A mass-conservative adaptive FAS multigrid solver for cell-centered finite dif- ference methods on block-structured, locally-cartesian grids.J. Comput. Phys. 352 (2018), 463–497
work page 2018
-
[18]
Mehdi Badri Ghomizad, Hosnieh Kor, and Koji Fukagata. 2021. A struc- tured adaptive mesh refinement strategy with a sharp interface direct-forcing immersed boundary method for moving boundary problems.Journal of Fluid Science and Technology16, 2 (2021), JFST0014–JFST0014
work page 2021
-
[19]
Frederic Gibou, Ronald P Fedkiw, Li-Tien Cheng, and Myungjoo Kang. 2002. A second-order-accurate symmetric discretization of the Poisson equation on irregular domains.Journal of computational physics176, 1 (2002), 205–227
work page 2002
-
[20]
Babak Hejazialhosseini, Diego Rossinelli, Michael Bergdorf, and Petros Koumoutsakos. 2010. High order finite volume methods on wavelet-adapted grids with local time-stepping on multicore architectures for the simulation of shock-bubble interactions.J. Comput. Phys.229, 22 (2010), 8364–8383
work page 2010
-
[21]
Hans Johansen and Phillip Colella. 1998. A Cartesian grid embedded boundary method for Poisson’s equation on irregular domains.Journal of computational physics147, 1 (1998), 60–85
work page 1998
-
[22]
Frank Losasso, Fr´ ed´ eric Gibou, and Ron Fedkiw. 2004. Simulating water and smoke with an octree data structure. InAcm siggraph 2004 papers. 457–462
work page 2004
-
[23]
Luan Lyu, Wei Cao, Xiaohua Ren, Enhua Wu, and Zhi-Xin Yang. 2024. Efficient odd–even multigrid for pointwise incompressible fluid simulation on GPU.The Visual Computer40, 12 (2024), 8675–8691
work page 2024
-
[24]
Aleka McAdams, Eftychios Sifakis, and Joseph Teran. 2010. A Parallel Multi- grid Poisson Solver for Fluids Simulation on Large Grids.. InSymposium on Computer Animation, Vol. 65. 74. 32
work page 2010
-
[25]
Maxim Naumov, Marat Arsaev, Patrice Castonguay, Jonathan Cohen, Julien Demouth, Joe Eaton, Simon Layton, Nikolay Markovskiy, Istv´ an Reguly, Niko- lai Sakharnykh, et al. 2015. AmgX: A library for GPU accelerated algebraic multigrid and preconditioned iterative methods.SIAM Journal on Scientific Computing37, 5 (2015), S602–S626
work page 2015
-
[26]
Yen Ting Ng, Chohong Min, and Fr´ ed´ eric Gibou. 2009. An efficient fluid–solid coupling algorithm for single-phase flows.J. Comput. Phys.228, 23 (2009), 8807–8829
work page 2009
-
[27]
Yvan Notay. 2010. An aggregation-based algebraic multigrid method.Electron. Trans. Numer. Anal37, 6 (2010), 123–146
work page 2010
-
[28]
Charles S Peskin. 2002. The immersed boundary method.Acta numerica11 (2002), 479–517
work page 2002
-
[29]
St´ ephane Popinet. 2003. Gerris: a tree-based adaptive solver for the incompress- ible Euler equations in complex geometries.Journal of computational physics 190, 2 (2003), 572–600
work page 2003
-
[30]
St´ ephane Popinet. 2015. A quadtree-adaptive multigrid solver for the Serre– Green–Naghdi equations.J. Comput. Phys.302 (2015), 336–358
work page 2015
-
[31]
Wouter Raateland, Torsten H¨ adrich, Jorge Alejandro Amador Herrera, Daniel T Banuti, Wojciech Pa lubicki, S¨ oren Pirk, Klaus Hildebrandt, and Dominik L Michels. 2022. Dcgrid: an adaptive grid structure for memory-constrained fluid simulation on the GPU.Proceedings of the ACM on Computer Graphics and Interactive Techniques5, 1 (2022), 1–14
work page 2022
-
[32]
Rahul S Sampath and George Biros. 2010. A parallel geometric multigrid method for finite elements on octree meshes.SIAM Journal on Scientific Com- puting32, 3 (2010), 1361–1392
work page 2010
-
[33]
Kumar Saurabh, Masado Ishii, Milinda Fernando, Boshun Gao, Kendrick Tan, Ming-Chen Hsu, Adarsh Krishnamurthy, Hari Sundar, and Baskar Ganapa- thysubramanian. 2021. Scalable adaptive pde solvers in arbitrary domains. In Proceedings of the International Conference for high performance computing, networking, storage and analysis. 1–15
work page 2021
-
[34]
Rajsekhar Setaluri, Mridul Aanjaneya, Sean Bauer, and Eftychios Sifakis. 2014. SPGrid: A sparse paged grid structure applied to adaptive smoke simulation. ACM Transactions on Graphics (TOG)33, 6 (2014), 1–12. 33
work page 2014
-
[35]
Han Shao, Libo Huang, and Dominik L Michels. 2022. A fast unsmoothed aggregation algebraic multigrid framework for the large-scale simulation of in- compressible flow.ACM Transactions on Graphics (TOG)41, 4 (2022), 1–18
work page 2022
-
[36]
Klaus St¨ uben. 2001. A review of algebraic multigrid.Numerical Analysis: His- torical Developments in the 20th Century(2001), 331–359
work page 2001
-
[37]
Jannis Teunissen and Ute Ebert. 2018. Afivo: A framework for quadtree/octree AMR with shared-memory parallelization and geometric multigrid methods. Computer Physics Communications233 (2018), 156–166
work page 2018
-
[38]
Jannis Teunissen and Rony Keppens. 2019. A geometric multigrid library for quadtree/octree AMR grids coupled to MPI-AMRVAC.Computer Physics Com- munications245 (2019), 106866
work page 2019
-
[39]
Jannis Teunissen and Francesca Schiavello. 2023. Geometric multigrid method for solving Poisson’s equation on octree grids with irregular boundaries.Com- puter Physics Communications286 (2023), 108665
work page 2023
-
[40]
Maxime Theillard, Chris H Rycroft, and Fr´ ed´ eric Gibou. 2013. A multigrid method on non-graded adaptive octree and quadtree Cartesian grids.Journal of Scientific Computing55 (2013), 1–15
work page 2013
-
[41]
Kengo Tomida and James M Stone. 2023. The Athena++ Adaptive Mesh Re- finement Framework: Multigrid Solvers for Self-gravity.The Astrophysical Jour- nal Supplement Series266, 1 (2023), 7
work page 2023
-
[42]
Mengdi Wang, Fan Feng, Junlin Li, and Bo Zhu. 2025. Cirrus: Adaptive Hybrid Particle-Grid Flow Maps on GPU.ACM Transactions on Graphics (TOG)44, 4 (2025), 1–17
work page 2025
-
[43]
Marion Weinzierl and Tobias Weinzierl. 2018. Quasi-matrix-free hybrid multi- grid on dynamically adaptive Cartesian grids.ACM Transactions on Mathe- matical Software (TOMS)44, 3 (2018), 1–44
work page 2018
-
[44]
Ulrike Meier Yang et al. 2002. BoomerAMG: A parallel algebraic multigrid solver and preconditioner.Applied Numerical Mathematics41, 1 (2002), 155–177
work page 2002
-
[45]
Omar Zarifi and Christopher Batty. 2017. A positive-definite cut-cell method for strong two-way coupling between fluids and deformable bodies. InProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 1–11. 34
work page 2017
-
[46]
Changjuan Zhang, Abbas Fakhari, Jie Li, Li-Shi Luo, and Tiezheng Qian. 2019. A comparative study of interface-conforming ALE-FE scheme and diffuse inter- face AMR-LB scheme for interfacial dynamics.J. Comput. Phys.395 (2019), 602–619
work page 2019
-
[47]
Weiqun Zhang, Ann Almgren, Vince Beckner, John Bell, Johannes Blaschke, Cy Chan, Marcus Day, Brian Friesen, Kevin Gott, Daniel Graves, et al. 2019. AM- ReX: a framework for block-structured adaptive mesh refinement.The Journal of Open Source Software4, 37 (2019), 1370. 35
work page 2019
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.