Search papers, labs, and topics across Lattice.
This paper investigates the performance of randomized Kaczmarz methods with adaptive row selection in an asynchronous shared-memory environment, revealing critical insights into how concurrent modifications affect stability and efficiency. The authors identify a boundary condition that dictates optimal sampling aggressiveness relative to thread count, demonstrating that aggressive sampling is beneficial when tuned correctly. Key findings include the instability of threshold-greedy selection at high thread counts and the advantages of using inconsistent reads over consistent-snapshot reads, which can lead to unexpected divergences.
Aggressive sampling can significantly enhance performance in asynchronous Kaczmarz methods, but only if tuned just right鈥攖oo much can lead to instability.
Randomized Kaczmarz is a natural fit for large sparse least-squares and tomographic reconstruction, and adaptive row selection can reduce iteration counts. However, deploying adaptive selection on a shared-memory machine means sampling from a residual that lock-free workers are concurrently modifying, often using stale data. We present the first systematic study of this regime: residual-weighted and greedy Kaczmarz under asynchronous execution, measured across 339 runs on a 96-core node with realized (not injected) delays. Four findings carry directly to practice. (i) Stability is governed by a boundary $\ell^*(T)$ between sampling aggressiveness and thread count; below it, more aggressive sampling is strictly better, so one should tune to just inside the cliff. (ii) Threshold-greedy selection (the standard accelerated rule) is unstable at high thread counts, diverging almost immediately. (iii) Under-relaxation buys back the cliff at a predictable cost, giving a usable safety knob. (iv) Consistent-snapshot reads admit a rare, scheduling-dependent divergence that live (inconsistent) reads never exhibited and that is also cheaper, making inconsistent reads the right default. We validate the implementation against published sequential results and outline the distributed two-level sampler these measurements motivate.
