multigrid#

Geometric multigrid for \((I - s A_h)\, x = b\) with \(A_h = \nu \Delta_h - c \cdot \nabla_h\), on a CPU (NumPy) or a GPU (CuPy).

This is the system an implicit Euler step, and so every node solve of SDC, of an advection-diffusion term \(\nu \Delta u - c \cdot \nabla u\) leads to, with \(s\) the factor of the step. \(\Delta_h\) is the second-order Laplacian (3, 5 or 7 points) and \(\nabla_h\) the first-order upwind gradient, each component of \(c\) differenced on the side it comes from, on \(N\) points per direction of an interval, square or cube of side length \(L\). The grid is periodic (bc='periodic', spacing \(h = L / N\)) or has zero Dirichlet values (bc='dirichlet-zero': \(N\) interior points of a vertex-centered grid, \(h = L / (N + 1)\)). Both are the grids, and \(A_h\) the matrix, of pySDC’s finite differences (get_finite_difference_matrix() with order=2, stencil_type='center' for \(\Delta_h\) and order=1, stencil_type='upwind' for positive velocities). Without a velocity it is pure diffusion, \(A_h = \nu \Delta_h\). GeometricMultigrid takes and returns plain arrays and does not depend on the rest of pySDC; GenericNDimFinDiff uses it for solver_type='MG'.

The method. V(2,2)-cycles with weighted Jacobi smoothing (\(\omega = 0.8\), with the diagonal of the whole operator), full-weighting restriction, linear interpolation, the same stencil on every grid, and an exact solve with a dense inverse on the coarsest grid, which has at most coarsest points (default COARSEST, 1000). A periodic grid coarsens from \(N\) to \(N / 2\) points per direction, a Dirichlet grid from \(N\) to \((N - 1) / 2\) interior points, with zero boundary values in the transfers. The exact coarse solve is needed: the smooth modes of \(I - s \Delta_h\) are damped only by the identity part, which Jacobi does not do. A solve starts from zero and stops when the 2-norm of the residual is below rtol times that of b, or when a V-cycle no longer halves it (stall), which is where the floating-point format of b ends (about \(\kappa u\), with \(\kappa\) the condition number and \(u\) the unit roundoff), or after maxiter cycles. A cycle that does not reduce the residual at all is discarded, so that a format too coarse for the system returns its best iterate, zero in the worst case, rather than one that is worse. Both rules judge a cycle against the one before from the second cycle on: the first cycle is kept unless it overflows, and a solve that ends worse than zero returns zero.

Advection. Point Jacobi smooths reliably while diffusion dominates on every grid, and the grid Peclet number \(|c_a| H / \nu\) is largest on the coarsest grid actually used (spacing \(H\), set by coarsest), which is what bounds it; at coarsest=15, a 1D grid has \(H = 1/16\) whatever \(N\). Measured with random right-hand sides in 1D to 3D, periodic and Dirichlet, with stiffness \(s \nu h^{-2}\) up to \(10^6\), every solve reaches rtol while that Peclet number is at most about 1 to 2. Beyond, a V-cycle reduces the residual by only 0.5 to 0.85 in 2D and 3D (the coarse grids, upwinded on their own spacing, approximate the smooth components along the flow badly), the stall rule takes that for the end of the format, and the solve stops after a few cycles with a residual of \(10^{-6}\) to \(10^{-2}\).

Raising stall (to 0.8 or 0.9) lets such slowly contracting solves go on to rtol (in 35 V-cycles at a coarsest-grid Peclet number of 16 in 2D, at the price of about one more cycle at the end of a low format), and is needed near the limit. Every solve leaves the relative residual of what it returns in relative_residual: check it with advection.

The first V-cycle is judged by the second, which matters for advection: with a smooth right-hand side and a stiff system (\(s \nu h^{-2} \gtrsim 10^4\)), the first cycle from zero leaves its error in the outflow boundary layer, where the residual is large, and reduces the 2-norm of the residual by only 0.5 to 0.9 or increases it (up to four times measured), even at coarsest-grid Peclet numbers far below 1 (0.03 at \(N = 1023\) and \(H = 1/512\)), in 1D as in 2D. The cycles after it contract by 0.15 to 0.7, and the solve converges as usual.

Formats. A solve computes in the floating-point type of its right-hand side: float64 and float32 arrays are solved in their own arithmetic, and float16 is a storage format, as on GPUs: every array is stored in half precision, every operation computes in single precision. The result has the type of the right-hand side.

Speed. On a GPU, periodic 3D grids run on fused CUDA kernels: one pass over the arrays for the residual, the Jacobi step, the restriction and the interpolation each, with the grid size compiled in. With fma=False (default), the stencil kernels compute bit for bit what the array operations compute, which is what the tests check; fma=True lets the compiler contract multiplications and additions, which is faster where the arithmetic and not the memory limits the kernels (fp64 on GPUs with few fp64 units). Measured at \(640^3\) with V(2,2)-cycles, one Jacobi step moves data at about 3 TB/s on an H100 in fp64. The fused kernels are for periodic pure diffusion; 1D and 2D grids, Dirichlet grids, advection, and every grid on a CPU use array operations.

