pith. sign in

arxiv: 2606.01232 · v1 · pith:464WXJGInew · submitted 2026-05-31 · 🧮 math.NA · cs.DC· cs.NA

Residual-Weighted Randomized Jacobi: Sharpened Bounds via Residual Concentration and Asynchronous Extension

Evan Coleman This is my paper

Pith reviewed 2026-06-28 16:32 UTC · model grok-4.3

classification 🧮 math.NA cs.DCcs.NA
keywords randomized Jacobiinverse participation ratioasynchronous iterationpower-weighted samplingconvergence analysisresidual concentrationlinear systems
0
0 comments X

The pith

Power-weighted randomized Jacobi improves one-step progress by the residual's inverse participation ratio ν^{2}.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that selecting components with probability proportional to |r_j|^{2} sharpens the expected per-step reduction in the error norm by exactly the factor u^{2}(r) = n||r||_{4}^{4}/||r||_{2}^{4} relative to uniform random selection. This ratio equals 1 for a flat residual and rises to n when the residual concentrates on few entries. The same quantity enters an epoch-based asynchronous convergence theorem, where it also sets the maximum tolerable delay. The bound is supported by shared-memory experiments in which the IPR trajectory stays largely insensitive to concurrency.

Core claim

For ρ-weighted Jacobi with ρ = 2, the standard one-step analysis is sharpened by replacing the uniform baseline with an IPR-amplified progress coefficient; the resulting epoch convergence theorem obtained via the Avron-Druinsky-Gupta framework has both its contraction factor and its allowable delay window controlled by the same online-computable IPR.

What carries the argument

The inverse participation ratio u^{2}(r) = n||r||_{4}^{4}/||r||_{2}^{4}, which multiplies the expected per-step progress and governs the delay tolerance in the asynchronous extension.

If this is right

  • Convergence accelerates automatically as the residual concentrates without any change to the algorithm.
  • The IPR can be maintained at O(n) cost per iteration and used both for analysis and as a runtime diagnostic.
  • In the asynchronous setting the same IPR value simultaneously tightens the progress bound and shrinks the permitted delay window.
  • The analysis applies to any symmetric positive definite matrix; no further spectral assumptions are required beyond positive definiteness.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Problems whose residuals naturally concentrate may see larger speed-ups than the uniform baseline predicts.
  • The observed stability difference between consistent and inconsistent reads at high concurrency suggests that thread collisions interact with the power-weighted selection rule in a way not captured by the epoch model.
  • A feedback mechanism that damps the weight exponent when the IPR exceeds a threshold could restore stability without sacrificing the sharpened bound.

Load-bearing premise

That the power-weighted selection rule for ρ = 2 admits a direct one-step analysis inside the existing uniform-sampling framework and that the Avron-Druinsky-Gupta epoch argument carries over unchanged once the IPR is inserted.

What would settle it

An experiment in which the measured contraction per epoch deviates from the IPR-predicted factor by more than the stated constants, or an asynchronous schedule in which the stable delay window is independent of the observed IPR.

read the original 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) $\nu^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 $\nu^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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript introduces a family of residual-weighted randomized Jacobi methods for symmetric positive definite linear systems, selecting component j with probability proportional to |r_j|^ℓ. This interpolates between uniform randomized Jacobi (ℓ→0) and Gauss-Southwell (ℓ→∞). For the central case ℓ=2, the standard one-step analysis is sharpened by the factor ν²(r)=n‖r‖₄⁴/‖r‖₂⁴ (the inverse participation ratio), which equals 1 for uniform residuals and grows with concentration; the expected per-step progress is thereby amplified exactly by ν² over the uniform baseline. The IPR is computable online in O(n) time and serves as a diagnostic. The analysis is extended to the asynchronous setting via the Avron-Druinsky-Gupta framework, yielding an epoch-based convergence theorem in which the IPR governs both the progress coefficient and the admissible delay window. Numerical experiments on shared-memory hardware corroborate the sharpened bound, demonstrate that the IPR trajectory is largely concurrency-insensitive, and document an unexpected stability difference between consistent and inconsistent reads at high concurrency, for which a feedback-damping mechanism is proposed and two size-dependent predictions are verified.

Significance. If the derivations hold, the work supplies a parameter-free sharpening of convergence bounds that follows directly from substituting the weighted selection probabilities into the standard expected-progress expression, together with an online diagnostic. The asynchronous extension and the empirical findings on read consistency provide concrete guidance for parallel implementations. The absence of auxiliary parameters or ad-hoc axioms in the central bound is a clear strength, as is the internal consistency of the one-step and epoch analyses with the cited frameworks.

