Communication-Efficient Distributed Algorithms for Solving Linear Algebraic Equations over Directed Graphs

Abstract

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. Show more