Stochastic communication-efficient distributed algorithms for solving linear algebraic equations

Xiaobin Gao, Ji Liu, Tamer Basar

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

Abstract

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.

Original languageEnglish (US)
Title of host publication2016 IEEE Conference on Control Applications, CCA 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages380-385
Number of pages6
ISBN (Electronic)9781509007554
DOIs
StatePublished - Oct 10 2016
Event2016 IEEE Conference on Control Applications, CCA 2016 - Buenos Aires, Argentina
Duration: Sep 19 2016Sep 22 2016

Publication series

Name2016 IEEE Conference on Control Applications, CCA 2016

Other

Other2016 IEEE Conference on Control Applications, CCA 2016
CountryArgentina
CityBuenos Aires
Period9/19/169/22/16

ASJC Scopus subject areas

  • Control and Optimization
  • Modeling and Simulation

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

Cite this