Network Flows That Solve Linear Equations

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 h T i of the matrix H and the corresponding entry z i in the vector z. The first "consensus + projection" flow under investigation consists of two term...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on automatic control 2017-06, Vol.62 (6), p.2659-2674
Main Authors: Guodong Shi, Anderson, Brian D. O., Helmke, Uwe
Format: Article
Language:English
Subjects:
Algebra
Australia
Computer networks
Convergence
distributed computation
Exact solutions
Feedback
Graph theory
Graphs
Illustrations
Least squares method
linear algebraic equations
Linear equations
Mathematical model
Matrices (mathematics)
Matrix methods
Networks
Optimization
Projection
Solvers
State feedback
Subspaces
Switches
Switching
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 h T i of the matrix H and the corresponding entry z i 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 h i and z i . 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.
ISSN:0018-9286
1558-2523
DOI:10.1109/TAC.2016.2612819