PaperlayerView exact revision on arXiv

Source-linked AI summary

A simple multigrid scheme for solving the Poisson equation with arbitrary domain boundaries

Thomas Guillet, Romain Teyssier

arXiv:1104.1703v1physics.comp-phastro-ph.CO

TL;DR

Irregular level domains and adaptive timesteps make whole-hierarchy Poisson solves impractical in graded-octree AMR. The paper builds a level-wise multigrid solver with reconstructed coarse-grid boundaries; it reports optimal convergence with second-order reconstruction and identifies small-feature loss on complex boundaries as a challenge.

  • Problem

    Graded-octree AMR creates irregular level domains, while disparate timescales make whole-hierarchy Poisson solves impractical under adaptive time stepping.

    Source: §1 · p. 4

  • Method

    The solver builds a multigrid hierarchy over each AMR level and reconstructs coarse-level boundaries using Cartesian interface-capturing techniques.

    Source: §1 · p. 6, §2 · p. 7, §3 · p. 11

  • Results

    The authors report optimal convergence with second-order boundary reconstruction, although complex boundaries can lose small features on coarse grids and cause convergence problems.

    Source: §4 · p. 14, §6 · p. 29

  • Takeaways & Limitations

    The orthogonal multigrid hierarchy keeps memory requirements minimal and yields performance gains over standard conjugate gradient, especially in cosmological zoom-in simulations with large fully refined domains.

    Source: §6 · pp. 29–30

    For particularly complex grids, choosing first- or second-order reconstruction is difficult because practical topology-based criteria are hard to establish.

    Source: §4 · p. 17

Abstract

from arXiv · show

We present a new multigrid scheme for solving the Poisson equation with Dirichlet boundary conditions on a Cartesian grid with irregular domain boundaries. This scheme was developed in the context of the Adaptive Mesh Refinement (AMR) schemes based on a graded-octree data structure. The Poisson equation is solved on a level-by-level basis, using a "one-way interface" scheme in which boundary conditions are interpolated from the previous coarser level solution. Such a scheme is particularly well suited for self-gravitating astrophysical flows requiring an adaptive time stepping strategy. By constructing a multigrid hierarchy covering the active cells of each AMR level, we have designed a memory-efficient algorithm that can benefit fully from the multigrid acceleration. We present a simple method for capturing the boundary conditions across the multigrid hierarchy, based on a second-order accurate reconstruction of the boundaries of the multigrid levels. In case of very complex boundaries, small scale features become smaller than the discretization cell size of coarse multigrid levels and convergence problems arise. We propose a simple solution to address these issues. Using our scheme, the convergence rate usually depends on the grid size for complex grids, but good linear convergence is maintained. The proposed method was successfully implemented on distributed memory architectures in the RAMSES code, for which we present and discuss convergence and accuracy properties as well as timing performances.

1. Introduction

Poisson solvers matter in astrophysics, but graded-octree AMR meshes create irregular level domains and adaptive time stepping makes whole-hierarchy solves impractical. The introduction motivates a multigrid solver for level-wise Poisson problems with Dirichlet boundaries.

1. Introduction

  • FFT methods suit periodic rectangular grids, while relaxation handles complex geometries but slows as grids grow; multigrid improves its convergence.Multigrid damps large-scale residual modes on coarser grids and can scale linearly with problem size in ideal cases.Source: §1 · pp. 2–4
  • Graded-octree AMR meshes adapt to flow geometry but create level domains with holes and irregular boundaries.Self-gravity creates disparate timescales, making a single timestep for the whole grid inefficient.Source: §1 · p. 4
  • Because fine and coarse AMR levels are often unsynchronized, one-way schemes solve levels separately and impose Dirichlet conditions from the coarser solution.In contrast, two-way schemes propagate information between coarse and fine grids, but solving the whole hierarchy at once is often unavailable under adaptive time stepping.Source: §1 · pp. 4–5
  • RAMSES advances fine levels using coarse boundary values fixed at the initial coarse timestep, a strategy that does not guarantee time-accurate interpolation.The proposed solver handles each AMR level independently and applies regardless of the boundary-condition derivation scheme.Source: §1 · p. 6
  • The solver targets Poisson problems on irregular Cartesian domains in tree-based AMR codes using one-way interfaces.The introduction frames this as a simpler, efficient approach for that setting.Source: §1 · p. 6
  • The paper focuses on reconstructing boundaries at coarsened multigrid levels; fine-level cut-cell or level-set boundaries would require an appropriate fine operator.For one-way AMR applications, the finest-level boundary usually lies on Cartesian cell faces.Source: §1 · p. 6

2. A Multigrid algorithm for complex boundary conditions

