Stability of a distributed algorithm for solving linear algebraic equations

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

Research output: Contribution to journalConference article

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 languageEnglish (US)
Article number7039966
Pages (from-to)3707-3712
Number of pages6
JournalProceedings of the IEEE Conference on Decision and Control
Volume2015-February
Issue numberFebruary
DOIs
StatePublished - Jan 1 2014
Event2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 - Los Angeles, United States
Duration: Dec 15 2014Dec 17 2014

Fingerprint

Strong Connectivity
Graph Connectivity
Autonomous agents
Exponential Convergence
Autonomous Agents
Directed graphs
Distributed Algorithms
Linear equations
Parallel algorithms
Algebraic Equation
Directed Graph
Linear equation
Necessary Conditions
Sufficient Conditions
Form

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Cite this

Stability of a distributed algorithm for solving linear algebraic equations. / Liu, Ji; Morse, A. Stephen; Nedic, Angelia; Basar, Tamer.

In: Proceedings of the IEEE Conference on Decision and Control, Vol. 2015-February, No. February, 7039966, 01.01.2014, p. 3707-3712.

Research output: Contribution to journalConference article

Liu, Ji ; Morse, A. Stephen ; Nedic, Angelia ; Basar, Tamer. / Stability of a distributed algorithm for solving linear algebraic equations. In: Proceedings of the IEEE Conference on Decision and Control. 2014 ; Vol. 2015-February, No. February. pp. 3707-3712.
@article{2c914aa093374ad4802728d13664ba2a,
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",
year = "2014",
month = "1",
day = "1",
doi = "10.1109/CDC.2014.7039966",
language = "English (US)",
volume = "2015-February",
pages = "3707--3712",
journal = "Proceedings of the IEEE Conference on Decision and Control",
issn = "0191-2216",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "February",

}

TY - JOUR

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/1/1

Y1 - 2014/1/1

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 - http://www.scopus.com/inward/record.url?scp=84988289973&partnerID=8YFLogxK

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

U2 - 10.1109/CDC.2014.7039966

DO - 10.1109/CDC.2014.7039966

M3 - Conference article

AN - SCOPUS:84988289973

VL - 2015-February

SP - 3707

EP - 3712

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

SN - 0191-2216

IS - February

M1 - 7039966

ER -