🔢 mathematics

Two-Level Sketching Alternating Anderson acceleration for Complex Physics Applications

This paper presents a novel two-level sketching extension of the Alternating Anderson-Picard method, implemented in Julia, which combines physics-based projections with dynamic algebraic sketching to achieve up to 50% time-to-solution reductions in complex single- and multi-physics simulations without compromising convergence rates.

Original authors: Nicolás A. Barnafi, Massimiliano Lupo Pasini

Published 2026-05-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nicolás A. Barnafi, Massimiliano Lupo Pasini

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, incredibly complex puzzle. In the world of physics simulations (like predicting how blood flows through a heart or how air moves over a wing), this "puzzle" is a set of equations that describe the laws of nature. To solve it, computers use a step-by-step guessing game called a fixed-point iteration.

Think of the computer as a hiker trying to find the bottom of a foggy valley.

The Guess: The hiker takes a step.
The Check: They look around to see if they are closer to the bottom.
The Correction: If they are off course, they adjust their path and try again.

The paper introduces a new, smarter way to make these corrections. It's called Two-Level Sketching Alternating Anderson Acceleration. That's a mouthful, so let's break it down using a few analogies.

The Problem: The "Over-Engineered" Correction

Standard methods (called Anderson Acceleration) try to be incredibly precise. Every time the hiker makes a correction, the computer looks at every single step they've taken in the past, calculates the perfect new direction, and solves a giant math problem to do it.

The problem? This "perfect calculation" is slow. It's like asking a team of 100 mathematicians to solve a complex equation just to tell the hiker which way to turn. For huge simulations, this takes up so much time that the hiker moves very slowly, even if the path is correct.

The Solution: A Two-Step "Sketching" Strategy

The authors propose a method that speeds things up by being "good enough" rather than "perfect," but doing it in a very smart, structured way. They call this Sketching. Imagine instead of looking at the whole map, you just look at a quick sketch.

They use two levels of sketching:

Level 1: The "Physics Filter" (The Static Sketch)

This is the first filter. The authors realized that in many physics problems, not all parts of the puzzle are equally important for finding the solution.

The Analogy: Imagine you are trying to figure out why a car engine is making a noise. You have data on the wheels, the tires, the fuel, and the engine block.
The Trick: Sometimes, if you just focus on the engine block (the pressure in a fluid, for example), you can figure out the whole problem without needing to look at the wheels (the velocity) first.
What they do: They use "physics knowledge" to throw away the less important data before they start calculating. They only keep the "engine block" data. This shrinks the problem size immediately, saving memory and time.

Level 2: The "Adaptive Randomizer" (The Dynamic Sketch)

Even after throwing away the unimportant stuff, the remaining data might still be too big. This is where the second level comes in.

The Analogy: You still have a thick phone book of engine parts, but you only need to check a few pages to find the broken part.
The Trick: The computer uses a mathematical safety net (called backward stability analysis) to decide how many pages it can skip without getting lost.
The "Random" Part: Instead of reading every page, it randomly picks a few pages to check.
The Catch: If you pick pages randomly, you might have to walk all over the library (which is slow due to "cache misses"—a computer memory issue). So, the authors also figured out exactly how many pages you can pick randomly before it becomes slower than just reading the whole book. They found that for some tasks, picking just 10% of the data is fast enough, while for others, you can pick 80%.

The "Alternating" Dance

The method doesn't just use these shortcuts all the time. It dances between two modes:

The Quick Step: It takes a few simple, cheap guesses (like a quick glance at the map).
The Big Correction: Every few steps, it pauses to do a "sketched" correction using the two-level filter.

This "Alternating" approach means the computer spends most of its time moving quickly, only stopping to do the heavy math when it's absolutely necessary and when it can do it efficiently.

What Did They Find?

The authors tested this on four different "puzzles" (fluid flow, electrical signals in the heart, and other physics problems):

Speed: In the best cases (like fluid flow and heart simulations), they solved the problems 40% to 50% faster than the standard method.
Accuracy: They didn't lose accuracy. The hiker still found the bottom of the valley; they just got there faster.
Robustness: The method worked well even when the puzzles got huge (millions of variables).

The Bottom Line

This paper presents a new tool for scientists running complex simulations. It's like giving a hiker a pair of binoculars (to see the important parts) and a map with a "skip ahead" feature (to avoid checking every single step). By combining deep knowledge of physics with smart, randomized math shortcuts, they made the computer's "guessing game" much faster without making the answers less reliable.

The code they wrote is open-source, meaning other scientists can use this "binoculars and map" tool to speed up their own physics simulations.

Technical Summary: Two-Level Sketching Alternating Anderson Acceleration for Complex Physics Applications