class GeometricMultigrid(N, ndim=3, L=1.0, xp=<module 'numpy' from '/home/runner/micromamba/envs/pySDC/lib/python3.14/site-packages/numpy/__init__.py'>, fma=False, bc='periodic', nu=1.0, velocity=None, stall=0.5, coarsest=1000)[source]#

Bases: object

Geometric multigrid for \((I - s A_h)\, x = b\) with \(A_h = \nu \Delta_h - c \cdot \nabla_h\) on a grid of \(N^d\) points with side length \(L\), periodic or with zero Dirichlet values: \(\Delta_h\) is the second-order Laplacian and \(\nabla_h\) the first-order upwind gradient. See pySDC.helpers.multigrid for the method, the formats and the speed.

Parameters:
  • N (int) – Points per direction. Periodic: \(N = m 2^k\) with \(m^d\) at most coarsest; zero Dirichlet: the interior points, \(N = 2^k - 1\) (or \(m 2^k - 1\) with \((m - 1)^d\) at most coarsest).

  • ndim (int) – Dimension: 1, 2 or 3.

  • L (float) – Side length of the domain.

  • xp (module) – numpy or cupy: where the arrays live.

  • fma (bool) – On a GPU, let the compiler contract multiplications and additions into fused multiply-adds: faster where arithmetic limits the kernels, but no longer bit for bit what the array operations compute.

  • bc (str) – 'periodic' (grid spacing \(h = L / N\)) or 'dirichlet-zero': \(N\) interior points of a vertex-centered grid with \(h = L / (N + 1)\) and zero values on the boundary.

  • nu (float) – Diffusion coefficient \(\nu\), positive.

  • velocity (sequence of float or None) – Constant velocity \(c\), one entry per dimension; None or zeros give pure diffusion. Each component is upwinded on the side it comes from.

  • coarsest (int) – The largest number of points the coarsest grid may have, which is solved exactly with a dense inverse: the grid is halved until it has at most this many. Default COARSEST (1000); smaller values give more levels, and a coarsest grid with a larger spacing, which is what bounds the Peclet number (see pySDC.helpers.multigrid).

  • stall (float) – The stall rule: a V-cycle that reduces the residual by a factor larger than this ends the solve, taken for the accuracy of the format. Raise it (to 0.9, say) where V-cycles contract slowly, as on advection-dominated coarse grids, so that they go on to rtol; the price is more cycles spent at the accuracy of a low format (fp16, fp32) before the solve notices it.

Variables:

relative_residual (float) – The 2-norm of the residual of the iterate the last solve() returned, relative to that of b.

Examples

>>> import numpy as np
>>> mg = GeometricMultigrid(64, ndim=2)
>>> b = np.random.default_rng(0).standard_normal((64, 64))
>>> x, cycles = mg.solve(b, s=1e-2, rtol=1e-10, maxiter=50)
>>> bool(np.linalg.norm(b - (x - mg.apply(x, 1e-2))) < 1e-10 * np.linalg.norm(b))
True
>>> mg = GeometricMultigrid(63, ndim=2, bc='dirichlet-zero', nu=0.1, velocity=(1.0, -0.5))
>>> b = np.random.default_rng(0).standard_normal((63, 63))
>>> x, cycles = mg.solve(b, s=1e-1, rtol=1e-10, maxiter=50)
>>> bool(np.linalg.norm(b - (x - mg.apply(x, 1e-1))) < 1e-10 * np.linalg.norm(b))
True
apply(x, scale=1.0, out=None)[source]#

\(\text{scale}\cdot A_h x\) on the finest grid, the operator the solve inverts, in the type of x.

laplacian(x, scale=1.0, out=None)[source]#

\(\text{scale}\cdot\Delta_h x\) on the finest grid, without \(\nu\) and the advection, in the type of x, into out if given; on a GPU on periodic 3D grids by the fused kernel.

solve(b, s, rtol, maxiter)[source]#

Solve \((I - s A_h)\, x = b\) from a zero guess, in the format of b.

Stops when the 2-norm of the residual is below rtol times that of b, when a V-cycle from the second on reduces it by less than stall (the accuracy of the format), or after maxiter V-cycles; a cycle from the second on that does not reduce it at all is discarded, and a solve that ends worse than zero returns zero. A solve that stops on the stall rule may not have reached rtol: where V-cycles contract slowly, as beyond the Peclet limit (see pySDC.helpers.multigrid), the stall rule mistakes that for the end of the format. The relative residual of the returned iterate is in relative_residual after every solve.

Parameters:
  • b (array) – Right-hand side, of shape (N,) * ndim and type float64, float32 or float16.

  • s (float) – Factor of the operator, positive.

  • rtol (float) – Relative tolerance for the residual.

  • maxiter (int) – Largest number of V-cycles.

Returns:

  • x (array) – The solution, of the shape and type of b.

  • cycles (int) – The V-cycles it took.

compute_type(dtype)[source]#

The type a format computes in: its own, but float32 for float16, which is a storage format here.