Scalable augmented Lagrangian preconditioners for fictitious domain problems

This paper proposes and analyzes two scalable augmented Lagrangian preconditioners for solving block-structured linear systems arising from fictitious domain discretizations of Poisson and Stokes problems, demonstrating their robustness and effectiveness through spectral analysis and extensive numerical tests in two and three dimensions.

The Gist

Here is an explanation of the paper, translated from complex mathematical jargon into a story about building bridges, managing traffic, and solving puzzles.

The Big Picture: The "Ghost Island" Problem

Imagine you are an engineer trying to simulate how water flows around a rock in a river, or how heat spreads through a complex machine part.

In the old days, to do this, you had to draw a perfect map (a mesh) that hugged the shape of the rock exactly. If the rock moved, or if the shape was weird, you had to redraw the entire map. This is like trying to fit a custom-made jigsaw puzzle piece into a box; if the piece moves, the whole puzzle breaks.

The Fictitious Domain Method is a clever shortcut. Instead of redrawing the map, you just put the rock inside a simple, square box (the "background domain"). The rock is now a "ghost island" floating inside the box. You don't change the grid of the box; you just tell the water, "Hey, you can't go inside the rock."

The Catch:
To enforce this rule, mathematicians use something called Lagrange Multipliers. Think of these as invisible "traffic cops" standing on the edge of the ghost island. They stop the water from crossing the line.

When you turn this into a computer problem, you get a giant system of equations. It's like a massive spreadsheet where every cell depends on every other cell. Solving this spreadsheet is incredibly slow and memory-hungry, especially if the rock is huge or the water is moving fast. The computer gets stuck in an endless loop trying to find the answer.

The Solution: The "Augmented Lagrangian" Preconditioner

This paper introduces a new way to speed up the computer so it can solve these "ghost island" problems quickly, even in 3D. They call it an Augmented Lagrangian Preconditioner.

Here is how it works, using an analogy:

1. The Problem: A Bumpy Road

Imagine you are driving a car (the computer solver) trying to get to a destination (the solution). The road is full of potholes and sharp turns (mathematical "ill-conditioning"). The car keeps stalling or taking forever to get there.

2. The Old Way: Guessing the Map

Previous methods tried to fix the road by building a perfect, detailed map of every single pothole (approximating the "Schur complement"). But in the "ghost island" method, the road is made of two different materials that don't match up perfectly. Building a perfect map of this mismatch is incredibly hard and expensive.

3. The New Way: The "Augmented" Detour

The authors propose a different strategy. Instead of trying to map every pothole perfectly, they add a detour to the road.

• The Augmentation: They add a "toll booth" (a mathematical term) to the road. This toll booth forces the car to pay a small fee to take a shortcut.
• The Magic: By paying this fee (mathematically, adding a specific term to the equations), the road becomes much smoother. The potholes disappear, and the car can drive straight to the destination.
• The Preconditioner: This "toll booth system" is the Preconditioner. It doesn't solve the problem for you; it just reshapes the road so the solver can run at top speed.

Why is this paper special?

1. It handles the "Mismatch" without crying.
Usually, when you have two different grids (the box and the rock) that don't line up, the math gets messy. The authors found a way to use a "mass matrix" (a simple count of how much space the rock takes up) to smooth out the road. They proved mathematically that this trick works no matter how small the grid gets.

2. It works for both simple and complex problems.
They tested this on two scenarios:

• The Poisson Problem: Like heat spreading through a metal plate with a hole in it. (Simple, 2 variables).
• The Stokes Problem: Like water flowing around a submarine. This is harder because you have to track both the speed of the water and its pressure. (Complex, 3 variables).
  Their "toll booth" trick worked for both.

3. It's built for the real world (3D and Big Data).
Many math papers only work on small, 2D examples on a laptop. This team built a version that runs on supercomputers with thousands of processors. They tested it with up to 56 million variables (imagine a 3D grid with 56 million tiny cubes).

