Stochastic communication-efficient distributed algorithms for solving linear algebraic equations

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.