Network Flows That Solve Linear Equations
Date
2017
Authors
Shi, Guodong
Anderson, Brian
Helmke, Uwe
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Electrical and Electronics Engineers (IEEE Inc)
Abstract
We study distributed network flows as solvers in continuous time for the linear algebraic equation z=Hy .Each node i has access to a row hTi of the matrix H and the corresponding entry zi in the vector z. The first “consensus + projection” flow under investigation consists of two terms, one from standard consensus dynamics and the other contributing to projection onto each affine subspace specified by the hi and zi. The second “projection consensus” flow on the other hand simply replaces the relative state feedback in consensus dynamics with projected relative state feedback. Without dwell-time assumption on switching graphs, we prove that all node states converge to a common solution of the linear algebraic equation, if there is any. The convergence is global for the “consensus + projection” flow while local for the “projection consensus” flow in the sense that the initial values must lie on the affine subspaces. If the linear equation has no exact solutions, we show that the node states can converge to a ball around the least-squares solution whose radius can be made arbitrarily small through selecting a sufficiently large gain for the “consensus + projection” flow for a fixed bidirectional graph. Semi-global convergence to approximate least-squares solutions is also demonstrated for switching balanced directed graphs under suitable conditions. It is also shown that the “projection consensus” flow drives the average of the node states to the least-squares solution with a complete graph. Numerical examples are provided as illustrations of the established results.
Description
Keywords
Networks, distributed computation, linear algebraic equations
Citation
Collections
Source
IEEE Transactions on Automatic Control
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
Restricted until
2099-12-31
Downloads
File
Description