• The Result: The computer didn't crash. It solved the problem in a reasonable amount of time, and the time didn't explode as the problem got bigger.

The Takeaway

Think of this paper as inventing a universal traffic management system for "ghost islands."

Before, if you wanted to simulate a moving object in a fluid, you had to spend hours just setting up the road map, and the drive was slow and bumpy.
Now, thanks to this "Augmented Lagrangian" trick, you can drop the object into the box, flip a switch, and the computer zooms through the solution, regardless of how complex the shape is or how fine the details are.

In short: They found a way to make the computer ignore the messy details of the mismatched grids and focus only on the smooth path to the answer. This makes simulating complex real-world physics (like blood flow in veins or air over a car) much faster and more reliable.

Technical Summary

Here is a detailed technical summary of the paper "Scalable augmented Lagrangian preconditioners for fictitious domain problems."

1. Problem Statement

The paper addresses the computational challenges associated with solving large-scale linear systems arising from the Fictitious Domain (FD) method using Lagrange multipliers. This method is used to solve partial differential equations (PDEs) on complex, time-dependent, or moving domains by embedding them into a simpler background domain (e.g., a box).

• Mathematical Structure: The finite element discretization of these problems results in saddle-point linear systems with specific block structures:
  • Poisson Problem: A $2 \times 2$block system involving the stiffness matrix ($A$) and a coupling matrix ($C$) between the background and the immersed boundary.
  • Stokes Problem: A $3 \times 3$block system (double saddle point) involving velocity ($A$), pressure ($B$), and the Lagrange multiplier coupling ($C$).
• Key Challenge:
  • Non-Matching Meshes: The background mesh and the immersed boundary mesh are independent and do not align. This makes the coupling matrix $C$ dense and defined on arbitrary overlapping grids.
  • Schur Complement Difficulty: Standard preconditioning strategies for saddle-point problems rely on approximating the Schur complement $S = CA^{-1}C^T$. In FD methods, $S$ is dense and difficult to approximate efficiently because $C$ does not correspond to integrals on a single mesh.
  • Scalability: Direct solvers do not scale well with problem size (especially in 3D), and iterative solvers suffer from poor convergence as the mesh is refined due to ill-conditioning.

2. Methodology

The authors propose Augmented Lagrangian (AL)-based preconditioners to overcome the difficulty of approximating the dense Schur complement.

A. Augmented Lagrangian Formulation

Instead of solving the original system directly, the authors reformulate the problem by adding a stabilization term to the $(1,1)$-block.

• Poisson Case: The system is augmented with a term $\gamma C^T W^{-1} C$, where $W$ is a mass matrix on the immersed boundary.
• Stokes Case: The system is augmented twice: once for the velocity-pressure coupling ($\gamma B^T Q^{-1} B$) and once for the velocity-multiplier coupling ($\delta C^T W^{-1} C$).

B. Preconditioner Design

The proposed preconditioner is a block triangular matrix (for the Stokes case):
$$P_{\gamma\delta} = \begin{bmatrix} A_{\gamma\delta} & B^T & C^T \\ 0 & -\frac{1}{\gamma}Q & 0 \\ 0 & 0 & -\frac{1}{\delta}W \end{bmatrix}$$

• Key Innovation: The choice of the matrices $Q$ and $W$.
  • $Q$ is chosen as the pressure mass matrix ($M_p$).
  • $W$ is chosen as the square of the immersed boundary mass matrix ($M_\lambda^2$).
• Why $W = M_\lambda^2$? Theoretical analysis shows that this specific choice ensures the eigenvalues of the preconditioned system remain bounded away from zero uniformly with respect to the mesh size ($h$), even when the meshes are non-matching.
• Inexact Solves: Since inverting the augmented block $A_{\gamma\delta}$ exactly is expensive, the authors use Flexible GMRES (FGMRES). The $(1,1)$-block is solved approximately using a Conjugate Gradient (CG) solver preconditioned by a single V-cycle of Algebraic Multigrid (AMG) with a loose tolerance. The mass matrices $Q$ and $W$ are either inverted exactly (for smaller 2D problems) or approximated by their diagonal entries (for large 3D problems).

