Space-time waveform relaxation multigrid for Navier-Stokes

This paper presents a scalable monolithic Newton-Krylov-multigrid solver that extends efficient spatial multigrid methods to a space-time waveform relaxation framework for the all-at-once solution of discretized Navier-Stokes equations.

The Gist

Imagine you are trying to predict the weather for an entire year, hour by hour, for every single square inch of a city. This is essentially what scientists do when they simulate fluid flow (like wind or water) using computers. They break the world into a 3D grid and try to calculate how the fluid moves at every point in space and time.

The problem is that this creates a massive amount of data. If you try to solve this step-by-step (like reading a book one page at a time), you hit a wall. Even with super-fast computers, the time it takes to finish the calculation stops getting faster because the computers are spending more time talking to each other than actually doing math.

This paper introduces a new way to solve these problems, called Space-Time Waveform Relaxation Multigrid. Here is how it works, explained with everyday analogies:

1. The Old Way: The "Assembly Line"

Traditionally, solving fluid problems is like a factory assembly line.

• Step 1: Calculate the fluid's position at 1:00 PM.
• Step 2: Pass that result to the next worker to calculate 1:01 PM.
• Step 3: Pass it on to 1:02 PM, and so on.

The problem is that the workers (computer cores) have to wait for the previous worker to finish before they can start. If you have 1,000 workers, they can't all work at once because the line is too sequential. You hit a "traffic jam" where adding more workers doesn't make the job finish faster.

2. The New Idea: The "Group Study Session"

The authors propose a different approach: Space-Time Multigrid. Instead of a line, imagine a group study session where everyone looks at the entire year of data at once.

