Residual-Weighted Randomized Jacobi: Sharpened Bounds via Residual Concentration and Asynchronous Extension
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917552436805632 |
|---|---|
| author | Coleman, Evan |
| author_facet | Coleman, Evan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_01232 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Residual-Weighted Randomized Jacobi: Sharpened Bounds via Residual Concentration and Asynchronous Extension Coleman, Evan Numerical Analysis Distributed, Parallel, and Cluster Computing 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. |
| title | Residual-Weighted Randomized Jacobi: Sharpened Bounds via Residual Concentration and Asynchronous Extension |
| topic | Numerical Analysis Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2606.01232 |