A Fast Convergent Distributed Algorithm for Solving Linear Systems with Diagonal Dominance

Title: A Fast Convergent Distributed Algorithm for Solving Linear Systems with Diagonal Dominance

报告人: Minyue Fu (付敏跃) Chair Professor, Department of Electrical and Computer Engineering at the University of Newcastle, Australia

报告时间: 2018年4月11号, 16:00

报告地点: 知新楼B924

Abstract: In this talk, we present a new distributed algorithm for solving linear systems associated with a sparse graph under a generalised diagonal dominance assumption. The algorithm runs iteratively on each node of the graph, with low complexities on local information exchange between neighbouring 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, equalling the diameter of the graph. 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 a recent distributed linear system solver based on average consensus and orthogonal projection.  If time permits, we will discuss variants of this algorithm for solving two related problems: average consensus and distributed least squares.

邀请人: 马树萍