Skip to content

The multigrid Poisson solver on AMR grids ​

IDGroupMilestoneBackendsFigureRegression
SV-9, SV-12, SV-13Self-gravityM8 (#81), P5a; #87, P1, P2CPU onlyyes—

Case and scope ​

On an AMR grid the exact E+W exchange needs the composite Laplacian A (finite-volume form, rows weighted by the cell volume V) to be symmetric: Φ=4πGKρ with VK symmetric, the AMR form of K=KT now that the volumes differ. Accuracy needs it consistent: a bounded truncation error at the 2:1 faces and a converging face gradient there, the face gravity the momentum and energy sources use. The coupling across a 2:1 face decides both, and the usual choices give one or the other.

The case has two parts:

  • the operator study (seam_operators.py): three couplings of a coarse cell C and the fine cells fk on its face, measured in a 2-D model, to choose the one the solver uses;
  • the solver leg (test_poisson_mg): the multigrid solver on that operator, on uniform grids against the FFT solver (SV-9a) and on box-refined grids against the exact potential (SV-9b);
  • the Dirichlet legs (test_poisson_mg, #87 P1): the same solver with Dirichlet domain faces, the ground the isolated solve on AMR is built on: on a uniform grid the coarsest-level solve (the FFT solver's Dirichlet mode) is the whole solve (SV-12a); on box-refined grids against the exact potential (SV-12b);
  • the isolated legs (test_poisson_mg --isolated, #87 P2): free-space boundaries on AMR by a symmetric James step, SV-6's stars: on uniform grids against the FFT solver's isolated mode (SV-13a), on grids with the star refined against the exact potentials (SV-13b), the symmetry of the solution map measured in situ;
  • the boundary-kind legs (test_poisson_mg --bc, #84 E1b): a kind per face, periodic, Dirichlet or Neumann at the face, or ghost-Dirichlet, mixed across and within axes: on uniform grids against the FFT solver with the same kinds, on grids with a refined corner (leaves of two levels on the boundary) against a manufactured potential whose boundary values of each kind are the ghost values, the domain-face ghosts included.

What the case catches:

  • a non-symmetric assembled operator (the symmetry defect of the assembled rows, which the assembly does not symmetrise);
  • an inconsistent seam coupling: a truncation error that grows as 1/h under refinement;
  • a multigrid that is not the FFT solve on a uniform grid, a ghost the fill leaves empty, a stalled FCG;
  • a boundary kind whose row, right-hand side or ghost is wrong (the order against the manufactured potential, the truncation, the agreement with the FFT solver);
  • a mixed grid accepted without bc, boundary kinds that disagree with the grid's periodicity, or that the coarsest-level FFT solver cannot take, accepted;
  • an isolated solve that is not the free-space solution on a uniform grid, or not a symmetric map (VK≠(VK)T: E+W would not be conserved);
  • an isolated solve accepted with a refined leaf on the domain boundary.

Models and numerics ​

The three couplings (the operator study):

  • B, Tomida and Stone's flux matching: the fine ghost interpolated from C and its tangential neighbours, the coarse flux the sum of the fine ones. Consistent, not symmetric.
  • S1 =(B+BT)/2, the symmetrisation the P5-0 design proposed. The transposed tangential terms land in the coarse rows with no matching Taylor terms.
  • M, the mimetic mean flux (adam_poisson_mg_object): every fine face carries 23w(Φ¯f−ΦC), Φ¯f the mean of the face's fine cells and w the fine face area over the fine spacing; C gets their sum. It is the hybrid mimetic finite-difference flux of the coarse cell, seen as a polygon with hanging nodes, with its face unknowns eliminated: consistency makes the coarse cell's sub-face block rank one (it sees only the mean of its face unknowns), and the elimination gives Φ¯f. Exact for linear Φ face by face, and symmetric by construction.
ItemChoiceCode
Operatorthe composite Laplacian of the leaves, V-weighted, with M across 2:1 faces; assembled from the geometry as distributed sparse rows over global cell keys, each with its halo-exchange planinitialize (assemble_a), a_row, face_cells, face_weight, adam_poisson_mg_object.F90
2:1 ghoststhe first ghost layer across a 2:1 face is the value whose one-sided difference equals M's face gradientinitialize (assemble_ghost_fill), adam_poisson_mg_object.F90
Iterationflexible conjugate gradients (Notay's FCG(1)) on A, stopping at a relative max-norm residual of 10−10solve, solve_packed, adam_poisson_mg_object.F90
Preconditionerone V-cycle. Levels: each holds its leaves plus a shadow block for every refined node (ADAM keeps leaves only). Smoothing: red-black Gauss–Seidel, 2 sweeps down and 2 up. Transfers: restriction by sum, piecewise-constant prolongationvcycle, smooth, adam_poisson_mg_object.F90
Coarsest level and root (#84 E5c)the minimum leaf level, which covers the domain; below it the levels coarsen inside the blocks (the same blocks and ranks, half the cells per block per level along the active directions) while those are even and the level has more than root_cells cells (default the root solver's root_cells_max, told the growth of the root's transform: on the host a transform of 1283 cells, so a periodic root of 1283 and a ghost-Dirichlet one of 643, the distributed FFT of a large root beating more smoothed levels (#84 E6b); on cuFFT 323 cells, the multigrid smoothing on the device (E6)); the last, the root, is solved exactly by the FFT solver, on every rank when it has at most 323 cells (redundant: the source gathered by MPI_ALLGATHERV, no scatter), on the FFT solver's distributed path above that (a larger root_cells). A coarsest level of at most that many cells is its own rootinitialize (lbot, assemble_levels), vcycle, adam_poisson_mg_object.F90; solve_everywhere, adam_poisson_fft_object.F90
Boundary faces (#87 P1; per face, #84 E1b)an active axis is periodic or bounded, each bounded face of a kind: ghost-Dirichlet (the #87 default; g at the ghost centre: −wΦC in the row, wg to the right-hand side), Dirichlet at the face (−2wΦC, 2wg) or Neumann at the face (g the outward derivative: no row term, whg); without a Dirichlet face the operator is singular and the means are removed; the V-cycle's levels take the same kinds and the coarsest level the FFT solver with them (odd and even extensions, E1a)a_row, assemble_ghost_fill, solve(..., ghost), apply_b, apply_bt, adam_poisson_mg_object.F90
Isolated, the James step (#87 P2)initialize(..., isolated=.true.): the zero-ghost solve Φ0=A−14πGVρ; the screening charge s=BTΦ0 on the ghost cells; their values g=−Gs, G the inverse of the V-weighted coarsest operator on the infinite lattice (the lattice Green's function over H), by the zero-padded FFT on the coarsest box widened by the ghost layer; then Φ=A−1(4πGVρ−Bg). The map K=A−1+A−1BGBTA−1 is symmetric since A and G are. Each solve warm-starts from its own last solutionsolve_packed, ghost_green, solve_fcg, adam_poisson_mg_object.F90; solve_blocks (isolated), adam_poisson_fft_object.F90
Scopewithout bc every active direction periodic or none (a mixed grid would get a silent zero on its bounded faces); with it, the grid's periodicity and bc agree, an axis's two faces both ghost-Dirichlet or neither; isolated: no periodic direction, no bc, 3-D, cubic cells, and every leaf on the domain boundary at the coarsest level (D-87-2; the ghost cells then form the coarse lattice G is exact on); 2:1-balanced faces; anything else is fatalinitialize (boundaries), assemble_ghost_fill (the boundary layer), classify (2:1 balance), adam_poisson_mg_object.F90
Verification hooksthe symmetry defect |x⋅Ay−y⋅Ax|/(|x||Ay|), y=Ax on the leavessymmetry_defect, apply_a, adam_poisson_mg_object.F90

The operator on AMR grids is described in models.

Initial and boundary conditions ​

LegDomain and sourceGridRanks
Operator study (seam_operators.py)the doubly periodic unit square; Φ=sin⁡2πxcos⁡2πy+12cos⁡(2πx+4πy)coarse (H=1/N) on x<1/2, fine (h=H/2) on x>1/2: two seams (x=1/2 and x=0≡1); N = 8, 16, 32, 48; dense solves— (NumPy)
SV-9aSV-2's: [0,1]×[0,2]×[0,3], periodic, the two oblique modes, G=1, the exact potential in closed formuniform, octree and quadtree at level 21, 2, 3
SV-9bthe samethe central box [L/4,3L/4] refined once over base levels 2 and 3: octree (120 and 960 leaves) and quadtree (28 and 112); 8 cells per block side, 3 ghosts1, 2, 3
SV-12athe same source and box without periodic boundaries, the exact potential as the ghost values (Dirichlet at the centres of the first ghost layer): AΦ=4πGV(ρ−ρ0)−Bguniform octree at levels 1 and 21, 2, 3
SV-12bthe sameSV-9b's box-refined grids, octree and quadtree1, 2, 3
SV-13aSV-6's: the cube [−1,1]3, isolated, the n=1 polytrope ρ=sin⁡(kr)/(kr), k=π/a, radius a=1/2, G=1, the exact potentialuniform octree at levels 1 and 2 (163, 323)1, 2, 3
SV-13bthe same polytrope, and the uniform sphere (ρ=1, cell averages of 83 samples)base levels 2 and 3 with the star's box [−1/2,1/2]3 refined once (120 and 960 leaves; finest 643 and 1283 equivalent)1, 2, 3
E1b, uniform (#84)SV-2's box and source, homogeneous, the face kinds per axis (x, y, z): P/P D/N N/D; D/D N/N G/G; P/P N/N N/N (singular); 2-D N/D P/Puniform octree at level 1, quadtree at level 21, 2, 3
E1b, AMRthe same kinds; the manufactured Φm=∏dcos⁡(2πxd/Ld+θd), θ=(0.3,0.7,1.1), its Laplacian the source and its boundary values of each kind the ghost valuesbase levels 2 and 3 with the corner octant [0,L/2] refined once (leaves of both levels on the low faces), octree and quadtree1, 2, 3
E5c, levels inside the blocks (#84)SV-9a's and SV-9b's box and source (periodic, D/D N/N G/G, P/P D/N N/D) and SV-13b's polytrope (isolated)base level 2: uniform octree, the box refined once (octree and quadtree); every level forced down to one cell per block (root_cells = 1: 3 levels for 83 blocks) against none (root_cells = huge)1, 2, 3
Refusals--mixed: a grid periodic along x only and no bc (without it, every active direction periodic or none); --refuse-bc-mismatch: the same grid, bc periodic along y as well; --refuse-bc-mixed-ghost: the same grid, a ghost-Dirichlet face and a Dirichlet one along y; --refuse-boundary-refined: the isolated cube at level 1 with the octant x,y,z>0 refined—2

The FNL path comes with FLUME on AMR (P5b, P5c: SV-10, SV-11).

Input files ​

FileRole
src/tests/flume/verification/selfgravity/seam_operators.pythe operator study ([N ...], default 8 16 32 48)
src/tests/poisson/test_poisson_mg.F90the unit test (mode test-poisson-mg-gnu), SV-9a, SV-9b, SV-12a, SV-12b; --isolated SV-13a, SV-13b; --bc the boundary kinds (E1b); --mixed, --refuse-bc-mismatch, --refuse-bc-mixed-ghost and --refuse-boundary-refined the refusals
src/tests/flume/verification/selfgravity/poisson.shlegs sv9, sv13, bcmg and sub: the test on every rank count of --np-list, and the refusals; POISSON_MG_EXE selects the build
src/tests/flume/verification/make_doc_runs.sh, group amrsv9-poisson and sv13-poisson: the test (and --isolated) with its log
src/tests/flume/verification/make_doc_figures.py, fig_selfgravity_amr, fig_selfgravity_amr_isolateddraws the figures (--only selfgravity-amr selfgravity-amr-isolated), the first running seam_operators.py
bash
python3 src/tests/flume/verification/selfgravity/seam_operators.py      # the three couplings
cd src/tests/flume/verification/selfgravity && ./poisson.sh --legs "sv9 sv13 bcmg"   # the solver, np 1, 2, 3

Results ​

SV-9: three 2:1 couplings against N, and the multigrid solver's errors on AMR

Left: the truncation error of S1 grows as 1/h; M's stays at about 40, an O(1) seam truncation that is still consistent (the classical supra-convergence of cell-centred schemes); B's decays in this model. Middle: the potentials of the three couplings coincide at second order; the seam face gradient converges at second order for B, at first order for M, and stalls for S1. Right: the multigrid solver on M in 3-D and 2-D: the potential second order, the 2:1 face gravity first order, the truncation bounded.

The operator study (measured, no bounds):

Coupling, N = 8 → 48‖A−AT‖/‖A‖max|τ|seam face gradient error, order (32 → 48)Φ order (32 → 48)
B6.8⋅10−318.1 → 3.24.1⋅10−2 at N=48, 1.931.99
S1030.7 → 107, growing as 1/h0.98 at N=48, 0.11: does not converge1.99
M037.4 → 41.0, bounded0.42 at N=48, 1.042.00

The solver (CPU only):

AssertedBoundCPU
SV-9a: multigrid against the FFT solver, max|Φmg−Φfft|/max|Φ|; FCG iterations10−8; ≤1≤3.0⋅10−15; 1
SV-9b: FCG residual, relative max norm10−10below it
symmetry defect of the assembled rows (not symmetrised by the assembly)10−12≤7.9⋅10−18
ghost cells left unfilled00
order of Φ against the exact potential, base level 2 → 3≥1.71.92 (3-D), 1.92 (2-D)
growth of max|τ| under refinement≤1.51.006 (3-D), 1.005 (2-D)
SV-12a (Dirichlet, uniform): FCG iterations; order of Φ, level 1 → 2≤1; ≥1.71; 1.95
SV-12a: growth of max|AΦexact+Bg−f|≤1.50.27 (it falls at second order, 0.64 → 0.17)
SV-12b (Dirichlet, AMR): FCG residual; symmetry defect of the Dirichlet rows; ghosts unfilled10−10; 10−12; 0below it; ≤6.7⋅10−18; 0
SV-12b: order of Φ; growth of max|τ|≥1.7; ≤1.51.91 (3-D), 1.93 (2-D); 1.006, 1.005
SV-13a (isolated, uniform): max|Φmg−Φfft|/max|Φ| against the FFT solver's isolated mode; FCG iterations of each solve10−9; ≤1≤2.6⋅10−13; 1 + 1
SV-13a: order of Φ against the exact potential, 163→323≥1.72.14
SV-13b (isolated, AMR): FCG residual (tolerance 10−12); ghosts unfilledbelow it; 0below it; 0
SV-13b: order of Φ, base level 2 → 3≥1.7 (polytrope), ≥1.2 (uniform sphere, as SV-6)2.01, 1.86
SV-13: symmetry of the solution map in situ, |x⋅VKy−y⋅VKx|/|x⋅VKy| for two pseudo-random sources, first grid of each leg10−9≤1.7⋅10−11
E1b (boundary kinds, uniform): max|Φmg−Φfft|/max|Φ| against the FFT solver with the same kinds; FCG iterations10−8; ≤1≤1.2⋅10−14; 1
E1b (AMR): FCG residual; symmetry defect; ghosts unfilledbelow the tolerance; 10−12; 0below it; ≤2.5⋅10−17; 0
E1b: order of Φ against Φm, base level 2 → 3; order of the domain-face ghosts against Φm at the ghost centres; growth of max|τ|≥1.7; ≥1.7; ≤1.5Φ 1.95 (P/P D/N N/D), 2.00 (D/D N/N G/G), 1.95 (P/P N/N N/N, singular), 2.00 (2-D N/D P/P); ghosts 1.95, 2.03, 1.95, 2.00; 1.00–1.02
mixed periodic and bounded directions without bc; bc against the grid's periodicity; a ghost-Dirichlet face against a face kind on one axisrefused, exit 1refused
E5c (--sub): both solves below their tolerance; max|Φsub−Φexact|/max|Φ|; FCG iterations against the exact coarsest levelbelow it; 10−7; ≤1.5× (20 where the exact needs 1)below it; 1.6⋅10−14 - 1.1⋅10−11; uniform 14 (1), AMR periodic 47 (36), quadtree 25 (24), D/D N/N G/G 41 (39), P/P D/N N/D 53 (40), isolated 52 (47)
isolated, a leaf above the coarsest level on the boundaryrefused, exit 1refused

Reported, not bounded:

  • 2:1 face gravity order: 1.03 (3-D) and 1.11 (2-D).
  • FCG iterations: 36–39 in 3-D (mean factor 0.52–0.54) and 24–25 in 2-D (0.37–0.40); with Dirichlet faces 35–36 (3-D) and 22–23 (2-D); isolated (SV-13b, tolerance 10−12) 24–25 for the zero-ghost solve and 23 for the second; with the E1b boundary kinds 31–40 (3-D) and 21 (2-D).
  • E1b truncation: max|τ|=12.0 (3-D) and 10.3 → 10.5 (2-D), the same in every configuration, with or without Dirichlet faces: the maximum sits on the 2:1 seams (the O(1) seam truncation of SV-9b for this potential), not on the boundary rows, so the growth bound does not test them; the boundary rows and weights are pinned by the orders of Φ and of the ghosts. Mutations, each alone, turn the suite red: the Neumann weight in B negated (every AMR configuration, orders 0.02–0.14), the Neumann ghost's hg negated (ghost orders 0.99–1.01), the Dirichlet ghost 2g+ΦC instead of 2g−ΦC (the three configurations with a Dirichlet face, ghost orders 0.02–0.03). Not covered: the preconditioner's boundary diagonal, which can change only the iteration count.
  • The James ghost values against the exact potential at the ghost centres: 9.1⋅10−4→6.2⋅10−5 (SV-13a), 1.0⋅10−4→2.5⋅10−5 (SV-13b polytrope), 2.8⋅10−4→8.9⋅10−5 (sphere).
  • AMR against the uniform grid at the same base level (323, polytrope): 1.18⋅10−3 against 2.31⋅10−3.

Every printed number is the same on 1, 2 and 3 ranks, up to round-off. The bound on the potential's order is 1.7, not 1.9, because two grids give a single pair.

SV-13: the isolated solve on AMR, errors against the finest cells per side, and its exactness measures

Left: the potential (solid) and the James ghost values (dashed) against the exact potential, uniform and with the star refined: second order, the ghost values converging with the potential. Right: the multigrid against the FFT solver's isolated mode on uniform grids (the same discrete free-space solution, to 2.6⋅10−13, the lattice Green's function's own accuracy), and the symmetry defect of the solution map, within 20 times the FCG tolerance, against the bound. CPU, 2 ranks.

Related cases: the FFT solver the coarsest level uses is SV-2, its isolated mode SV-6; the solver coupled to FLUME on a static AMR grid is SV-10, under runtime AMR SV-11.

Findings ​

  • S1 is refuted. The P5-0 design comment claimed the symmetrisation costs nothing. Its potential is second order like the others, but its truncation grows as 1/h and the gravity at the seam does not converge. The potential's max-norm hides the defect; the gravity, the quantity the scheme uses, shows it.
  • M pays for symmetry with one order of seam gravity. Its seam face gradient is first order (B's is second order in this model), and 10 times B's at N=48. The error sits on the one layer of seam faces; the potential stays second order.
  • M's truncation is O(1) at the seam but consistent: bounded under refinement, the classical supra-convergence of cell-centred schemes.
  • On FNL the FCG iteration and the V-cycle run on the device (#84 E6a, adam_fnl_poisson_mg_object: CSR rows, red-black sweeps per colour, transfers, dots by device reductions, GPU-aware halo exchange), the root on cuFFT (SV-10). The results equal the host's to round-off, and the iteration counts are the host's wherever both take the same root: 60 of 72 over the default, isolated, boundary-kind and sub-block suites at 1 and 2 ranks. The other 12 are the coarsest levels of 643 cells, which the host solves exactly (its root sized by the transform, E6b) and cuFFT coarsens to 323 (E6: with the device multigrid a 1283 cuFFT root cost 2.4 to 6.8 times more per solve on 3.9 M AMR cells); there FNL takes 2 to 4 more iterations (39 -> 42, 35 -> 38, 25 -> 27, 31 -> 35).
  • The levels inside the blocks trade iterations for the rank-0 gather (E5c). Forced to one cell per block they add 1 to 13 FCG iterations on AMR and 13 on a uniform grid, where the exact coarsest level needs 1: the point smoother on SV-2's 1:2:3 cells (the prototype src/tests/poisson/mg_subblock_e5c.py measures the same, 26 for white noise, against 8 on cubic cells; trilinear prolongation gains nothing over piecewise constant there). The default root of 323 cells on the host keeps the exact coarsest level wherever it is cheap; above it the gather of the whole base grid per V-cycle, 70% of the isolated solve at 1283, goes: on 3.9 M AMR cells (medooza CPU) the isolated solve falls from 39.9 s to 6.5 s at 16 ranks and from 50.7 s to 31.2 s at one, the periodic one from 2.6 s to 2.3 s at 16 ranks but rises from 9.2 s to 12.7 s at one: there one FFT of the 1283 base level beats smoothing it with the generic CSR sweep. Since E5d the FFT is distributed, and E6b sizes the host's root by its transform: a periodic root of 1283 cells, a ghost-Dirichlet one of 643 (medooza CPU, np 1 / 4 / 16, periodic 12.4 / 3.9 / 2.5 -> 8.6 / 2.7 / 1.6 s, isolated 30.4 / 9.6 / 6.3 -> 26.8 / 8.5 / 5.2 s), which recovers the np-1 case without a stencil smoother. On FNL the root is 323 (E6). A mutation with no off-diagonal in the levels below the coarsest fails 5 of the 6 configurations on the iteration bound.
  • Dirichlet boundaries cost nothing in symmetry or order (SV-12): a boundary face adds −wΦC to its row and moves wg to the right-hand side, so the rows stay symmetric (6.7⋅10−18) and consistent (the uniform truncation falls at second order). The coarsest level's odd extension is exact: one iteration on a uniform grid. Mixed boundaries are refused; the periodic legs are unchanged to every printed digit.
  • The James step is symmetric and second order on AMR (SV-13), the P0 prototype's result in the library: on a uniform grid it is the discrete free-space solution (the FFT solver's, to 2.6⋅10−13), on AMR the potential is second order (2.01 for the polytrope) and the solution map is symmetric to the solve tolerance, which the exact E+W exchange needs. The cost is two composite solves and one padded FFT of the coarsest box per Poisson solve. The price is D-87-2: every leaf on the domain boundary at the coarsest level, fatal otherwise; the FLUME coupling (P3) lifts the run-time refusals.