Asynchronous Jacobi and randomized Gauss--Seidel methods in shared and distributed memory: A unified convergence-rate analysis
Abstract
Asynchronous iterative methods are attractive for large-scale parallel computing because they reduce synchronization and communication overhead. Existing convergence-rate analyses, however, have primarily focused on shared memory implementations, whereas distributed memory systems introduce more general and potentially inconsistent communication delays. In this work, we revisit asynchronous Jacobi and randomized Gauss--Seidel (RGS) methods for symmetric positive definite linear systems from a unified perspective. We first introduce a general asynchronous model that encompasses both shared memory and distributed memory settings and expresses the two methods through a common coordinate-update framework. We then establish linear convergence in expectation under an explicit stability condition. The resulting convergence bound depends algebraically on the delay through the quantity √(ρτ)+ρτ, where τ is the maximum communication delay and ρ reflects the communication pattern of the underlying parallel implementation. In particular, under an appropriate scaling regime with ρτ=O(1), the guaranteed per-iteration convergence rate has the same asymptotic order as that of synchronous RGS. These results provide a unified framework for quantifying the effect of asynchronicity on asynchronous Jacobi/RGS methods in both shared and distributed memory environments.
Related
- A Unified Framework for Wasserstein Convergence of ULMC Methods beyond Log-Concavity: Old and New
- On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems
- A Unified Framework for Randomized Row-Action Methods for Structured Data Fitting and Constraint Geometry
- Asynchronous Sensitivity-Based Distributed NMPC
- Technical Report: Partially Asynchronous Distributed Optimization on Riemannian Manifolds
BibTeX
@misc{carson2026asynchronous,
title = {{Asynchronous Jacobi and randomized Gauss--Seidel methods in shared and distributed memory: A unified convergence-rate analysis}},
author = {Erin Carson and Yuxin Ma},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15605},
eprint = {2609.15605},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15605},
}
RIS
TY - UNPB
TI - Asynchronous Jacobi and randomized Gauss--Seidel methods in shared and distributed memory: A unified convergence-rate analysis
AU - Erin Carson
AU - Yuxin Ma
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15605
UR - https://arxiv.org/abs/2609.15605
AB - Asynchronous iterative methods are attractive for large-scale parallel computing because they reduce synchronization and communication overhead. Existing convergence-rate analyses, however, have primarily focused on shared memory implementations, whereas distributed memory systems introduce more general and potentially inconsistent communication delays. In this work, we revisit asynchronous Jacobi and randomized Gauss--Seidel (RGS) methods for symmetric positive definite linear systems from a unified perspective. We first introduce a general asynchronous model that encompasses both shared memory and distributed memory settings and expresses the two methods through a common coordinate-update framework. We then establish linear convergence in expectation under an explicit stability condition. The resulting convergence bound depends algebraically on the delay through the quantity √(ρτ)+ρτ, where τ is the maximum communication delay and ρ reflects the communication pattern of the underlying parallel implementation. In particular, under an appropriate scaling regime with ρτ=O(1), the guaranteed per-iteration convergence rate has the same asymptotic order as that of synchronous RGS. These results provide a unified framework for quantifying the effect of asynchronicity on asynchronous Jacobi/RGS methods in both shared and distributed memory environments.
ER -