🔢 mathematics

Adaptive Row Selection Meets Asynchrony in Randomized Kaczmarz

This paper presents the first systematic study of adaptive row selection in Randomized Kaczmarz under asynchronous execution, identifying stability boundaries, demonstrating the superiority of inconsistent reads over consistent snapshots, and proposing under-relaxation as a practical mechanism to maintain convergence on multi-core systems.

Original authors: Evan Coleman

Published 2026-07-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Evan Coleman

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 giant, messy puzzle where thousands of people are working on it at the same time in a shared room. This is what happens when computers try to solve massive math problems using a method called Randomized Kaczmarz. It's like a team of lock-free workers, each grabbing a piece of the puzzle (a row of equations), fixing it, and shouting the change to everyone else without waiting for permission.

Usually, to solve these puzzles faster, you want the workers to be "smart." Instead of picking puzzle pieces at random, you want them to grab the pieces that are the most broken or "noisy" (high residual) first. This is called adaptive selection. It's like a chef who only cooks the burnt toast first because it needs the most attention.

But here's the twist: when you have a huge team (like 96 workers) all shouting updates at once, the "noise" they hear is often outdated. One worker might think a piece is burnt because they saw it 5 seconds ago, but another worker just fixed it. This is the world of asynchronous computing.

The "Cliff" of Chaos

The authors of this paper ran a massive experiment on a 96-core computer to see what happens when you combine "smart" selection with "chaotic" teamwork. They ran 339 different tests on real hardware (not just a simulation) using three types of problems: a standard math test, a medical imaging (tomography) problem, and a library of standard sparse matrices.

They discovered a dangerous stability boundary, which they call a "cliff."

Think of it like a tightrope walker. The "aggressiveness" of the smart selection is how much the walker leans forward. The "thread count" (number of workers) is how windy it is.

The Finding: If you lean too far forward (pick the "most broken" pieces too aggressively) while the wind is too strong (too many workers), you don't just wobble—you fall off the cliff immediately.
The Result: On their 96-core machine, if the workers were too greedy (using a specific mathematical setting called $\ell \ge 2$ or the standard "greedy" rule), the system didn't just slow down; it diverged (exploded into chaos) almost instantly. In fact, the standard "greedy" rule failed in every single test at high thread counts.

The "Interference Floor"

Why does this happen? The authors explain it with a concept called the interference floor.
Imagine the puzzle pieces are getting fixed, but the workers are also accidentally bumping into each other, creating new noise. When the puzzle is very messy (high error), the workers can easily tell which piece is the worst. But as the puzzle gets cleaner, the "noise" from the workers bumping into each other becomes just as loud as the actual problem.
If the workers are too greedy, they start picking pieces that are actually just "bumps" caused by their own teammates, not real errors. They keep fixing the same spots over and over, making the noise louder and louder until the whole system crashes.

What Doesn't Work (and What Does)

The paper explicitly rules out a few things that people might guess would help:

Taking a "Snapshot": One idea was to have every worker take a perfect, frozen photo of the whole puzzle before starting their turn (consistent reads). The authors found this doesn't help and is actually more expensive. In fact, in one specific test, taking a snapshot caused a rare, catastrophic crash that the "live" (messy) reading method never did.
Just adding more workers: More workers don't mean more speed if you cross the cliff. In fact, more workers mean you have to be less greedy to stay safe.

So, what is the solution?

The Safety Knob (Under-relaxation): If you are pushed past the cliff by having too many workers, you can save the system by taking smaller steps. The authors found that if you cut the step size in half (using a factor $\beta \le 0.5$ ), the system stabilizes. It's like telling the workers, "Don't fix the whole piece; just nudge it a little." It costs a bit more time (about 2x slower than the ideal math prediction), but it saves the run.
Live Reads are Better: The paper suggests that the "messy" way of reading data (live reads) is actually the best default. It's cheaper and, surprisingly, more stable against those rare, scheduling-dependent crashes.
The Sweet Spot: The best strategy is to tune your "greediness" just inside the cliff. You want to be as aggressive as possible without falling off. This "cliff" moves depending on how many workers you have and how much the puzzle pieces are connected to each other.

The Bottom Line

The paper proves that aggressive selection and high concurrency are enemies unless you manage them carefully.

The Rule: The more workers you have, the less greedy you can be.
The Metric: The stability isn't about how "perfect" the math looks; it's about the mean pairwise coupling (how much the puzzle pieces touch each other). If the pieces are too connected and you have too many workers, the system will crash unless you slow down your steps.
The Scale: On a 96-core machine, the system can handle about 10 rows per thread to stay safe. If you have fewer rows per worker, the system collapses regardless of how smart the selection is.

In short, if you want to solve these giant puzzles with a huge team, don't let the workers get too greedy. Keep them on a leash, take smaller steps if the room gets crowded, and let them read the messy, live updates rather than waiting for a perfect snapshot. It's a race to the edge of the cliff, but if you tune it right, you can run faster than anyone else without falling.

Technical Summary: Adaptive Row Selection Meets Asynchrony in Randomized Kaczmarz

Problem Statement

The Randomized Kaczmarz (RK) method is a row-action solver effective for large sparse least-squares and tomographic reconstruction. While adaptive row selection (e.g., greedy or residual-weighted sampling) accelerates convergence by prioritizing high-residual equations, and asynchronous execution enables parallelism via lock-free updates, combining these mechanisms creates a regime not covered by existing theory.

