{"ID":2921731,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-03T05:56:00.181519634Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.01232","arxiv_id":"2606.01232","title":"Residual-Weighted Randomized Jacobi: Sharpened Bounds via Residual Concentration and Asynchronous Extension","abstract":"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.","short_abstract":"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 \\...","url_abs":"https://arxiv.org/abs/2606.01232","url_pdf":"https://arxiv.org/pdf/2606.01232v1","authors":"[\"Evan Coleman\"]","published":"2026-05-31T13:29:29Z","proceeding":"math.NA","tasks":"[\"math.NA\",\"cs.DC\"]","methods":"[]","has_code":false}