Problem Statement
The Alternating Anderson-Picard (AAP) method is a robust technique for accelerating fixed-point iterations in single- and multi-physics simulations governed by discretized partial differential equations (PDEs). While AAP improves convergence rates and restores convergence for non-contractive operators, it requires solving a least-squares (LS) problem at every mixing step. In large-scale scientific computing, particularly on High-Performance Computing (HPC) platforms, the cost of solving these LS problems—often involving tall-and-skinny matrices with millions of rows—becomes a significant bottleneck. Existing approaches to reduce this cost either rely on physics-specific approximations (which are not generalizable) or adaptive sketching techniques that may introduce instability or memory-access overhead (cache misses) if not carefully managed.

Methodology
The authors propose a novel two-level sketching extension of the AAP method. This approach decomposes the approximation of the LS problem into two distinct, complementary stages:

Level 1: Static Physics-Based Projection ( $\Pi_1$ ):
- This level projects the residual onto a specific subset of physical fields (e.g., pressure in Stokes flow or extracellular potential in Bidomain models).
- Motivation: Multi-physics problems can often be recast as systems involving a single variable (analogous to the Schur complement in linear systems). Furthermore, different physical fields often operate on vastly different scales; combining them in a monolithic LS problem can degrade conditioning.
- Implementation: This operator is static and determined before execution, allowing for pre-allocation of memory and reducing the dimension of the LS matrix from $n$ to $\ell_1$ .
Level 2: Dynamic Algebraic Sketching ( $\Pi_2$ ):
- This level performs an adaptive subselection of rows from the already projected matrix.
- Stability Analysis: The authors extend backward stability analysis (previously applied to linear systems) to non-linear fixed-point iterations under the assumption of Lipschitz continuity. They derive conditions where the perturbation introduced by sketching does not compromise the convergence of AAP.
- Adaptive Strategy: The algorithm estimates stability thresholds ( $\epsilon_{LHS}$ and $\epsilon_{RHS}$ ) using inexpensive approximations of the smallest singular value and the Lipschitz constant. If these thresholds are satisfied, a mask is applied.
- Cache Awareness: To mitigate the performance penalty of random memory access (cache misses), the authors conducted empirical benchmarks. They determined that for matrix-vector products, retaining no more than 10% of rows yields speedups, while for QR factorizations, retaining up to 80% is optimal. The strategy employs either "subselection" (keeping rows with the largest residuals) or "randomized" selection, governed by convergent series parameters ( $\eta_j$ ).

Key Contributions

Structured Decomposition: The paper introduces a structured two-level decomposition where the static physics-based restriction addresses conditioning and scaling, while dynamic algebraic sketching introduces controlled perturbations. The authors argue these roles are distinct and cannot be merged without loss of robustness.
Non-Linear Stability Analysis: The work extends backward stability analysis to non-linear operators, providing theoretical justification for adaptive row selection in non-linear fixed-point iterations.
Memory and Cache Optimization: The implementation utilizes in-place operations and specific randomized selection guidelines (10% for mat-vec, 80% for QR) to minimize memory footprints and cache misses, addressing practical HPC constraints.
Open-Source Implementation: The algorithm is implemented in Julia, utilizing libraries like Ferrite and Gridap, and is made available via a GitHub repository.

Results
The method was tested on four benchmark problems: Stokes, $p$ -Laplacian, Bidomain equations, and stationary Navier-Stokes, across varying problem sizes (Degrees of Freedom).

Performance Gains: The two-level sketching AAP achieved up to 50% reduction in time-to-solution compared to standard Anderson Acceleration (AA) without degrading convergence rates.
Problem-Specific Behavior:
- Stokes: The pressure-based mask was most effective, reducing iterations by 24% and time by 33% in large problems. The "Randomized Power" adaptivity strategy was the most efficient.
- Bidomain: The extracellular mask performed robustly, while the intracellular mask caused divergence in large problems. Randomized adaptivity yielded up to a 43% reduction in CPU time.
- Navier-Stokes: The velocity mask was superior to the pressure mask (contrary to Stokes), though gains were modest (~9%) because the dominant cost was the direct linear solver rather than the LS solve.
- $p$ -Laplacian: Randomized adaptivity strategies provided the best performance for larger problems.
Robustness: The adaptive strategies maintained convergence behavior comparable to non-adaptive methods, confirming the stability of the proposed sketching bounds.

Significance and Claims
The authors claim that their work provides a stability-driven framework for sketching Anderson acceleration. They emphasize that the goal is not to establish global convergence rates for sketching (which remains an open problem even for standard AA) but to characterize admissible approximations that preserve the convergence behavior of the exact method.

The significance lies in the ability to reduce the computational overhead of the LS solve—a non-negligible fraction of runtime in repeated AA applications—without altering the underlying nonlinear solver or preconditioner. The method is particularly effective in scenarios where residual evaluation is not excessively dominant, allowing the savings in the LS solve to translate directly into total time-to-solution reductions. The paper concludes that this approach is robust, scalable, and ready for integration into high-performance scientific computing frameworks.