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)

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

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)