Exponential convergence of a distributed algorithm for solving linear algebraic equations

DOI10.1016/J.AUTOMATICA.2017.05.004MaRDI QIDQ1679072zbMATH OpenOpenAlexWikidataFDO

Authors Ji Liu, A. Stephen Morse, Angelia Nedić, Tamer Başar

Publication date 8 November 2017

Published in Automatica (Search for Journal in Brave)

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

zbMATH Keywords

distributed algorithmexponential convergencesolving linear algebraic equations

Mathematics Subject Classification ID

Agent technology and artificial intelligence (68T42) Decentralized systems (93A14) Linear systems in control theory (93C05)

Abstract: In a recent paper, a distributed algorithm was proposed for solving linear algebraic equations of the form $Ax=b$ assuming that the equation has at least one solution. The equation is presumed to be solved by $m$ agents assuming that each agent knows a subset of the rows of the matrix $[A;b]$, the current estimates of the equation's solution generated by each of its neighbors, and nothing more. Neighbor relationships are represented by a time-dependent directed graph $N(t)$ whose vertices correspond to agents and whose arcs characterize neighbor relationships. Sufficient conditions on $N(t)$ were derived under which the algorithm can cause all agents' estimates to converge exponentially fast to the same solution to $Ax=b$. These conditions were also shown to be necessary for exponential convergence, provided the data about $[A;b]$ available to the agents is "non-redundant". The aim of this paper is to relax this "non-redundant" assumption. This is accomplished by establishing exponential convergence under conditions which are the weakest possible for the problem at hand; the conditions are based on a new notion of graph connectivity. An improved bound on the convergence rate is also derived.

Recommendations

• A Distributed Algorithm for Solving a Linear Algebraic Equation
• Continuous distributed algorithms for solving linear equations in finite time
• scientific article; zbMATH DE number 7042406
• Distributed fixed point method for solving systems of linear algebraic equations
• Asynchronous Distributed Algorithms for Solving Linear Algebraic Equations
• Distributed algorithms with finite data rates that solve linear equations
• A Distributed Algorithm for Solving Linear Algebraic Equations Over Random Networks
• A distributed algorithm for efficiently solving linear equations and its applications (special issue JCW)
• Distributed Algorithm for Solving Convex Inequalities
• A Randomized Solver for Linear Systems with Exponential Convergence

Cites work

• A Distributed Algorithm for Solving a Linear Algebraic Equation
• Asynchronous Distributed ADMM for Large-Scale Optimization—Part I: Algorithm and<?Pub _newline ?>Convergence Analysis
• Consensus and Cooperation in Networked Multi-Agent Systems
• Consensus-based distributed sensor calibration and least-square parameter identification in WSNs
• Constrained Consensus and Optimization in Multi-Agent Networks
• Constrained Consensus in Unbalanced Networks With Communication Delays
• Convexity and characterization of optimal policies in a dynamic routing problem
• Coordination of groups of mobile autonomous agents using nearest neighbor rules
• Decentralized gradient algorithm for solution of a linear equation
• Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
• Distributed Continuous-Time Convex Optimization on Weight-Balanced Digraphs
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Distributed Optimization Over Time-Varying Directed Graphs
• Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication
• Distributed Subgradient Methods for Multi-Agent Optimization
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• Error Scaling Laws for Linear Optimal Estimation From Relative Measurements
• Estimation From Relative Measurements: Electrical Analogy and Large Graphs
• EXTRA: an exact first-order algorithm for decentralized consensus optimization
• Fast Distributed Gradient Methods
• scientific article; zbMATH DE number 1001723 (Why is no real title available?)
• Newton-Raphson Consensus for Distributed Convex Optimization
• On Distributed Averaging Algorithms and Quantization Effects
• Reaching a Consensus in a Dynamically Changing Environment: A Graphical Approach
• Stability of multiagent systems with time-dependent communication links

Cited in

(22)

• An Arrow-Hurwicz-Uzawa type flow as least squares solver for network linear equations
• 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 least squares solver for network linear equations
• Distributed fixed point method for solving systems of linear algebraic equations
• A distributed algorithm for efficiently solving linear equations and its applications (special issue JCW)
• Designing linear distributed algorithms with memory for fast convergence
• Decentralized gradient algorithm for solution of a linear equation
• scientific article; zbMATH DE number 7042406 (Why is no real title available?)
• Computation of linear algebraic equations with solvability verification over multi-agent networks.
• Distributed algorithms with finite data rates that solve linear equations
• Lyapunov based stochastic stability of a quantum decision system for human-machine interaction
• Distributed algorithms of solving linear matrix equations via double-layered networks
• Distributed convex optimization based on ADMM and belief propagation methods
• Control-theoretic methods for solving linear algebraic equations: a continuous-time perspective
• Distributed algorithms for solving linear algebraic equations: an optimal control perspective
• Consensus-based distributed solution algorithms for linear equations with block Toeplitz structures
• Distributed optimization and scaling design for solving Sylvester equations
• Distributed inexact Newton method with adaptive step sizes
• 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: Exponential convergence of a distributed algorithm for solving linear algebraic equations

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