2021/07/29 by Haodi Ping, Ping, Haodi, Yongcai Wang +3
Computer Science · Engineering · #Distributed #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #Indoor and Outdoor Localization Technologies #Parallel #Sparse and Compressive Sensing Techniques #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.2107.13814
arxiv created 2021/07/29 · openalex publication_date 2021/07/29 · arxiv updated 2021/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Distributed algorithms to solve linear equations in multi-agent networks have attracted great research attention and many iteration-based distributed algorithms have been developed. The convergence speed is a key factor to be considered for distributed algorithms, and it is shown dependent on the spectral radius of the iteration matrix. However, the iteration matrix is determined by the network structure and is hardly pre-tuned, making the iterative-based distributed algorithms may converge very slowly when the spectral radius is close to 1. In contrast, in centralized optimization, the Conjugate Gradient (CG) is a widely adopted idea to speed up the convergence of the centralized solvers, which can guarantee convergence in fixed steps. In this paper, we propose a general distributed implementation of CG, called DCG. DCG only needs local communication and local computation, while inheriting the characteristic of fast convergence. DCG guarantees to converge in 4Hn rounds, where H is the maximum hop number of the network and n is the number of nodes. We present the applications of DCG in solving the least square problem and network localization problem. The results show the convergence speed of DCG is three orders of magnitude faster than the widely used Richardson iteration method.