A continuous-time distributed algorithm for solving linear equations

Ji Liu, Xudong Chen, M Tamer Basar, Angelia Nedic

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

Abstract

A continuous-time distributed algorithm is studied for solving linear equations of the form Ax = b with at least one solution. The equation is simultaneously solved by a network of m agents with the assumption that each agent knows only a subset of the rows of the partitioned matrix [A b ], the current estimates of the equation's solution generated by its current neighbors, and nothing more. Neighbor relationships among the agents are described by a piecewise-constant switching directed graph whose vertices correspond to agents and whose arcs depict neighbor relationships. It is shown that for any matrix-vector pair (A, b) for which the equation has a solution and any sequence of repeatedly jointly strongly connected graphs, the algorithm causes all agents' estimates to asymptotically converge to the same solution to Ax = b. The limiting behavior of the algorithm in the case when Ax = b does not have a solution is also studied. It is shown that for any static strongly connected graph, the algorithm causes all agents' estimates to asymptotically converge to different values, and therefore enables the agents to detect the no-solution case distributively.

Original languageEnglish (US)
Title of host publication2016 American Control Conference, ACC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages5551-5556
Number of pages6
ISBN (Electronic)9781467386821
DOIs
StatePublished - Jul 28 2016
Event2016 American Control Conference, ACC 2016 - Boston, United States
Duration: Jul 6 2016Jul 8 2016

Publication series

NameProceedings of the American Control Conference
Volume2016-July
ISSN (Print)0743-1619

Other

Other2016 American Control Conference, ACC 2016
CountryUnited States
CityBoston
Period7/6/167/8/16

Fingerprint

Linear equations
Parallel algorithms
Directed graphs

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Liu, J., Chen, X., Basar, M. T., & Nedic, A. (2016). A continuous-time distributed algorithm for solving linear equations. In 2016 American Control Conference, ACC 2016 (pp. 5551-5556). [7526540] (Proceedings of the American Control Conference; Vol. 2016-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ACC.2016.7526540

A continuous-time distributed algorithm for solving linear equations. / Liu, Ji; Chen, Xudong; Basar, M Tamer; Nedic, Angelia.

2016 American Control Conference, ACC 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 5551-5556 7526540 (Proceedings of the American Control Conference; Vol. 2016-July).

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

Liu, J, Chen, X, Basar, MT & Nedic, A 2016, A continuous-time distributed algorithm for solving linear equations. in 2016 American Control Conference, ACC 2016., 7526540, Proceedings of the American Control Conference, vol. 2016-July, Institute of Electrical and Electronics Engineers Inc., pp. 5551-5556, 2016 American Control Conference, ACC 2016, Boston, United States, 7/6/16. https://doi.org/10.1109/ACC.2016.7526540
Liu J, Chen X, Basar MT, Nedic A. A continuous-time distributed algorithm for solving linear equations. In 2016 American Control Conference, ACC 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 5551-5556. 7526540. (Proceedings of the American Control Conference). https://doi.org/10.1109/ACC.2016.7526540
Liu, Ji ; Chen, Xudong ; Basar, M Tamer ; Nedic, Angelia. / A continuous-time distributed algorithm for solving linear equations. 2016 American Control Conference, ACC 2016. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 5551-5556 (Proceedings of the American Control Conference).
@inproceedings{d1111a2c78f243d7b63fb76550045aaa,
title = "A continuous-time distributed algorithm for solving linear equations",
abstract = "A continuous-time distributed algorithm is studied for solving linear equations of the form Ax = b with at least one solution. The equation is simultaneously solved by a network of m agents with the assumption that each agent knows only a subset of the rows of the partitioned matrix [A b ], the current estimates of the equation's solution generated by its current neighbors, and nothing more. Neighbor relationships among the agents are described by a piecewise-constant switching directed graph whose vertices correspond to agents and whose arcs depict neighbor relationships. It is shown that for any matrix-vector pair (A, b) for which the equation has a solution and any sequence of repeatedly jointly strongly connected graphs, the algorithm causes all agents' estimates to asymptotically converge to the same solution to Ax = b. The limiting behavior of the algorithm in the case when Ax = b does not have a solution is also studied. It is shown that for any static strongly connected graph, the algorithm causes all agents' estimates to asymptotically converge to different values, and therefore enables the agents to detect the no-solution case distributively.",
author = "Ji Liu and Xudong Chen and Basar, {M Tamer} and Angelia Nedic",
year = "2016",
month = "7",
day = "28",
doi = "10.1109/ACC.2016.7526540",
language = "English (US)",
series = "Proceedings of the American Control Conference",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "5551--5556",
booktitle = "2016 American Control Conference, ACC 2016",
address = "United States",

}

TY - GEN

T1 - A continuous-time distributed algorithm for solving linear equations

AU - Liu, Ji

AU - Chen, Xudong

AU - Basar, M Tamer

AU - Nedic, Angelia

PY - 2016/7/28

Y1 - 2016/7/28

N2 - A continuous-time distributed algorithm is studied for solving linear equations of the form Ax = b with at least one solution. The equation is simultaneously solved by a network of m agents with the assumption that each agent knows only a subset of the rows of the partitioned matrix [A b ], the current estimates of the equation's solution generated by its current neighbors, and nothing more. Neighbor relationships among the agents are described by a piecewise-constant switching directed graph whose vertices correspond to agents and whose arcs depict neighbor relationships. It is shown that for any matrix-vector pair (A, b) for which the equation has a solution and any sequence of repeatedly jointly strongly connected graphs, the algorithm causes all agents' estimates to asymptotically converge to the same solution to Ax = b. The limiting behavior of the algorithm in the case when Ax = b does not have a solution is also studied. It is shown that for any static strongly connected graph, the algorithm causes all agents' estimates to asymptotically converge to different values, and therefore enables the agents to detect the no-solution case distributively.

AB - A continuous-time distributed algorithm is studied for solving linear equations of the form Ax = b with at least one solution. The equation is simultaneously solved by a network of m agents with the assumption that each agent knows only a subset of the rows of the partitioned matrix [A b ], the current estimates of the equation's solution generated by its current neighbors, and nothing more. Neighbor relationships among the agents are described by a piecewise-constant switching directed graph whose vertices correspond to agents and whose arcs depict neighbor relationships. It is shown that for any matrix-vector pair (A, b) for which the equation has a solution and any sequence of repeatedly jointly strongly connected graphs, the algorithm causes all agents' estimates to asymptotically converge to the same solution to Ax = b. The limiting behavior of the algorithm in the case when Ax = b does not have a solution is also studied. It is shown that for any static strongly connected graph, the algorithm causes all agents' estimates to asymptotically converge to different values, and therefore enables the agents to detect the no-solution case distributively.

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

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

U2 - 10.1109/ACC.2016.7526540

DO - 10.1109/ACC.2016.7526540

M3 - Conference contribution

AN - SCOPUS:84992093392

T3 - Proceedings of the American Control Conference

SP - 5551

EP - 5556

BT - 2016 American Control Conference, ACC 2016

PB - Institute of Electrical and Electronics Engineers Inc.

ER -