TY - GEN
T1 - Communication-Efficient Distributed Algorithms for Solving Linear Algebraic Equations over Directed Graphs
AU - Liu, Ji
AU - Anderson, Brian D.O.
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/12/14
Y1 - 2020/12/14
N2 - This paper presents two communication-efficient distributed algorithms for solving linear algebraic equations of the form Ax = b, which has at least one solution, among a network of m> 1 agents. Each agent knows only a subset of the rows of the partitioned matrix [A b] and recursively updates its estimate of a solution by utilizing information received only from its neighbors. Neighbor relations are characterized by a fixed directed graph. The first algorithm aims to reduce communication costs at each iteration, in which each agent broadcasts the entries of its estimate in a cyclic manner, instead of broadcasting the entire vector of its estimate. It is shown that for any strongly connected neighbor graph, the algorithm causes all agents' estimates to converge to the same solution to Ax = b exponentially fast. The second algorithm reduces the vector size of each agent's estimate by exploiting the sparsity of the matrix A. It is shown that the algorithm causes each agent's estimate to converge to a specific part of the same solution to Ax = b corresponding to its own interest exponentially fast for a certain class of directed graphs.
AB - This paper presents two communication-efficient distributed algorithms for solving linear algebraic equations of the form Ax = b, which has at least one solution, among a network of m> 1 agents. Each agent knows only a subset of the rows of the partitioned matrix [A b] and recursively updates its estimate of a solution by utilizing information received only from its neighbors. Neighbor relations are characterized by a fixed directed graph. The first algorithm aims to reduce communication costs at each iteration, in which each agent broadcasts the entries of its estimate in a cyclic manner, instead of broadcasting the entire vector of its estimate. It is shown that for any strongly connected neighbor graph, the algorithm causes all agents' estimates to converge to the same solution to Ax = b exponentially fast. The second algorithm reduces the vector size of each agent's estimate by exploiting the sparsity of the matrix A. It is shown that the algorithm causes each agent's estimate to converge to a specific part of the same solution to Ax = b corresponding to its own interest exponentially fast for a certain class of directed graphs.
UR - http://www.scopus.com/inward/record.url?scp=85099878524&partnerID=8YFLogxK
U2 - 10.1109/CDC42340.2020.9304062
DO - 10.1109/CDC42340.2020.9304062
M3 - Conference contribution
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 5360
EP - 5365
BT - 2020 59th IEEE Conference on Decision and Control, CDC 2020
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 59th IEEE Conference on Decision and Control, CDC 2020
Y2 - 14 December 2020 through 18 December 2020
ER -