minor comments (3)
  1. The definition and online computation of the IPR ν²(r) appear in the abstract; repeating the definition with an equation label in the main text (e.g., near the one-step analysis) would improve readability.
  2. The numerical-experiments section should state the precise test matrices (dimensions, condition numbers, generation method), the exact rules for data exclusion or iteration counting, and the hardware configuration to allow independent reproduction of the concurrency and stability results.
  3. The feedback-damping mechanism is introduced to address the observed destabilization; a short pseudocode or explicit update rule would clarify its implementation and the two verified predictions about problem-size dependence.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive evaluation, the accurate summary of the contributions, and the recommendation of minor revision. We appreciate the recognition that the central bound is parameter-free and follows directly from the weighted selection probabilities.

Circularity Check

0 steps flagged

No significant circularity; derivation is direct substitution

full rationale

The central claim substitutes the ℓ=2 probabilities p_j = r_j²/‖r‖₂² directly into the standard one-step expected-progress formula, producing the factor ν²(r) = n‖r‖₄⁴/‖r‖₂⁴ by algebraic identity; this is a mathematical consequence of the definition rather than a fitted parameter or self-referential loop. The ADG epoch extension carries the same coefficient forward as an external framework application with no overlapping-author citation load. No self-definitional, ansatz-smuggling, or renaming patterns appear; the IPR serves as both bound coefficient and online diagnostic without reducing the result to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard domain assumptions for linear systems and an existing asynchronous analysis framework, without introducing new free parameters or entities.

axioms (2)
  • domain assumption The linear system is symmetric positive definite
    Required for convergence properties of Jacobi-like methods and the one-step analysis.
  • domain assumption The Avron-Druinsky-Gupta framework applies to the asynchronous power-weighted Jacobi
    Invoked for the epoch-based convergence theorem controlling progress and delay window.

