🔢 mathematics

CoarseSolvers for Exascale Solution of Poisson Problems

This paper introduces a novel two-level Schwarz method featuring a structured, non-nested global coarse space as a communication-free alternative to Algebraic Multigrid for solving pressure Poisson equations in incompressible Navier-Stokes simulations, demonstrating superior scalability on exascale supercomputers compared to the state-of-the-art BoomerAMG solver.

Original authors: Thilina Ratnayaka, Paul Fischer, Luke Olson

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Thilina Ratnayaka, Paul Fischer, Luke Olson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, complex puzzle representing the flow of water or air around an object (like an airplane or a bed of pebbles). To do this on a supercomputer, scientists break the puzzle into millions of tiny pieces (called "elements").

The paper describes a new, faster way to solve the hardest part of this puzzle: the "coarse" level. Here is how the authors explain their method using simple analogies.

The Problem: The "All-to-All" Traffic Jam

When scientists solve these fluid flow problems, they use a technique called $p$ -multigrid. Think of this as solving the puzzle in layers:

The Fine Layer: You look at the tiny details (millions of pieces). This is easy to solve locally because each piece only talks to its immediate neighbors.
The Coarse Layer: As you zoom out, the pieces get bigger and fewer. However, at the very bottom level (the "coarsest" level), the problem changes. The pieces stop being local; they become globally connected.

The authors compare this to a global phone call. In the fine layers, you only talk to your neighbors. But in the coarse layer, every single computer in the supercomputer cluster needs to talk to every other computer simultaneously to get the answer. This creates a massive "traffic jam" (communication overhead) that slows everything down, especially when you have thousands of computers working together.

The Old Solution: The "Boomerang" Solver

The standard way to fix this traffic jam was to use a method called AMG (Algebraic Multigrid).

The Analogy: Imagine trying to organize a massive group of people by having them pass a message up and down a chain of command, level by level.
The Issue: On modern supercomputers (specifically those with thousands of GPUs), this "chain of command" takes too many steps. The time spent passing messages back and forth (communication) becomes the bottleneck, slowing down the entire simulation.

The New Solution: A "Two-Level" Shortcut

The authors propose a new method called a Two-Level Schwarz Method with a Non-Nested Coarse Space. Here is how it works, broken down into simple steps:

1. The Local "Team Huddles" (The Overlapping Subdomains)

Instead of one giant global conversation, the new method breaks the problem into smaller, overlapping groups.

The Analogy: Imagine a stadium full of people. Instead of everyone shouting to everyone else, the crowd is divided into small, overlapping circles. Inside each circle, people can talk freely and solve their local part of the puzzle without bothering anyone outside their circle.
Why it helps: This part is very fast because it only requires talking to immediate neighbors.

2. The "Magic Map" (The Novel Coarse Space)

This is the paper's biggest innovation. Usually, to connect these local groups, you need a complex, messy map that fits the exact shape of the puzzle.

The Innovation: The authors created a simple, structured "grid of boxes" that covers the entire area, regardless of the puzzle's complex shape.
The Analogy: Imagine the puzzle is a weirdly shaped island. Instead of drawing a complex map of the island's coastline, you just lay a simple, perfect grid of square tiles over the whole ocean. You only care about the tiles that touch the island.
The Benefit: Because this "grid of boxes" is perfectly structured and simple, the computers can translate information between the local groups and the global grid without any talking (communication) at all. It's like a pre-printed map where everyone knows exactly where to look.

3. The "Global Fix"

Once the local groups solve their parts and the "Magic Map" provides a quick global correction, the problem is solved.

The Result: The new method avoids the massive "traffic jam" of the old method. It trades a slightly more complex calculation for a massive reduction in waiting time for messages.

What the Experiments Showed

The team tested this on two of the world's fastest supercomputers (Summit and Frontier) using complex simulations like water flowing through a T-junction or around thousands of pebbles.

The Trade-off: The new method sometimes required a few more "rounds" of calculation (iterations) to get the perfect answer compared to the old method.
The Win: However, because each "round" was so much faster (due to less waiting for messages), the total time to solve the problem was shorter, especially when using a huge number of computers.
The Verdict: On smaller setups, the old method was fine. But on the massive "Exascale" systems (thousands of GPUs), the new method was significantly faster, cutting the time spent on the "coarse" problem by a factor of 2 to 3.

Summary

The paper presents a new way to solve massive fluid dynamics puzzles on supercomputers. Instead of using a complex, message-heavy method (AMG) that gets stuck in traffic, they use a local teamwork approach combined with a simple, rigid grid that allows computers to coordinate instantly without talking. This makes the simulation run much faster on the world's most powerful machines.

Technical Summary: Coarse Solvers for Exascale Solution of Poisson Problems

