TY - GEN

T1 - A communication-efficient distributed algorithm for solving linear algebraic equations

AU - Liu, Ji

AU - Gao, Xiaobin

AU - Basar, Tamer

N1 - Publisher Copyright:
© 2014 University of Trento.

PY - 2014/7/2

Y1 - 2014/7/2

N2 - This paper proposes a communication-efficient distributed algorithm for solving linear algebraic equations of the form Ax = b 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 time-dependent undirected graph. To reduce communication costs at each iteration, 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 matrix A and vector b for which the equation has at least one solution and any repeatedly jointly connected sequence of neighbor graphs, the algorithm causes all agents' estimates to converge to the same solution to Ax = b under appropriate assumption. An asynchronous version of the algorithm is also proposed in which each agent independently updates its estimate at times determined by its own clock. It is not assumed that the agents' clocks are synchronized or that the event times at which any one agent updates its estimate are evenly spaced. It is shown that in the absence of transmission delays, convergence to the same solution occurs even if the cycle with which each agent broadcasts the entries of its estimate is not consistent with the cycles of its neighbors.

AB - This paper proposes a communication-efficient distributed algorithm for solving linear algebraic equations of the form Ax = b 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 time-dependent undirected graph. To reduce communication costs at each iteration, 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 matrix A and vector b for which the equation has at least one solution and any repeatedly jointly connected sequence of neighbor graphs, the algorithm causes all agents' estimates to converge to the same solution to Ax = b under appropriate assumption. An asynchronous version of the algorithm is also proposed in which each agent independently updates its estimate at times determined by its own clock. It is not assumed that the agents' clocks are synchronized or that the event times at which any one agent updates its estimate are evenly spaced. It is shown that in the absence of transmission delays, convergence to the same solution occurs even if the cycle with which each agent broadcasts the entries of its estimate is not consistent with the cycles of its neighbors.

UR - http://www.scopus.com/inward/record.url?scp=84994223360&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84994223360&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84994223360

T3 - 2014 7th International Conference on Network Games, Control and Optimization, NetGCoop 2014

SP - 62

EP - 69

BT - 2014 7th International Conference on Network Games, Control and Optimization, NetGCoop 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 7th International Conference on Network Games, Control and Optimization, NetGCoop 2014

Y2 - 29 October 2014 through 31 October 2014

ER -