TY - GEN

T1 - Stochastic communication-efficient distributed algorithms for solving linear algebraic equations

AU - Gao, Xiaobin

AU - Liu, Ji

AU - Basar, Tamer

PY - 2016/10/10

Y1 - 2016/10/10

N2 - In this paper, we propose two stochastic distributed algorithms for solving linear algebraic equations in the form of Ax = b among a network of m > 1 agents. Each agent knows only a subset of the rows of the partitioned matrix [A b]. Each agent recursively updates its estimate of a solution based on the messages received only from its neighbors. The neighbor relationships among the agents are captured by a directed graph whose vertices correspond to agents and whose arcs characterize neighbor relationships. To reduce the communication load and the memory used, each agent partitions its vector of estimate into multiple blocks, and randomly chooses and broadcasts one block at each iteration. Under some technical conditions, we show that for any linear equation admitting a unique solution and any strongly connected neighbor graph, all agents are almost surely able to compute ultimately the unique solution to the linear equation by applying the proposed algorithms.

AB - In this paper, we propose two stochastic distributed algorithms for solving linear algebraic equations in the form of Ax = b among a network of m > 1 agents. Each agent knows only a subset of the rows of the partitioned matrix [A b]. Each agent recursively updates its estimate of a solution based on the messages received only from its neighbors. The neighbor relationships among the agents are captured by a directed graph whose vertices correspond to agents and whose arcs characterize neighbor relationships. To reduce the communication load and the memory used, each agent partitions its vector of estimate into multiple blocks, and randomly chooses and broadcasts one block at each iteration. Under some technical conditions, we show that for any linear equation admitting a unique solution and any strongly connected neighbor graph, all agents are almost surely able to compute ultimately the unique solution to the linear equation by applying the proposed algorithms.

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

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

U2 - 10.1109/CCA.2016.7587861

DO - 10.1109/CCA.2016.7587861

M3 - Conference contribution

AN - SCOPUS:84994381565

T3 - 2016 IEEE Conference on Control Applications, CCA 2016

SP - 380

EP - 385

BT - 2016 IEEE Conference on Control Applications, CCA 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE Conference on Control Applications, CCA 2016

Y2 - 19 September 2016 through 22 September 2016

ER -