The solver builds a separate multigrid hierarchy over each AMR level’s active domain, then iteratively computes coarse-grid corrections for the fine-level Poisson problem. Its design combines multigrid acceleration with memory use that scales with the cells on the level being solved.

2. A Multigrid algorithm for complex boundary conditions

  • Each AMR level’s active domain becomes the finest multigrid level, with a separate coarser hierarchy that is distinct from the underlying AMR coarse levels.This hierarchy covers the reference domain for the current level.Source: §2 · p. 7
  • The solver’s cost at a given level scales with that level’s cell count because it uses only a subset of the AMR coarser cells.This is especially useful when fine grids occupy much less volume than coarse levels.Source: §2 · p. 7
  • A multigrid iteration smooths the fine estimate, restricts its solution and residual, defines a coarse domain and boundary, solves for a coarse correction, then corrects and smooths the fine solution.The iteration repeats until the fine residual norm is considered small enough.Source: §2 · pp. 7, 9
  • Two pre-smoothing and two post-smoothing passes gave the best solver-time performance for the authors’ RAMSES applications.The scheme also specifies the number of multigrid cycles, restriction and prolongation operators, and Laplacian discretization.Source: §2 · p. 9
  • Away from boundaries, the Poisson equation uses a second-order-accurate standard 7-point Laplacian, and smoothing uses red-black Gauss-Seidel.The implementation is currently restricted to this second-order Laplacian; the smoother updates the two checkerboard colors in separate passes.Source: §2 · pp. 9–10
  • The scheme uses simple averaging for restriction (R1) and linear interpolation for prolongation (P2), a combination that gave the best convergence rates on the studied grid classes.Simple averaging is also convenient for the boundary representation prescription.Source: Figure 3 · p. 10, §2 · p. 11

3. Second-order multigrid boundary reconstruction and the modified Laplacian operator

The method tracks domain boundaries across multigrid levels by restricting a cell mask and modifying the Laplacian near the boundary. Linear ghost-value reconstruction preserves boundary location to second-order accuracy, though complex boundaries require first-order reconstruction for convergence.

3. Second-order multigrid boundary reconstruction and the modified Laplacian operator

  • The boundary-capturing framework can use either cut-cell or level-set interface reconstruction as its basic scheme.The paper focuses on a simpler mask-based approach in its one-way AMR solver.Source: §3 · p. 11
  • At the finest multigrid level, inner cells have mask value 1 and outer cells −1, placing the interpolated zero crossing at cell faces.At coarser levels, cells belong to the domain when their restricted mask value is positive.Source: §3 · pp. 11–12
  • In the boundary stencil, an outside-domain neighbor with negative mask is replaced by a reconstructed ghost value, while the other three cell values remain unchanged.The ghost value is obtained by linearly extrapolating the boundary condition from the interior cell.Source: Figure 4 · p. 12, Figure 5 · p. 13
  • The scheme restricts the cell mask to coarser levels and replaces out-of-domain neighbors in the Laplacian with ghost values linearly extrapolated from the interior value and boundary condition.The boundary is located where the interpolated mask crosses zero; this linear reconstruction recovers its position at second-order spatial accuracy.Source: §3 · pp. 11–12
  • The restriction operator for the mask and the modified near-boundary Laplacian keep the boundary location consistent across multigrid levels to second order.The resulting coarse Poisson solution corresponds to the fine-level solution with its fine boundary representation.Source: §3 · pp. 12–13
  • For smooth boundaries, second-order multigrid boundary reconstruction yields perfect multigrid convergence, while first-order reconstruction does not.For very complex boundaries, second-order reconstruction is no longer possible and the scheme is degraded to first order to ensure convergence.Source: §3 · p. 13

4. First-order multigrid boundary reconstruction and the “small islands” problem

Small islands can vanish under mask coarsening, losing Dirichlet constraints and destabilizing multigrid. First-order boundary reconstruction restores convergence on complex boundaries, though the rate is slower and grid-size dependent.

