A Fast Distributed Solver for Linear Systems Under Generalized Diagonal Dominance

• 成果类型: Article
• 署名作者: Zhang, Zhaorong; Cai, Qianqian; Fu, Minyue
• 署名单位: University of Newcastle; Guangdong University of Technology
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3010261
• 发表日期: 2021
• 页码: 2423-2429
• 关键词: Linear systems; Distributed algorithms; Jacobian matrices; information exchange; nickel; Complexity theory; iterative methods; Distributed algorithm; distributed estimation; distributed optimization; Linear systems

摘要

This article proposes a new distributed algorithm for solving linear systems associated with a sparse graph under a generalized diagonal dominance assumption. The algorithm runs iteratively on each node of the graph, with low complexities on local information exchange between neighboring nodes, local computation, and local storage. For an acyclic graph under the condition of diagonal dominance, the algorithm is shown to converge to the correct solution in a finite number of iterations, equaling the graph diameter. For a loopy graph, the algorithm is shown to converge to the correct solution asymptotically. Simulations verify that the proposed algorithm significantly outperforms the classical Jacobi method and an orthogonal projection-based method.