Problem Statement
The paper addresses the scalability bottleneck encountered when solving the pressure Poisson equation arising from incompressible Navier-Stokes simulations using high-order Spectral Element Methods (SEM) or Finite Element Methods (FEM) on exascale architectures. While $p$ -multigrid ( $p$ MG) preconditioners effectively reduce the problem size through local tensor-product operations, the final coarse grid level ( $N=1$ ) presents a significant challenge. At this level, the system matrix becomes dense, and the solution requires all-to-all communication, which scales poorly with the number of processes ( $P$ ). On current and future exascale platforms (e.g., Summit, Frontier), this coarse grid solve can dominate the time-to-solution, accounting for up to 45% of the simulation time in large-scale cases. The existing state-of-the-art solution, Algebraic Multigrid (AMG), incurs high communication costs due to its multi-level structure, particularly as $P$ increases.

Methodology
The authors propose a two-level additive Schwarz method (ASM) as a low-communication alternative to AMG for the coarse grid solve. The method consists of two components:

Local Subdomain Solves: The domain is partitioned into overlapping subdomains. Local problems are solved exactly (using Cholesky factorization) on each process. These operations are highly localized and communication-free, making them well-suited for GPU acceleration.
Global Coarse Correction: A novel, structured, and nonnested coarse space is introduced to handle the long-wavelength error components. Unlike traditional nested multigrid approaches, this coarse space is constructed using piecewise linear interpolants over a simple rectangular box mesh that spans the computational domain.
- Nonnested Coarse Space: The coarse basis functions are defined on a regular grid of boxes, independent of the underlying unstructured finite element mesh topology. This allows for communication-free interpolation between the original $p$ MG coarse space and the reduced global coarse problem.
- Reduced System: The global coarse problem is formulated as a reduced system $A_r u_r = b_r$ , where $A_r = J^T A J$ . Here, $J$ is an interpolation matrix mapping the reduced coarse basis to the fine nodal points. The size of this reduced system is $O(P)$ , typically containing only a few degrees of freedom per process (e.g., 4–10).
- Solver: The reduced system is solved using a communication-minimal $XX^T$ factorization algorithm, which is efficient for small, dense systems arising from Poisson problems.

Key Contributions

Novel Nonnested Coarse Space: The primary contribution is the development of a structured, nonnested coarse space that enables communication-free interpolation. This eliminates the need for complex geometric mapping or topology preservation during the coarse-to-fine transfer, significantly simplifying the implementation on heterogeneous architectures.
Low-Communication Architecture: By decoupling the local solves (which are communication-free) from the global correction (which is solved on a drastically reduced system), the method minimizes the communication overhead that typically plagues coarse grid solves in strong-scaling regimes.
Integration with $p$ MG: The method is designed specifically as the last-level solver for $p$ -multigrid preconditioners in SEM/FEM codes (Nek5000 and NekRS), replacing the standard AMG coarse solver.

Results
The proposed method was evaluated using the Nek5000 (CPU-based) and NekRS (GPU-based) solvers on the Summit and Frontier supercomputers. Experiments involved four complex flow cases, including T-junctions and pebble bed reactors with up to 98 million elements and 51 billion degrees of freedom.

Iteration Counts: While the two-level Schwarz method sometimes resulted in slightly higher pressure iteration counts compared to a single AMG $V$ -cycle (particularly in smaller scale tests), the difference was marginal.
Time-to-Solution: The critical metric was the time per time step. The new method demonstrated superior performance at large process counts. For the largest test case (350K pebbles, $P=27,648$ ), the coarse grid solve time was approximately 2.7 times faster than the default AMG solver.
Strong Scaling: Strong scaling studies revealed that the two-level Schwarz method maintains better parallel efficiency than AMG as the number of processes increases. The crossover point where the Schwarz method becomes faster than AMG occurs at a local problem size ( $n/P$ ) of approximately $3.5 \times 10^6$ .
Complexity Analysis: Theoretical complexity estimates confirmed that the communication cost of the proposed method scales favorably compared to the multi-level communication requirements of AMG, which grows with the number of levels in the $V$ -cycle.

Significance and Claims
The paper claims that the proposed two-level Schwarz method with a nonnested coarse space is a viable and effective alternative to AMG for exascale Poisson problems. The significance lies in its ability to mitigate the communication bottleneck inherent in coarse grid solves on massively parallel systems. By leveraging a structured coarse space and a communication-minimal solver for the reduced system, the method achieves competitive or superior time-to-solution compared to state-of-the-art AMG solvers, particularly in the strong-scaling regime where process counts are high. The authors emphasize that while the method may require slightly more outer iterations in some cases, the reduction in coarse solve time is sufficient to yield overall performance gains, making it a critical component for scalable incompressible flow simulations on future exascale platforms.