Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates a family of randomized stationary methods for solving symmetric positive definite linear systems, specifically focusing on a power-weighted approach that interpolates between uniform randomized Jacobi and Gauss–Southwell methods. By employing the inverse participation ratio (IPR) to sharpen the convergence analysis, the authors demonstrate that their method can enhance expected progress per iteration by a factor proportional to the IPR, which can be computed efficiently. The study also extends the analysis to asynchronous settings, revealing critical insights into the stability of power-weighted sampling under varying concurrency conditions.
Amplifying convergence rates by leveraging the inverse participation ratio reveals unexpected stability dynamics in high-concurrency scenarios.
We study randomized stationary methods for symmetric positive definite linear systems in which component $j$ is selected with probability proportional to $|r_j|^\ell$. This power-weighted family interpolates continuously between uniform randomized Jacobi as $\ell \to 0$ and Gauss--Southwell greedy relaxation as $\ell \to \infty$. For the central case $\ell = 2$, we sharpen the standard one-step convergence analysis using the inverse participation ratio (IPR) $ν^2(r) = n\|r\|_4^4/\|r\|_2^4$, which equals $1$ when the residual is uniform and grows toward $n$ as it concentrates. The resulting bound amplifies the expected per-step progress by exactly $ν^2$ over the uniform-sampling baseline. The IPR can be computed online at $O(n)$ cost and doubles as a per-iteration diagnostic. We extend the analysis to asynchronous power-weighted Jacobi via the Avron--Druinsky--Gupta framework, obtaining an epoch-based convergence theorem in which the IPR controls both the progress coefficient and the allowed-delay window. Numerical experiments on shared-memory hardware support the sharpened bound and show the IPR trajectory is essentially concurrency-insensitive. Unexpectedly, consistent-reads execution, the easier case for the ADG analysis, destabilizes power-weighted sampling at high concurrency while inconsistent reads remain stable; the same IPR that amplifies progress amplifies a thread-collision rate that inconsistent reads appear to absorb. We propose a feedback-damping mechanism and verify two predictions about its dependence on problem size.