A communication-efficient distributed algorithm for solving linear algebraic equations

Ji Liu, Xiaobin Gao, Tamer Basar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2014 7th International Conference on Network Games, Control and Optimization, NetGCoop 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages62-69
Number of pages8
ISBN (Electronic)9788884435743
StatePublished - Jun 7 2017
Event7th International Conference on Network Games, Control and Optimization, NetGCoop 2014 - Trento, Italy
Duration: Oct 29 2014Oct 31 2014

Publication series

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

Other

Other7th International Conference on Network Games, Control and Optimization, NetGCoop 2014
CountryItaly
CityTrento
Period10/29/1410/31/14

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Control and Optimization

Fingerprint Dive into the research topics of 'A communication-efficient distributed algorithm for solving linear algebraic equations'. Together they form a unique fingerprint.

Cite this