Network Flows That Solve Linear Equations

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.