Decentralized gradient algorithm for solution of a linear equation

DOI10.3934/NACO.2016014zbMATH Open1346.93159arXiv1509.04538OpenAlexW2964255343MaRDI QIDQ330302FDOQ330302

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)

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.

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

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

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)

Cites Work

• Matrix Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constrained Consensus and Optimization in Multi-Agent Networks
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• Iterative Solution Methods
• Title not available (Why is that?)
• A Distributed Algorithm for Solving a Linear Algebraic Equation
• Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
• Fast Distributed Gradient Methods
• Proof of the gradient conjecture of R. Thom.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication
• Distributed Optimization Over Time-Varying Directed Graphs

Cited In (18)

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

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)