Current theoretical frameworks assume either a current residual vector (for adaptive selection) or a fixed sampling distribution (for asynchronous analysis). In practice, on shared-memory machines, lock-free workers modify the residual vector concurrently. Consequently, adaptive selectors operate on stale, imperfect distributions where the discrepancy from the ideal grows with the number of in-flight updates. This paper addresses the lack of systematic measurement regarding how residual-weighted and greedy Kaczmarz behave under asynchronous execution with realized hardware delays.

Methodology

The study instruments residual-weighted and threshold-greedy Kaczmarz algorithms across 339 runs on a 96-core node. The experiments utilize a power-weighted sampling family where the probability of selecting row $i$ is proportional to $|r_i|^\ell$ . The exponent $\ell$ interpolates between uniform sampling ( $\ell=0$ ) and the maximal-residual Motzkin rule ( $\ell \to \infty$ ).

Experimental Setup:

Hardware: A 96-core ACES node (Texas A&M) with threads pinned to cores.
Delays: Staleness is measured via realized dispatch-to-commit gaps rather than synthetically injected delays.
Test Problems: Three categories were used: (1) a benign dense system, (2) coherent tomographic problems at two scales, and (3) 16 SuiteSparse matrices from the Bai–Wu test suite.
Read Semantics: Two policies were compared:
- Consistent Reads: Workers snapshot the residual vector once per step for both sampling and update calculation.
- Inconsistent (Live) Reads: The sampling CDF is built from live atomic reads, and the specific residual value is re-read after row selection.
Validation: The implementation was validated against published sequential results and verified by recomputing $b - Ax$ at termination to ensure divergences were numerical behaviors rather than data races.

Key Contributions and Findings

1. The Stability Boundary $\ell^*(T)$

The paper identifies a stability boundary in the $(\ell, T)$ plane (sampling exponent vs. thread count).

Observation: As concurrency ( $T$ ) increases, the system tolerates less aggressive sampling (lower $\ell$ ).
Mechanism: Below the boundary, more aggressive sampling is strictly faster. Above the boundary, the sampler begins ranking "interference" (perturbations caused by $\Theta(T)$ in-flight updates) rather than signal, leading to divergence.
Tuning Implication: Optimal tuning is a "race to a cliff," where one must select the largest $\ell$ that remains just inside the stability boundary for a given $T$ .

2. Instability of Threshold-Greedy Selection

Standard threshold-greedy selection (GRK), which selects rows above a residual cutoff, is found to be incompatible with high-concurrency asynchronous execution.

Result: At $T=96$ , GRK diverges within a fraction of a sweep on all test problems, regardless of read semantics. The concentration of selection on the largest residuals causes workers to repeatedly update the same coupled neighborhoods, amplifying interference.

3. Step-Size Control as a Recovery Mechanism

Under-relaxation (reducing the step size $\beta$ ) can restore convergence for configurations that diverge at full step ( $\beta=1$ ).

Effectiveness: Every configuration that diverged at $\beta=1$ converged when $\beta \le 0.5$ .
Cost: This recovery incurs a predictable cost. The sweep-count penalty is approximately $1.7\text{--}2.3\times$ higher than the synchronous prediction of $1/[\beta(2-\beta)]$ , attributed to an "asynchronous interference premium."

4. Read-Mode Semantics and Tail Risk

Contrary to findings in asynchronous Jacobi, read consistency does not govern the primary stability boundary here, but it does affect tail behavior.

Divergence: Consistent-snapshot reads admitted a rare, scheduling-dependent divergence (1 in 36 runs on a coherent tomographic problem) that inconsistent (live) reads never exhibited.
Efficiency: Inconsistent reads are cheaper per step (no full residual copy) and showed no tail failures in matched tests. The paper concludes inconsistent reads are the superior default for broad-coupling regimes.

5. Structural Discriminators

The stability boundary is strictly ordered by the mean pairwise coupling $\bar{\chi} = E|Q_{ij}|$ , where $Q = AA^\top$ .

Spectral proxies (like off-diagonal Gram-row norms) and worst-case coherence failed to predict stability.
Stability is a race between convergence speed and interference growth. Problems with higher coupling density require less aggressive sampling or lower thread counts to remain stable.

Significance and Claims

The paper claims to provide the first systematic study of adaptive row selection under asynchronous execution with realized delays. Its primary significance lies in defining the practical limits of combining these two acceleration techniques:

Practical Tuning: It establishes that tuning adaptive Kaczmarz for parallelism is not merely about maximizing selection aggressiveness but requires navigating a concurrency-dependent stability cliff.
Algorithmic Guidance: It demonstrates that standard greedy rules (GRK) are unstable at scale and that inconsistent reads are the preferred implementation strategy for shared-memory Kaczmarz.
Implementation Safety: It validates that under-relaxation serves as a reliable "safety knob" to recover convergence when concurrency forces a reduction in sampling aggressiveness.
Future Direction: The findings motivate the development of a distributed two-level sampler to decouple sampling staleness from iterate staleness, addressing the $O(m)$ global sampling bottleneck observed in the experiments.

The authors remain modest, noting that the observed phenomena are properties of the asynchronous iteration itself, not implementation errors, and that the theoretical understanding of the $\ell^*(T)$ boundary and the super-quadratic under-relaxation premium requires further development.