pith-pipeline@v0.9.1-grok · 5814 in / 1436 out tokens · 39539 ms · 2026-06-28T16:32:17.215339+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 3 canonical work pages

  1. [1]

    Journal of Fourier Analysis and Applications15(2), 262–278 (2009)

    Strohmer, T., Vershynin, R.: A randomized kaczmarz algorithm with exponential convergence. Journal of Fourier Analysis and Applications15(2), 262–278 (2009)

    2009

  2. [2]

    Mathematics of Operations Research35(3), 641–654 (2010)

    Leventhal, D., Lewis, A.S.: Randomized methods for linear constraints: con- vergence rates and conditioning. Mathematics of Operations Research35(3), 641–654 (2010)

    2010

  3. [3]

    Journal of the ACM62(6), 51–15127 (2015) https://doi.org/10.1145/2814566

    Avron, H., Druinsky, A., Gupta, A.: Revisiting asynchronous linear solvers: Provable convergence rate through randomization. Journal of the ACM62(6), 51–15127 (2015) https://doi.org/10.1145/2814566

    work page doi:10.1145/2814566 2015

  4. [4]

    Clarendon Press, Oxford (1946)

    Southwell, R.V.: Relaxation Methods in Theoretical Physics. Clarendon Press, Oxford (1946)

    1946

  5. [5]

    Linear Algebra and its Applica- tions2(2), 199–222 (1969) https://doi.org/10.1016/0024-3795(69)90028-7

    Chazan, D., Miranker, W.: Chaotic relaxation. Linear Algebra and its Applica- tions2(2), 199–222 (1969) https://doi.org/10.1016/0024-3795(69)90028-7

    work page doi:10.1016/0024-3795(69)90028-7 1969

  6. [6]

    Journal of the ACM25(2), 226–244 (1978) https://doi.org/10.1145/322063.322067 33

    Baudet, G.M.: Asynchronous iterative methods for multiprocessors. Journal of the ACM25(2), 226–244 (1978) https://doi.org/10.1145/322063.322067 33

    work page doi:10.1145/322063.322067 1978

  7. [7]

    Prentice Hall, ??? (1989)

    Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numeri- cal Methods. Prentice Hall, ??? (1989)

    1989

  8. [8]

    Journal of Computational and Applied Mathematics123(1–2), 201–216 (2000) https://doi.org/10.1016/ S0377-0427(00)00409-X

    Frommer, A., Szyld, D.B.: On asynchronous iterations. Journal of Computational and Applied Mathematics123(1–2), 201–216 (2000) https://doi.org/10.1016/ S0377-0427(00)00409-X

    2000

  9. [9]

    Linear algebra and its applications349(1-3), 125–154 (2002)

    Strikwerda, J.C.: A probabilistic analysis of asynchronous iteration. Linear algebra and its applications349(1-3), 125–154 (2002)

    2002

  10. [10]

    SIAM journal on Scientific Computing37(2), 169–193 (2015)

    Chow, E., Patel, A.: Fine-grained parallel incomplete lu factorization. SIAM journal on Scientific Computing37(2), 169–193 (2015)

    2015

  11. [11]

    In: 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp

    Wolfson-Pou, J., Chow, E.: Convergence models and surprising results for the asynchronous jacobi method. In: 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 940–949 (2018). IEEE

    2018

  12. [12]

    In: 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp

    Wolfson-Pou, J., Chow, E.: Asynchronous multigrid methods. In: 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 101– 110 (2019). IEEE

    2019

  13. [13]

    Numerical Algorithms87, 1635–1651 (2021) https://doi.org/10

    Chow,E.,Frommer,A.,Szyld,D.B.:AsynchronousRichardsoniterations:Theory and practice. Numerical Algorithms87, 1635–1651 (2021) https://doi.org/10. 1007/s11075-020-01023-3

    2021

  14. [14]

    SIAM Journal on Scientific Computing, 23–49 (2025)

    Wolfson-Pou, J., Chow, E.: Asynchronous semi-iterative methods and the asyn- chronous chebyshev method with multigrid preconditioning. SIAM Journal on Scientific Computing, 23–49 (2025)

    2025

  15. [15]

    SIAM Journal on Scientific Computing 42(6), 384–409 (2020)

    Glusa,C.,Boman,E.G.,Chow,E.,Rajamanickam,S.,Szyld,D.B.:Scalableasyn- chronous domain decomposition solvers. SIAM Journal on Scientific Computing 42(6), 384–409 (2020)

    2020

  16. [16]

    SIAM Journal on Scientific Computing43(1), 1–30 (2021)

    Kashi, A., Nadarajah, S.: An asynchronous incomplete block lu preconditioner for computational fluid dynamics on unstructured grids. SIAM Journal on Scientific Computing43(1), 1–30 (2021)

    2021

  17. [17]

    Computers & Fluids299, 106714 (2025)

    Kashi, A., Nadarajah, S.: On the effectiveness of fine-grain parallel linear itera- tions for computational aerodynamics on structured grids for graphics processing units. Computers & Fluids299, 106714 (2025)

    2025

  18. [18]

    Advances in neural information processing systems24(2011)

    Recht, B., Re, C., Wright, S., Niu, F.: Hogwild!: A lock-free approach to paral- lelizing stochastic gradient descent. Advances in neural information processing systems24(2011)

    2011

  19. [19]

    SIAM Journal on Optimization25(1), 351–376 (2015) 34

    Liu,J.,Wright,S.J.:Asynchronousstochasticcoordinatedescent:Parallelismand convergence properties. SIAM Journal on Optimization25(1), 351–376 (2015) 34

    2015

  20. [20]

    SIAM Journal on Scientific Computing 38(5), 2851–2879 (2016)

    Peng, Z., Xu, Y., Yan, M., Yin, W.: Arock: an algorithmic framework for asyn- chronous parallel coordinate updates. SIAM Journal on Scientific Computing 38(5), 2851–2879 (2016)

    2016

  21. [21]

    SIAM Journal on Scientific Computing, 1–22 (2025)

    Kalantzis, V., Xi, Y., Horesh, L., Saad, Y.: Straggler-tolerant stationary methods for linear systems. SIAM Journal on Scientific Computing, 1–22 (2025)

    2025

  22. [22]

    International Journal of Parallel Programming49(1), 51–80 (2021)

    Coleman, E., Jensen, E.J., Sosonkina, M.: Fault recovery methods for asyn- chronous linear solvers. International Journal of Parallel Programming49(1), 51–80 (2021)

    2021

  23. [23]

    arXiv preprint arXiv:2605.28426 (2026)

    Coleman, E., Sosonkina, M.: Fault tolerance of accelerated asynchronous fixed-point iterations on flexible computing infrastructure. arXiv preprint arXiv:2605.28426 (2026)

    Pith/arXiv arXiv 2026

  24. [24]

    SIAM Journal on Scientific Computing46(5), 3258–3281 (2024)

    Vogl, C.J., Atkins, Z.R., Fox, A., Międlar, A., Ponce, C.: Modifying the asyn- chronous jacobi method for data corruption resilience. SIAM Journal on Scientific Computing46(5), 3258–3281 (2024)

    2024

  25. [25]

    SIAM Journal on Optimization22(2), 341–362 (2012)

    Nesterov, Y.: Efficiencyof coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization22(2), 341–362 (2012)

    2012

  26. [26]

    SIAM Journal on Matrix Analysis and Applications36(4), 1660–1690 (2015)

    Gower, R.M., Richtárik, P.: Randomized iterative methods for linear systems. SIAM Journal on Matrix Analysis and Applications36(4), 1660–1690 (2015)

    2015

  27. [27]

    Canadian Journal of Mathematics6, 382–392 (1954)

    Agmon, S.: The relaxation method for linear inequalities. Canadian Journal of Mathematics6, 382–392 (1954)

    1954

  28. [28]

    Canadian Journal of Mathematics6, 393–404 (1954)

    Motzkin, T.S., Schoenberg, I.J.: The relaxation method for linear inequalities. Canadian Journal of Mathematics6, 393–404 (1954)

    1954

  29. [29]

    In: International Conference on Machine Learning, pp

    Nutini, J., Schmidt, M., Laradji, I., Friedlander, M., Koepke, H.: Coordinate descent converges faster with the gauss-southwell rule than random selection. In: International Conference on Machine Learning, pp. 1632–1641 (2015). PMLR

    2015

  30. [30]

    Linear Algebra and its Applications437(7), 1596–1610 (2012)

    Griebel, M., Oswald, P.: Greedy and randomized versions of the multiplicative schwarz method. Linear Algebra and its Applications437(7), 1596–1610 (2012)

    2012

  31. [31]

    Numerical Algorithms92(1), 639–664 (2023)

    Frommer, A., Szyld, D.B.: On the convergence of randomized and greedy relax- ation schemes for solving nonsingular linear systems of equations. Numerical Algorithms92(1), 639–664 (2023)

    2023

  32. [32]

    SIAM Journal on Scientific Computing39(5), 66–87 (2017)

    De Loera, J.A., Haddock, J., Needell, D.: A sampling kaczmarz–motzkin algo- rithm for linear feasibility. SIAM Journal on Scientific Computing39(5), 66–87 (2017)

    2017

  33. [33]

    SIAM Journal on Mathematics of Data Science3(1), 342–368 (2021) 35

    Haddock, J., Ma, A.: Greed works: An improved analysis of sampling kaczmarz– motzkin. SIAM Journal on Mathematics of Data Science3(1), 342–368 (2021) 35

    2021

  34. [34]

    SIAM Journal on Scientific Computing40(1), 592–606 (2018)

    Bai, Z.-Z., Wu, W.-T.: On greedy randomized kaczmarz method for solving large sparse linear systems. SIAM Journal on Scientific Computing40(1), 592–606 (2018)

    2018

  35. [35]

    Applied Mathematics Letters83, 21–26 (2018)

    Bai, Z.-Z., Wu, W.-T.: On relaxed greedy randomized kaczmarz methods for solving large sparse linear systems. Applied Mathematics Letters83, 21–26 (2018)

    2018

  36. [36]

    Numerical Linear Algebra with Applications26(4), 2237 (2019)

    Bai, Z.-Z., Wu, W.-T.: On greedy randomized coordinate descent methods for solving large linear least-squares problems. Numerical Linear Algebra with Applications26(4), 2237 (2019)

    2019

  37. [37]

    SIAM Journal on Matrix Analysis and Applications42(2), 954–989 (2021)

    Gower, R.M., Molitor, D., Moorman, J., Needell, D.: On adaptive sketch- and-project for solving linear systems. SIAM Journal on Matrix Analysis and Applications42(2), 954–989 (2021)

    2021

  38. [38]

    Procedia Computer Science80, 1906–1916 (2016)

    Wolfson-Pou, J., Chow, E.: Reducing communication in distributed asynchronous iterative methods. Procedia Computer Science80, 1906–1916 (2016)

    1906

  39. [39]

    In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp

    Wolfson-Pou, J., Chow, E.: Distributed southwell: an iterative method with low communication costs. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1–13 (2017)

    2017

  40. [40]

    In: 2019 Spring Simulation Conference (SpringSim), pp

    Coleman, E., Jensen, E.J., Sosonkina, M.: Enhancing asynchronous linear solvers through randomization. In: 2019 Spring Simulation Conference (SpringSim), pp. 1–12 (2019). IEEE

    2019

  41. [41]

    Cambridge university press, Cambridge (1952)

    Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities. Cambridge university press, Cambridge (1952)

    1952

  42. [42]

    Reviews of Modern Physics80(4), 1355–1417 (2008)

    Evers, F., Mirlin, A.D.: Anderson transitions. Reviews of Modern Physics80(4), 1355–1417 (2008)

    2008

  43. [43]

    In: Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Con- tributions to the Theory of Statistics, vol

    Rényi, A.: On measures of entropy and information. In: Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Con- tributions to the Theory of Statistics, vol. 4, pp. 547–562 (1961). University of California Press 36

    1961