C. Spectral Analysis

The paper provides a rigorous spectral analysis for both exact and inexact versions of the preconditioner:

• Eigenvalue Bounds: They prove that the non-zero eigenvalues of the preconditioned matrix are real, positive, and lie in the interval $[\min(\eta, \epsilon, \theta), 1]$.
• Mesh Independence: Crucially, they demonstrate that the lower bound ($\min(\eta, \epsilon, \theta)$) is bounded away from zero by a constant independent of the mesh sizes $h_\Omega$ and $h_\Gamma$. This guarantees that the number of iterations does not increase as the mesh is refined.
• Inexact Variant: The analysis extends to the case where the sub-blocks are solved inexactly, showing that the eigenvalues remain clustered provided the inner solvers have sufficient accuracy.

3. Key Contributions

1. Novel Preconditioner for FD Methods: Introduction of an AL-based preconditioner specifically tailored for fictitious domain problems with non-matching meshes, eliminating the need to approximate the dense Schur complement $CA^{-1}C^T$.
2. Theoretical Proof of Robustness: A rigorous proof that the proposed preconditioner yields a mesh-independent convergence rate for both Poisson and Stokes problems, even with non-matching grids.
3. Extension to Stokes Problems: Generalization of the AL approach to the double saddle-point structure of the Stokes equations, including a combined inf-sup condition analysis.
4. Scalable Implementation: A distributed-memory implementation using the deal.II finite element library and Trilinos/PETSc linear algebra backends, validated on high-performance computing (HPC) systems.

4. Results

The authors validated their approach through extensive numerical experiments in 2D and 3D.

• Poisson Problem:
  • Compared against BFBt and Rational preconditioners.
  • Result: The AL preconditioner required significantly fewer outer iterations (e.g., ~15-20 iterations) compared to BFBt (which grew with mesh size) and Rational methods. The iteration count remained constant as the degrees of freedom (DoF) increased from thousands to millions.
• Stokes Problem (2D & 3D):
  • Tested on circular, flower-shaped, and toroidal interfaces.
  • Result: The solver achieved robust convergence with outer iteration counts independent of mesh refinement (e.g., 8–16 iterations for 2D, 8–14 for 3D).
  • Inexact Solvers: Using diagonal approximations for mass matrices and AMG for the augmented block did not degrade performance significantly.
  • 3D Scalability: The method successfully solved problems with up to 56 million unknowns on the Galileo100 supercomputer. Strong scaling tests showed good efficiency up to 512 MPI ranks.
• Computational Cost: The AL approach was consistently faster than competing methods, particularly in 3D, due to the avoidance of dense matrix operations and the efficiency of the AMG preconditioner.

5. Significance

This work provides a robust, scalable, and mesh-independent solution strategy for one of the most computationally demanding aspects of fictitious domain methods: the solution of the resulting linear systems.

• Practical Impact: By avoiding the need for complex Schur complement approximations and utilizing standard mass matrices, the method is easier to implement and highly efficient for moving boundary problems (e.g., fluid-structure interaction).
• Theoretical Impact: It bridges the gap between the theoretical requirements of inf-sup stability and practical preconditioning strategies for non-matching meshes, proving that spectral equivalence can be maintained without explicit mesh alignment.
• Future Directions: The authors note that this framework can be extended to more complex elliptic interface problems and that developing specialized multigrid schemes for the augmented block is a promising area for future research.

In summary, the paper establishes that Augmented Lagrangian preconditioning with specific mass-matrix choices is the superior strategy for solving large-scale fictitious domain problems, offering both theoretical guarantees of mesh independence and practical scalability on modern supercomputers.