• The "All-at-Once" View: Instead of solving 1:00 PM, then 1:01 PM, the computer tries to solve the whole year simultaneously. It treats time as just another dimension, like width or height.
• The "Waveform" (The Song Analogy): Imagine trying to tune a choir. If you ask everyone to sing perfectly at once, it's chaotic. Instead, you ask everyone to sing their part, listen to the group, and then adjust their pitch. You do this over and over.
  • In this paper, the "song" is the fluid's movement over time. The computer guesses the whole year's movement, listens to the "errors" (where the physics doesn't make sense), and adjusts the whole timeline at once. This is called Waveform Relaxation.

3. The "Multigrid" Trick: The "Zoom-Out" Strategy

Even with the "Group Study" approach, the math is still incredibly hard. This is where Multigrid comes in.

Imagine you are trying to find a specific house in a giant, messy city.

• The Hard Way: You walk down every single street, checking every door. (This is what standard computers do).
• The Multigrid Way:
  1. Zoom Out: First, you look at a map of the whole country. You quickly realize the house is in the "North" region.
  2. Zoom In a Little: You look at a map of the state. "Okay, it's in the North-East."
  3. Zoom In More: You look at the city map. "It's in the downtown district."
  4. Final Detail: Now you only need to check the specific streets in that district.

The paper's algorithm does this mathematically. It solves the problem on a "coarse" grid (low detail) to get the big picture, then uses that to fix the "fine" grid (high detail). This makes the "Group Study" session converge (find the answer) much faster.

4. Why This Matters (The "Super-Parallel" Potential)

The authors haven't fully built the "parallel-in-time" version yet (due to software limits), but they built a performance model (a prediction) to show what it could do.

• Current Reality: On today's computers, their new method is actually a bit slower than the old "Assembly Line" method because it does extra work to look at everything at once.
• The Future Potential: The model predicts that if we had a supercomputer with thousands of cores (like a massive cluster), this new method would be a game-changer.
  • Analogy: The old method is like having 100 people read a book one page at a time. The new method is like having 100 people read the whole book at the same time, discussing the plot together.
  • If you have enough people (cores), the "Group Study" method finishes the job 12 to 40 times faster than the assembly line.

Summary

• The Problem: Simulating fluids is too slow because computers get stuck waiting for previous steps to finish.
• The Solution: A new algorithm that treats time and space as one big puzzle, solving the whole timeline at once using a "zoom-out" strategy (Multigrid) and iterative adjustments (Waveform Relaxation).
• The Result: It works well now for smaller problems, but its true power lies in the future. When we have massive supercomputers, this method could allow us to simulate complex weather or ocean currents in a fraction of the time it currently takes.

The authors are essentially saying: "We've built a prototype for a car that drives on a new type of road. Right now, the road is bumpy, but once we pave it, this car will be the fastest way to travel across the universe."

Technical Summary

Here is a detailed technical summary of the paper "Space-Time Waveform Relaxation Multigrid for Navier-Stokes" by James Jackaman and Scott MacLachlan.

1. Problem Statement

The paper addresses the computational challenges associated with solving time-dependent incompressible fluid flow problems (Navier-Stokes equations) using space-time finite-element discretizations.

• Context: While high-fidelity simulations are standard, solving the resulting large-scale linear and nonlinear systems efficiently remains difficult. Traditional "timestepping" approaches (solving sequentially in time) face a "strong scaling" limit on modern many-core High-Performance Computing (HPC) systems. Once spatial parallelism saturates (typically around $O(10,000)$ degrees of freedom per processor), adding more cores yields no speedup due to communication overhead.
• Goal: To develop a monolithic "all-at-once" solver that treats space and time simultaneously. This approach aims to unlock time-parallelism, allowing the problem to be solved concurrently across the entire time domain to overcome spatial scaling limits.
• Specific Challenge: Extending efficient spatial multigrid relaxation methods to Waveform Relaxation Multigrid (WRMG) for the nonlinear Navier-Stokes equations, which are more complex than the scalar parabolic problems (like the heat equation) typically studied in this domain.

2. Methodology

The authors propose a Newton-Krylov-multigrid framework where the linear systems arising from Newton's method are solved using a Waveform Relaxation Multigrid (WRMG) preconditioner.

A. Discretization

• Space-Time Formulation: The authors utilize a tensor-product structure separating spatial and temporal domains.
  • Spatial: Continuous Lagrange finite elements (Taylor-Hood elements: $P_{k+1}$ for velocity, $P_k$ for pressure).
  • Temporal: Discontinuous Galerkin (DG) methods with upwinding. This allows for high-order accuracy and flexibility in time-step adaptation.
• Monolithic Approach: The discretization results in a single large system of equations spanning all space and time steps, rather than a sequence of smaller systems.

B. The Solver Algorithm

The core of the method is a Multigrid V-cycle used as a preconditioner for FGMRES (Flexible Generalized Minimal Residual method) within a Newton-Krylov loop.

1. Relaxation (Smoothing):
   • Instead of point-wise relaxation, the method uses patch-based relaxation.
   • Heat Equation: Uses Vertex-Star patches (coupling all DoFs in a spatial patch across the entire time horizon).
   • Navier-Stokes: Uses a Vanka+Star relaxation strategy. This couples velocity and pressure degrees of freedom within a spatial patch and extends this coupling across all time steps in the waveform relaxation framework.
   • Acceleration: Relaxation sweeps are accelerated using Chebyshev polynomials, with eigenvalue estimates derived from a few GMRES steps.
2. Grid Transfer:
   • Standard geometric multigrid operators are used. The restriction and interpolation operators are tensor products of the identity in time and standard finite-element operators in space ($P = I \otimes P_h$).
3. Parallel Performance Model:
   • Since a full parallel-in-time implementation was not available during the study, the authors developed a theoretical performance model.
   • The model accounts for:
     • Computation: Costs of assembling interpolation operators and solving patch systems (which have a block lower-bidiagonal structure in time).
     • Communication: Latency ($\alpha$) and bandwidth ($\beta$) costs, including halo exchanges and the specific costs of Cyclic Reduction (used to solve the block-tridiagonal systems arising in waveform relaxation).

3. Key Contributions

1. Extension to Navier-Stokes: The paper successfully extends efficient spatial multigrid relaxation schemes (previously applied to Poisson and steady Navier-Stokes) to space-time waveform relaxation for unsteady, incompressible Navier-Stokes equations.
2. High-Order Discretization: The method supports high-order polynomial discretizations (up to 3rd order in time and space) and demonstrates that the relaxation schemes remain robust regardless of polynomial order.
3. Monolithic Newton-Krylov Framework: The authors demonstrate a robust coupling of Newton's method with Krylov solvers preconditioned by WRMG, handling the nonlinearity of the Navier-Stokes equations effectively.
4. Performance Modeling: A detailed cost model is developed to predict the scalability of the WRMG solver. It quantifies the trade-offs between spatial and temporal parallelism, showing that significant speedups are possible when the number of temporal cores is optimized relative to spatial cores.

4. Numerical Results

The authors tested the solver on two benchmark problems: the Chorin test problem (manufactured solution) and the Lid-driven cavity (complex dynamics).

• Heat Equation (Validation):
  • The WRMG solver showed sub-linear scaling with respect to the number of nonzeros, outperforming direct LU factorization significantly for higher-order discretizations.
  • While classical timestepping was faster in serial (due to lower memory overhead and no time-parallel overhead), WRMG demonstrated superior algorithmic scaling for large systems.
• Navier-Stokes (Chorin & Lid-Driven Cavity):
  • Convergence: The solver required a stable number of Newton iterations (typically 4) and FGMRES iterations.
  • Comparison with Timestepping: In the current serial-in-time implementation, the monolithic WRMG solver was slower (5–20x) than the timestepping approach. This is attributed to the "extra" work required to solve the full space-time system at once and the lack of temporal parallelism in the current code.
  • Memory: The monolithic approach has a higher memory footprint, limiting the maximum problem size solvable on the test hardware compared to timestepping.
• Parallel Performance Model Predictions:
  • The theoretical model predicts that with sufficient parallel resources (specifically, a "two-level" parallelism strategy using cyclic reduction for time), the WRMG solver can achieve speedups of 12x to 40x over timestepping.
  • The model highlights that time-parallelism becomes beneficial only when spatial parallelism saturates (i.e., when the problem is large enough that adding more spatial cores yields diminishing returns).

5. Significance and Future Work

• Significance: This work provides a proof-of-concept that waveform relaxation multigrid is a viable and robust strategy for solving complex, nonlinear, time-dependent PDEs like the Navier-Stokes equations. It bridges the gap between efficient spatial solvers and the need for time-parallel algorithms in the era of exascale computing.
• Limitations: The current implementation is serial-in-time. The full potential of the method relies on implementing cyclic reduction or similar algorithms to parallelize the solution of the space-time patch systems.
• Future Directions:
  • Implementing a true parallel-in-time version of the solver.
  • Extending the method to 3D flows (currently limited by memory).
  • Exploring local-in-space and local-in-time adaptivity, which is naturally supported by monolithic space-time discretizations but difficult with standard timestepping.

In conclusion, the paper establishes that while the monolithic space-time approach currently incurs overhead compared to sequential timestepping, it offers a scalable pathway for future HPC systems where time-parallelism is necessary to solve large-scale fluid dynamics problems efficiently.