A Distributed Algorithm for Solving a Linear Algebraic Equation

DOI10.1109/TAC.2015.2414771MaRDI QIDQ2982503zbMATH OpenWikidataFDO

Authors Ji Liu, Shaoshuai Mou, A. Stephen Morse

Publication date 16 May 2017

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.00808

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05) Distributed algorithms (68W15)

Abstract: A distributed algorithm is described for solving a linear algebraic equation of the form $Ax=b$ assuming the equation has at least one solution. The equation is simultaneously solved by $m$ agents assuming each agent knows only a subset of the rows of the partitioned matrix $(A,b)$, the current estimates of the equation's solution generated by its neighbors, and nothing more. Each agent recursively updates its estimate by utilizing the current estimates generated by each of its neighbors. Neighbor relations are characterized by a time-dependent directed graph $mathbbN(t)$ whose vertices correspond to agents and whose arcs depict neighbor relations. It is shown that for any matrix $A$ for which the equation has a solution and any sequence of "repeatedly jointly strongly connected graphs" $mathbbN(t)$, $t=1,2,ldots$, the algorithm causes all agents' estimates to converge exponentially fast to the same solution to $Ax=b$. It is also shown that the neighbor graph sequence must actually be repeatedly jointly strongly connected if exponential convergence is to be assured. A worst case convergence rate bound is derived for the case when $Ax=b$ has a unique solution. It is demonstrated that with minor modification, the algorithm can track the solution to $Ax=b$, even if $A$ and $b$ are changing with time, provided the rates of change of $A$ and $b$ are sufficiently small. It is also shown that in the absence of communication delays, exponential convergence to a solution occurs even if the times at which each agent updates its estimates are not synchronized with the update times of its neighbors. A modification of the algorithm is outlined which enables it to obtain a least squares solution to $Ax=b$ in a distributed manner, even if $Ax=b$ does not have a solution.

Cited in

(50)

• Exponential convergence of a distributed algorithm for solving linear algebraic equations
• An Arrow-Hurwicz-Uzawa type flow as least squares solver for network linear equations
• Consensus control for linear systems with optimal energy cost
• Distributed networked learning with correlated data
• Scalable distributed least square algorithms for large-scale linear equations via an optimization approach
• A hybrid observer for estimating the state of a distributed linear system
• Distributed solver for linear matrix inequalities: an optimization perspective
• Asymptotic convergence of a distributed weighted least squares algorithm for networked systems with vector node variables
• Continuous distributed algorithms for solving linear equations in finite time
• Distributed least squares solver for network linear equations
• Distributed weighted least-squares estimation for networked systems with edge measurements
• Network flows that solve least squares for linear equations
• Distributed algorithms for computing a fixed point of multi-agent nonexpansive operators
• A distributed algorithm for solving mixed equilibrium problems
• Convergence rate on periodic gossiping
• Resilient consensus of multi-agent systems against malicious data injections
• Distributed inverse optimal control
• Distributed consensus-based solver for semi-definite programming: an optimization viewpoint
• Distributed and communication-efficient solutions to linear equations with special sparse structure
• A distributed algorithm for efficiently solving linear equations and its applications (special issue JCW)
• Reprint of ``A distributed algorithm for efficiently solving linear equations and its applications (Special issue JCW)
• Decentralized gradient algorithm for solution of a linear equation
• An algorithm for coordination of solutions in a distributed system of interdependent problems with linear models
• Distributed continuous-time algorithms for nonsmooth extended monotropic optimization problems
• scientific article; zbMATH DE number 7042406 (Why is no real title available?)
• Design of heterogeneous multi-agent system for distributed computation
• Distributed algorithms with finite data rates that solve linear equations
• Topology design for group consensus in directed multi-agent systems.
• A Distributed Algorithm for Least Squares Solutions
• Asynchronous algorithms for computing equilibrium prices in a capital asset pricing model
• Distributed solving linear algebraic equations with switched fractional order dynamics
• Split-spectrum based distributed state estimation for linear systems
• Distributed optimization under edge agreements: a continuous-time algorithm
• Reaching a consensus with limited information
• Fully distributed adaptive control for output consensus of uncertain discrete-time linear multi-agent systems
• Lyapunov based stochastic stability of a quantum decision system for human-machine interaction
• Alternating projection method for intersection of convex sets, multi-agent consensus algorithms, and averaging inequalities
• Distributed algorithms of solving linear matrix equations via double-layered networks
• Distributed convex optimization based on ADMM and belief propagation methods
• Stability analysis and controller design for consensus in discrete-time networks with heterogeneous agent dynamics
• An event-based distributed least square linear equation solver employing network flow
• Distributed algorithm for solving variational inequalities over time-varying unbalanced digraphs
• Distributed algorithms for solving linear algebraic equations: an optimal control perspective
• A data-driven distributed fault diagnosis scheme for large-scale systems based on correlation analysis
• Consensus-based distributed solution algorithms for linear equations with block Toeplitz structures
• Distributed optimization and scaling design for solving Sylvester equations
• Distributedly solving network linear equations with event-based algorithms
• Distributed optimisation design for solving the Stein equation with constraints
• Solving linear algebraic equations with limited computational power and network bandwidth
• Discrete-time distributed algorithms for solving linear equations via layered coordination

This page was built for publication: A Distributed Algorithm for Solving a Linear Algebraic Equation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2982503)