Stability of a distributed algorithm for solving linear algebraic equations

Ji Liu; A. Stephen Morse; Angelia Nedic; Tamer Basar

doi:10.1109/CDC.2014.7039966

Stability of a distributed algorithm for solving linear algebraic equations

Ji Liu
, A. Stephen Morse
, Angelia Nedic
, Tamer Basar

Electrical Engineering

Yale University
University of Illinois at Urbana-Champaign

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

12 Scopus citations

Abstract

In [1], given a matrix A and a vector b, a distributed algorithm was proposed for solving linear algebraic equations of the form Ax = b when there is at least one solution. The equation is simultaneously solved by a group of autonomous agents whose neighbor relations are characterized by a time-dependent directed graph. The main contribution of this paper is to provide necessary and sufficient conditions for exponential convergence of the algorithm under the most general assumption. These conditions utilize a new notion of graph connectivity which is less restrictive than strong connectivity.

Original language	English
Title of host publication	53rd IEEE Conference on Decision and Control,CDC 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3707-3712
Number of pages	6
Edition	February
ISBN (Electronic)	9781479977468
DOIs	https://doi.org/10.1109/CDC.2014.7039966
State	Published - 2014
Event	2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 - Los Angeles, United States Duration: Dec 15 2014 → Dec 17 2014

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
Number	February
Volume	2015-February
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
Country/Territory	United States
City	Los Angeles
Period	12/15/14 → 12/17/14

Access to Document

10.1109/CDC.2014.7039966

Cite this

Liu, J., Morse, A. S., Nedic, A., & Basar, T. (2014). Stability of a distributed algorithm for solving linear algebraic equations. In 53rd IEEE Conference on Decision and Control,CDC 2014 (February ed., pp. 3707-3712). Article 7039966 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2015-February, No. February). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2014.7039966

@inproceedings{0b3ff9b437bc47148e97115442165a6b,

title = "Stability of a distributed algorithm for solving linear algebraic equations",

abstract = "In [1], given a matrix A and a vector b, a distributed algorithm was proposed for solving linear algebraic equations of the form Ax = b when there is at least one solution. The equation is simultaneously solved by a group of autonomous agents whose neighbor relations are characterized by a time-dependent directed graph. The main contribution of this paper is to provide necessary and sufficient conditions for exponential convergence of the algorithm under the most general assumption. These conditions utilize a new notion of graph connectivity which is less restrictive than strong connectivity.",

author = "Ji Liu and Morse, \{A. Stephen\} and Angelia Nedic and Tamer Basar",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 ; Conference date: 15-12-2014 Through 17-12-2014",

year = "2014",

doi = "10.1109/CDC.2014.7039966",

language = "English",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "February",

pages = "3707--3712",

booktitle = "53rd IEEE Conference on Decision and Control,CDC 2014",

edition = "February",

}

Liu, J, Morse, AS, Nedic, A & Basar, T 2014, Stability of a distributed algorithm for solving linear algebraic equations. in 53rd IEEE Conference on Decision and Control,CDC 2014. February edn, 7039966, Proceedings of the IEEE Conference on Decision and Control, no. February, vol. 2015-February, Institute of Electrical and Electronics Engineers Inc., pp. 3707-3712, 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014, Los Angeles, United States, 12/15/14. https://doi.org/10.1109/CDC.2014.7039966

Stability of a distributed algorithm for solving linear algebraic equations. / Liu, Ji; Morse, A. Stephen; Nedic, Angelia et al.
53rd IEEE Conference on Decision and Control,CDC 2014. February. ed. Institute of Electrical and Electronics Engineers Inc., 2014. p. 3707-3712 7039966 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2015-February, No. February).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Stability of a distributed algorithm for solving linear algebraic equations

AU - Liu, Ji

AU - Morse, A. Stephen

AU - Nedic, Angelia

AU - Basar, Tamer

PY - 2014

Y1 - 2014

N2 - In [1], given a matrix A and a vector b, a distributed algorithm was proposed for solving linear algebraic equations of the form Ax = b when there is at least one solution. The equation is simultaneously solved by a group of autonomous agents whose neighbor relations are characterized by a time-dependent directed graph. The main contribution of this paper is to provide necessary and sufficient conditions for exponential convergence of the algorithm under the most general assumption. These conditions utilize a new notion of graph connectivity which is less restrictive than strong connectivity.

AB - In [1], given a matrix A and a vector b, a distributed algorithm was proposed for solving linear algebraic equations of the form Ax = b when there is at least one solution. The equation is simultaneously solved by a group of autonomous agents whose neighbor relations are characterized by a time-dependent directed graph. The main contribution of this paper is to provide necessary and sufficient conditions for exponential convergence of the algorithm under the most general assumption. These conditions utilize a new notion of graph connectivity which is less restrictive than strong connectivity.

UR - https://www.scopus.com/pages/publications/84988289973

U2 - 10.1109/CDC.2014.7039966

DO - 10.1109/CDC.2014.7039966

M3 - Conference contribution

AN - SCOPUS:84988289973

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 3707

EP - 3712

BT - 53rd IEEE Conference on Decision and Control,CDC 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014

Y2 - 15 December 2014 through 17 December 2014

ER -

Stability of a distributed algorithm for solving linear algebraic equations

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this