    • Previous Article
Partial fraction expansion based frequency weighted model reduction for discrete-time systems
• NACO Home
• This Issue
• Next Article
Development of concurrent structural decentralised discrete event system using bisimulation concept
2016, 6(3): 319-328. doi: 10.3934/naco.2016014

## Decentralized gradient algorithm for solution of a linear equation

 1 College of Engineering and Computer Science, The Australian National University, Canberra, Australia 2 School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN, United States 3 Department of Electrical Engineering, Yale University, New Haven, CT, United States 4 Institute for Mathematics, University of Würzburg, Emil-Fischer Straße 40, 97074 Würzburg

Received  July 2015 Revised  September 2016 Published  September 2016

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 $\mathcal G$ with vertex set and edge set $\mathcal V$ and $\mathcal E$ 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 $\mathcal G$ 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.
Citation: Brian D. O. Anderson, Shaoshuai Mou, A. Stephen Morse, Uwe Helmke. Decentralized gradient algorithm for solution of a linear equation. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 319-328. doi: 10.3934/naco.2016014
##### References:
  C. Anderson, Solving linear eqauations on parallel distributed memory architectures by extrapolation,, Technical Report, (1997).   Google Scholar  O. Axelsson, Iterative Solution Methods,, Cambridge University Press, (1996).  doi: 10.1017/CBO9780511624100.  Google Scholar  T. Chang, A. Nedic and A. Scaglione, Distributed constrained optimization by consensus-based primal-dual perturbation method,, \emph{IEEE Transactions on Automatic Control}, 59 (2014), 1524.  doi:  10.1109/TAC.2014.2308612. Google Scholar  F. R. K. Chung, Spectral Graph Theory,, American Mathematical Society, (1997). Google Scholar  J. C. Duchi, A. Agarwal and M. J. Wainwright, Dual averaging for distributed optimization: Convergence analysis and network scaling,, \emph{IEEE Transactions on Automatic Control}, 57 (2012), 592.  doi: 10.1109/TAC.2011.2161027.  Google Scholar  A. Edelman, Large dense numerical linear algebra in 1993: The Parallel Computing Influence,, Technical Report, (1993).   Google Scholar  U. Helmke and J. B. Moore, Optimization and Dynamical Systems,, Communications and Control Engineering, (1994).  doi: 10.1007/978-1-4471-3467-1.  Google Scholar  R. A. Horn and C. R. Johnson, Matrix Analysis,, Cambridge University Press, (1985).  doi: 10.1017/CBO9780511810817.  Google Scholar  D. Jakovetic, J. M. F. Moura and J. Xavier, Fast distributed gradient methods,, \emph{IEEE Transactions on Automatic Control}, 59 (2014), 1131.  doi: 10.1109/TAC.2014.2298712.  Google Scholar  S. Kar, J. M. F. Moura and K. Ramanan, Distributed parameter estimation in sensor networks: Nonlinear observation models and imperfect communication,, \emph{IEEE Transactions on Information Theory}, 58 (2012), 1.  doi: 10.1109/TIT.2012.2191450.  Google Scholar  K. Kurdyka, T. Mostowski and A. Parusinski, Proof of the gradient conjecture of R. Thom,, \emph{Annals of Mathematics}, 152 (2000), 763.  doi: 10.2307/2661354.  Google Scholar  S. Lojasiewicz, Sur les trajectoires du gradient dune fonction analytique,, \emph{Seminari di Geometria, (1984), 115. Google Scholar  D. G. Luenberger, Optimization by Vector Space Methods,, John Wiley and Sons, (1969). Google Scholar  R. Mehmood and J. Crowcroft, Parallel Iterative Solution Method of Large Sparse Linear Equation Systems,, Technical Report, (2005).   Google Scholar  B. Mohar, The Laplacian spectrum of graphs,, \emph{Graph Theory, (1991), 871.  doi: 10.1.1.96.2577.  Google Scholar  S. Mou, A. S. Morse, Z. Lin, L. Wang and D. Fullmer, A distributed algorithm for efficiently solving linear equations and its applications,, \emph{Systems and Control Letters}, (2015).   Google Scholar  S. Mou and A. S. Morse, A fixed-neighbor,distributed algorithm for solving a linear algebraic equation,, \emph{European Control Conference}, (2013), 2269.   Google Scholar  S. Mou, J. Liu and A. S. Morse, A distributed algorithm for solving a linear algebraic equation,, \emph{the 51st Annual Allerton Conference on Communication, (2013), 267. Google Scholar  S. Mou, J. Liu and A. S. Morse, A distributed algorithm for solving a linear algebraic equation,, \emph{IEEE Transactions on Automatic Control}, 60 (2015), 5409.  doi: 10.1109/TAC.2015.2414771.  Google Scholar  A. Nedic, A. Ozdaglar and P. A. Parrilo, Constrained consensus and optimization in multi-agent networks,, \emph{IEEE Transactions on Automatic Control}, 55 (2010), 922.  doi: 10.1109/TAC.2010.2041686.  Google Scholar  A. Nedic and A. Olshevsky, Distributed optimization over time-varying directed graphs,, \emph{IEEE Transactions on Automatic Control}, 60 (2014), 601.  doi: 10.1109/TAC.2014.2364096.  Google Scholar  J. J. Sylvester, On the relation between the minor determinants of linearly equivalent quadratic functions,, \emph{Phylosophical Magazine}, 1 (1851), 295.  doi: 10.1080/14786445108646735. Google Scholar  C. Wang, K. Ren, J. Wang and Q. Wang, Harnessing the cloud for securely outsourcing large-scale systems of linear equations,, \emph{IEEE Transactions on Parallel and Distributed Systems}, 24 (2013), 1172.  doi: 10.1109/TPDS.2012.206. Google Scholar

show all references

##### References:
  C. Anderson, Solving linear eqauations on parallel distributed memory architectures by extrapolation,, Technical Report, (1997).   Google Scholar  O. Axelsson, Iterative Solution Methods,, Cambridge University Press, (1996).  doi: 10.1017/CBO9780511624100.  Google Scholar  T. Chang, A. Nedic and A. Scaglione, Distributed constrained optimization by consensus-based primal-dual perturbation method,, \emph{IEEE Transactions on Automatic Control}, 59 (2014), 1524.  doi:  10.1109/TAC.2014.2308612. Google Scholar  F. R. K. Chung, Spectral Graph Theory,, American Mathematical Society, (1997). Google Scholar  J. C. Duchi, A. Agarwal and M. J. Wainwright, Dual averaging for distributed optimization: Convergence analysis and network scaling,, \emph{IEEE Transactions on Automatic Control}, 57 (2012), 592.  doi: 10.1109/TAC.2011.2161027.  Google Scholar  A. Edelman, Large dense numerical linear algebra in 1993: The Parallel Computing Influence,, Technical Report, (1993).   Google Scholar  U. Helmke and J. B. Moore, Optimization and Dynamical Systems,, Communications and Control Engineering, (1994).  doi: 10.1007/978-1-4471-3467-1.  Google Scholar  R. A. Horn and C. R. Johnson, Matrix Analysis,, Cambridge University Press, (1985).  doi: 10.1017/CBO9780511810817.  Google Scholar  D. Jakovetic, J. M. F. Moura and J. Xavier, Fast distributed gradient methods,, \emph{IEEE Transactions on Automatic Control}, 59 (2014), 1131.  doi: 10.1109/TAC.2014.2298712.  Google Scholar  S. Kar, J. M. F. Moura and K. Ramanan, Distributed parameter estimation in sensor networks: Nonlinear observation models and imperfect communication,, \emph{IEEE Transactions on Information Theory}, 58 (2012), 1.  doi: 10.1109/TIT.2012.2191450.  Google Scholar  K. Kurdyka, T. Mostowski and A. Parusinski, Proof of the gradient conjecture of R. Thom,, \emph{Annals of Mathematics}, 152 (2000), 763.  doi: 10.2307/2661354.  Google Scholar  S. Lojasiewicz, Sur les trajectoires du gradient dune fonction analytique,, \emph{Seminari di Geometria, (1984), 115. Google Scholar  D. G. Luenberger, Optimization by Vector Space Methods,, John Wiley and Sons, (1969). Google Scholar  R. Mehmood and J. Crowcroft, Parallel Iterative Solution Method of Large Sparse Linear Equation Systems,, Technical Report, (2005).   Google Scholar  B. Mohar, The Laplacian spectrum of graphs,, \emph{Graph Theory, (1991), 871.  doi: 10.1.1.96.2577.  Google Scholar  S. Mou, A. S. Morse, Z. Lin, L. Wang and D. Fullmer, A distributed algorithm for efficiently solving linear equations and its applications,, \emph{Systems and Control Letters}, (2015).   Google Scholar  S. Mou and A. S. Morse, A fixed-neighbor,distributed algorithm for solving a linear algebraic equation,, \emph{European Control Conference}, (2013), 2269.   Google Scholar  S. Mou, J. Liu and A. S. Morse, A distributed algorithm for solving a linear algebraic equation,, \emph{the 51st Annual Allerton Conference on Communication, (2013), 267. Google Scholar  S. Mou, J. Liu and A. S. Morse, A distributed algorithm for solving a linear algebraic equation,, \emph{IEEE Transactions on Automatic Control}, 60 (2015), 5409.  doi: 10.1109/TAC.2015.2414771.  Google Scholar  A. Nedic, A. Ozdaglar and P. A. Parrilo, Constrained consensus and optimization in multi-agent networks,, \emph{IEEE Transactions on Automatic Control}, 55 (2010), 922.  doi: 10.1109/TAC.2010.2041686.  Google Scholar  A. Nedic and A. Olshevsky, Distributed optimization over time-varying directed graphs,, \emph{IEEE Transactions on Automatic Control}, 60 (2014), 601.  doi: 10.1109/TAC.2014.2364096.  Google Scholar  J. J. Sylvester, On the relation between the minor determinants of linearly equivalent quadratic functions,, \emph{Phylosophical Magazine}, 1 (1851), 295.  doi: 10.1080/14786445108646735. Google Scholar  C. Wang, K. Ren, J. Wang and Q. Wang, Harnessing the cloud for securely outsourcing large-scale systems of linear equations,, \emph{IEEE Transactions on Parallel and Distributed Systems}, 24 (2013), 1172.  doi: 10.1109/TPDS.2012.206. Google Scholar
  Leonid Berezansky, Elena Braverman. Stability of linear differential equations with a distributed delay. Communications on Pure & Applied Analysis, 2011, 10 (5) : 1361-1375. doi: 10.3934/cpaa.2011.10.1361  Harry L. Johnson, David Russell. Transfer function approach to output specification in certain linear distributed parameter systems. Conference Publications, 2003, 2003 (Special) : 449-458. doi: 10.3934/proc.2003.2003.449  Samuel Bernard, Fabien Crauste. Optimal linear stability condition for scalar differential equations with distributed delay. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 1855-1876. doi: 10.3934/dcdsb.2015.20.1855  Samuel Bernard, Jacques Bélair, Michael C Mackey. Sufficient conditions for stability of linear differential equations with distributed delay. Discrete & Continuous Dynamical Systems - B, 2001, 1 (2) : 233-256. doi: 10.3934/dcdsb.2001.1.233  Mahesh G. Nerurkar. Spectral and stability questions concerning evolution of non-autonomous linear systems. Conference Publications, 2001, 2001 (Special) : 270-275. doi: 10.3934/proc.2001.2001.270  Boris Buffoni, Laurent Landry. Multiplicity of homoclinic orbits in quasi-linear autonomous Lagrangian systems. Discrete & Continuous Dynamical Systems - A, 2010, 27 (1) : 75-116. doi: 10.3934/dcds.2010.27.75  Stefano Maset. Conditioning and relative error propagation in linear autonomous ordinary differential equations. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2879-2909. doi: 10.3934/dcdsb.2018165  Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195  Chuong Van Nguyen, Phuong Huu Hoang, Hyo-Sung Ahn. Distributed optimization algorithms for game of power generation in smart grid. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 327-348. doi: 10.3934/naco.2019022  Xuan Wang, Shaoshuai Mou, Shreyas Sundaram. A resilient convex combination for consensus-based distributed algorithms. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 269-281. doi: 10.3934/naco.2019018  Jehad O. Alzabut. A necessary and sufficient condition for the existence of periodic solutions of linear impulsive differential equations with distributed delay. Conference Publications, 2007, 2007 (Special) : 35-43. doi: 10.3934/proc.2007.2007.35  Lu Yang, Meihua Yang, Peter E. Kloeden. Pullback attractors for non-autonomous quasi-linear parabolic equations with dynamical boundary conditions. Discrete & Continuous Dynamical Systems - B, 2012, 17 (7) : 2635-2651. doi: 10.3934/dcdsb.2012.17.2635  Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049  Luisa Arlotti, Bertrand Lods, Mustapha Mokhtar-Kharroubi. Non-autonomous Honesty theory in abstract state spaces with applications to linear kinetic equations. Communications on Pure & Applied Analysis, 2014, 13 (2) : 729-771. doi: 10.3934/cpaa.2014.13.729  Mustapha Mokhtar-Kharroubi. On permanent regimes for non-autonomous linear evolution equations in Banach spaces with applications to transport theory. Kinetic & Related Models, 2010, 3 (3) : 473-499. doi: 10.3934/krm.2010.3.473  Larbi Berrahmoune. Null controllability for distributed systems with time-varying constraint and applications to parabolic-like equations. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2020062  Ugur G. Abdulla. On the optimal control of the free boundary problems for the second order parabolic equations. II. Convergence of the method of finite differences. Inverse Problems & Imaging, 2016, 10 (4) : 869-898. doi: 10.3934/ipi.2016025  Jean Ginibre, Giorgio Velo. Modified wave operators without loss of regularity for some long range Hartree equations. II. Communications on Pure & Applied Analysis, 2015, 14 (4) : 1357-1376. doi: 10.3934/cpaa.2015.14.1357  Mohamed Assellaou, Olivier Bokanowski, Hasnaa Zidani. Error estimates for second order Hamilton-Jacobi-Bellman equations. Approximation of probabilistic reachable sets. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 3933-3964. doi: 10.3934/dcds.2015.35.3933  Shitao Liu, Roberto Triggiani. Determining damping and potential coefficients of an inverse problem for a system of two coupled hyperbolic equations. Part I: Global uniqueness. Conference Publications, 2011, 2011 (Special) : 1001-1014. doi: 10.3934/proc.2011.2011.1001

Impact Factor: