Asynchronous Stochastic Block Projection Algorithm for Solving Linear Systems under Predefined Communication Patterns
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916794704330752 |
|---|---|
| author | Yin, Yanchen Wang, Yongli |
| author_facet | Yin, Yanchen Wang, Yongli |
| contents | This paper proposes an event-triggered asynchronous distributed randomized block Kaczmarz projection (ER-AD-RBKP) algorithm for efficiently solving large-scale linear systems in resource-constrained and communication-unstable environments. The algorithm enables each agent to update its local state estimate independently and engage in communication only when specific triggering conditions are satisfied, thereby significantly reducing communication overhead. At each iteration, agents perform projections using randomly selected partial local data blocks to lower per-iteration computational costs and enhance scalability. By defining events that ensure strong connectivity in the communication graph, we derive the sufficient conditions for global convergence under a probabilistic framework, proving that the algorithm converges exponentially in expectation as long as no extreme events (e.g., permanent agent disconnection) occur. Besides, for inconsistent systems, auxiliary variables are incorporated to transform the problem into an equivalent consistent formulation, and theoretical error bounds are derived. Moreover, we implement the ER-AD-RBKP algorithm in an asynchronous communication environment built on ROS2, a distributed middleware framework for real-time robotic systems. We evaluate the algorithm under various settings, including varying numbers of agents, neighborhood sizes, communication intervals, and failure scenarios such as communication disruptions and processing faults. Experimental results demonstrate the robust performance of the proposed algorithm in terms of computational efficiency, communication cost, and system resilience, highlighting its strong potential for practical applicability in real-world distributed systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_14213 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asynchronous Stochastic Block Projection Algorithm for Solving Linear Systems under Predefined Communication Patterns Yin, Yanchen Wang, Yongli Numerical Analysis This paper proposes an event-triggered asynchronous distributed randomized block Kaczmarz projection (ER-AD-RBKP) algorithm for efficiently solving large-scale linear systems in resource-constrained and communication-unstable environments. The algorithm enables each agent to update its local state estimate independently and engage in communication only when specific triggering conditions are satisfied, thereby significantly reducing communication overhead. At each iteration, agents perform projections using randomly selected partial local data blocks to lower per-iteration computational costs and enhance scalability. By defining events that ensure strong connectivity in the communication graph, we derive the sufficient conditions for global convergence under a probabilistic framework, proving that the algorithm converges exponentially in expectation as long as no extreme events (e.g., permanent agent disconnection) occur. Besides, for inconsistent systems, auxiliary variables are incorporated to transform the problem into an equivalent consistent formulation, and theoretical error bounds are derived. Moreover, we implement the ER-AD-RBKP algorithm in an asynchronous communication environment built on ROS2, a distributed middleware framework for real-time robotic systems. We evaluate the algorithm under various settings, including varying numbers of agents, neighborhood sizes, communication intervals, and failure scenarios such as communication disruptions and processing faults. Experimental results demonstrate the robust performance of the proposed algorithm in terms of computational efficiency, communication cost, and system resilience, highlighting its strong potential for practical applicability in real-world distributed systems. |
| title | Asynchronous Stochastic Block Projection Algorithm for Solving Linear Systems under Predefined Communication Patterns |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2502.14213 |