4. First-order multigrid boundary reconstruction and the “small islands” problem

  • Restriction can erase boundary constraints when small holes or islands disappear from coarse masks, making coarse and fine Poisson solutions significantly different.Figure 6 shows an isolated negative-mask cell whose Dirichlet boundary is lost after one coarsening step.Source: §4 · p. 14, Figure 6 · p. 14
  • Existing fixes are ill-suited: iterant recombination requires substantial storage and worsens with more islands, while truncating coarsening can break multigrid on complex boundaries.Source: §4 · pp. 14–15
  • The proposed remedy switches to first-order reconstruction and imposes Φ = 0 on coarse cells whose mask value is below 1.Simple mask averaging makes a cell's mask fall below 1 exactly when it intersects the boundary.Source: §4 · p. 15
  • For the smooth disk, second-order reconstruction gives fast, grid-size-independent textbook convergence, whereas first-order degrades the rate.Source: §4 · p. 15
  • On complex boundaries with many holes and islands, second-order reconstruction diverges, while first-order restores convergence at a slower, grid-size-dependent rate.The residual curves in Figure 7 compare the two reconstruction orders across domain shapes and grid sizes.Source: §4 · pp. 13, 16, Figure 7 · p. 16
  • Because order selection and local adaptation are difficult, the implementation tests second-order reconstruction and switches to first-order when the residual ratio exceeds a threshold, typically 0.5.The switch applies to that AMR level and the next 10 solves.Source: §4 · pp. 16–17

5. Accuracy and performance tests

The tests show that multigrid is generally faster than conjugate gradient on the tested cosmological simulations, with a clustered-grid exception, and retains near-second-order accuracy for key solution measures. Its performance depends on multigrid scheduling and parallel workload size, while AMR interfaces and complex boundaries qualify the accuracy and convergence results.

5.1. Accuracy tests

  • Potential truncation error converges at second order on both Cartesian and AMR grids, although AMR error is larger at a given resolution level.The authors attribute the larger AMR error to coarser cells outside regions at maximal resolution.Source: §5.1 · p. 18, Figure 8 · p. 19
  • At AMR level interfaces, force accuracy degrades to first order in thin codimension-one shells, while local error stays below about 1% and L2 convergence remains near order 2.The reported L2 scaling is approximately ∆x^1.6; the interface effect follows from interpolating missing fine values from the coarser level.Source: §5.1 · pp. 20–21, Figure 10 · p. 20
  • When a density peak is more than about 3r0 from a level boundary, its gradient has no noticeable effect on global solution quality; closer peaks can introduce potential errors.In the reported test, force was less sensitive, and the solver converged in 6 or 7 iterations across the tested positions.Source: §5.1 · p. 22, Figure 12 · p. 23

5.2. Performance in cosmological simulations

  • On simulation B, multigrid was almost ten times faster than conjugate gradient, which took 140 seconds even with a coarse-level-interpolated initial guess.Adaptive time stepping leaves the interpolated coarse-level guess out of synchronization with the finer solution; multigrid is less sensitive to guess quality.Source: §5.2 · p. 25
  • Multigrid had a strong timing advantage over conjugate gradient overall, but in simulation C conjugate gradient took 850 seconds, about 20% less than multigrid.The authors attribute simulation C's exception to clustered fine grids and small-island handling, and suggest a hybrid using multigrid on most levels and conjugate gradient on the finest ones.Source: §5.2 · pp. 24–25

5.3. Effect of Ncycles

  • V-cycles were generally faster overall than W-cycles in the tested RAMSES applications, although W-cycles were less sensitive to boundary-reconstruction order.First-order reconstruction with V-cycles harms convergence but permits convergence with small islands; the authors caution that the schedule preference can depend on implementation and grid geometry.Source: §5.3 · p. 26

5.4. Parallel computing

  • Parallel efficiency fell to 50% at 32^3 cells per processor, while weak scaling was almost perfect when workload stayed above 64^3 cells per processor.At the lower workload, communication took longer than updating the solution during each Gauss-Seidel sweep.Source: §5.4 · p. 28, Figure 15 · p. 29

6. Conclusion

The paper presents a memory-efficient multigrid algorithm for Poisson problems on irregular Cartesian domains in AMR codes using one-way interfaces. Its second-order boundary reconstruction supports accuracy and convergence, with a first-order fallback addressing small-island cases.

6. Conclusion

  • The method solves Poisson problems on irregular domains in AMR codes with a one-way interface strategy and is designed for astrophysical applications with multiple adaptive time steps.Its multigrid hierarchy is orthogonal to the AMR grid, keeping memory requirements minimal.Source: §6 · p. 29
  • Second-order reconstruction of multigrid-level boundaries gives optimal convergence, while a first-order fallback addresses nonconvergence from complex boundaries and small islands.The method determines on the fly which reconstruction order to use.Source: §6 · p. 29
  • The potential is second-order accurate with AMR levels, and global force accuracy is close to second order despite first-order degradation in localized interface regions.The force degradation is confined to codimension-one regions around level interfaces.Source: §6 · p. 29
  • The solver showed significant performance gains over the standard conjugate-gradient solver, especially for cosmological zoom-in simulations with large fully refined domains.The method could also be used for incompressible-flow solvers with multiphase fluids or complex embedded solid boundaries.Source: §6 · pp. 29–30
Loading 1104.1703v1…