Decentralized gradient algorithm for solution of a linear equation

DOI10.3934/NACO.2016014MaRDI QIDQ330302zbMATH OpenOpenAlexFDO

Authors Shaoshuai Mou, Brian D. O. Anderson, A. Stephen Morse, Uwe Helmke

Publication date 25 October 2016

Published in Numerical Algebra, Control and Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

distributed algorithmslinear equationsautonomous systems

Mathematics Subject Classification ID

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

Abstract: The paper develops a technique for solving a linear equation $Ax=b$ with a square and nonsingular matrix $A$, using a decentralized gradient algorithm. In the language of control theory, there are $n$ agents, each storing at time $t$ an $n$-vector, call it $x_i(t)$, and a graphical structure associating with each agent a vertex of a fixed, undirected and connected but otherwise arbitrary graph $mathcalG$ with vertex set and edge set $mathcalV$ and $mathcalE$ respectively. We provide differential equation update laws for the $x_i$ with the property that each $x_i$ converges to the solution of the linear equation exponentially fast. The equation for $x_i$ includes additive terms weighting those $x_j$ for which vertices in $mathcalG$ corresponding to the $i$-th and $j$-th agents are adjacent. The results are extended to the case where $A$ is not square but has full row rank, and bounds are given on the convergence rate.

Recommendations

• A distributed algorithm for efficiently solving linear equations and its applications (special issue JCW)
• Exponential convergence of a distributed algorithm for solving linear algebraic equations
• Continuous distributed algorithms for solving linear equations in finite time
• Computation of linear algebraic equations with solvability verification over multi-agent networks.
• Distributed and communication-efficient solutions to linear equations with special sparse structure

Cites work

• scientific article; zbMATH DE number 3980094 (Why is no real title available?)
• scientific article; zbMATH DE number 1324524 (Why is no real title available?)
• scientific article; zbMATH DE number 867649 (Why is no real title available?)
• scientific article; zbMATH DE number 3281211 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A Distributed Algorithm for Solving a Linear Algebraic Equation
• Constrained Consensus and Optimization in Multi-Agent Networks
• Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
• Distributed Optimization Over Time-Varying Directed Graphs
• Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• Fast Distributed Gradient Methods
• Iterative Solution Methods
• Matrix Analysis
• Proof of the gradient conjecture of R. Thom.

Cited in

(19)

• Distributed algorithms with finite data rates that solve linear equations
• Computation of open-loop inputs for uniformly ensemble controllable systems
• A distributed algorithm for efficiently solving linear equations and its applications (special issue JCW)
• Distributed optimisation approach to least-squares solution of Sylvester equations
• Computation of linear algebraic equations with solvability verification over multi-agent networks.
• Distributed fixed point method for solving systems of linear algebraic equations
• Distributed continuous-time algorithms for nonsmooth extended monotropic optimization problems
• Design of heterogeneous multi-agent system for distributed computation
• Designing linear distributed algorithms with memory for fast convergence
• Continuous distributed algorithms for solving linear equations in finite time
• Distributed least squares solver for network linear equations
• Exponential convergence of a distributed algorithm for solving linear algebraic equations
• Reprint of ``A distributed algorithm for efficiently solving linear equations and its applications (Special issue JCW)
• An event-based distributed least square linear equation solver employing network flow
• Network flows that solve least squares for linear equations
• Distributed algorithms of solving linear matrix equations via double-layered networks
• 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
• On the gradient method for solving multi-agent systems

This page was built for publication: Decentralized gradient algorithm for solution of a linear equation

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