# American Institute of Mathematical Sciences

• Previous Article
Development of concurrent structural decentralised discrete event system using bisimulation concept
• NACO Home
• This Issue
• Next Article
Partial fraction expansion based frequency weighted model reduction for discrete-time systems
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:
 [1] C. Anderson, Solving linear eqauations on parallel distributed memory architectures by extrapolation,, Technical Report, (1997). [2] O. Axelsson, Iterative Solution Methods,, Cambridge University Press, (1996). doi: 10.1017/CBO9780511624100. [3] 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. [4] F. R. K. Chung, Spectral Graph Theory,, American Mathematical Society, (1997). [5] 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. [6] A. Edelman, Large dense numerical linear algebra in 1993: The Parallel Computing Influence,, Technical Report, (1993). [7] U. Helmke and J. B. Moore, Optimization and Dynamical Systems,, Communications and Control Engineering, (1994). doi: 10.1007/978-1-4471-3467-1. [8] R. A. Horn and C. R. Johnson, Matrix Analysis,, Cambridge University Press, (1985). doi: 10.1017/CBO9780511810817. [9] 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. [10] 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. [11] 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. [12] S. Lojasiewicz, Sur les trajectoires du gradient dune fonction analytique,, \emph{Seminari di Geometria, (1984), 115. [13] D. G. Luenberger, Optimization by Vector Space Methods,, John Wiley and Sons, (1969). [14] R. Mehmood and J. Crowcroft, Parallel Iterative Solution Method of Large Sparse Linear Equation Systems,, Technical Report, (2005). [15] B. Mohar, The Laplacian spectrum of graphs,, \emph{Graph Theory, (1991), 871. doi: 10.1.1.96.2577. [16] 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). [17] S. Mou and A. S. Morse, A fixed-neighbor,distributed algorithm for solving a linear algebraic equation,, \emph{European Control Conference}, (2013), 2269. [18] 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. [19] 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. [20] 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. [21] 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. [22] 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. [23] 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.

show all references

##### References:
 [1] C. Anderson, Solving linear eqauations on parallel distributed memory architectures by extrapolation,, Technical Report, (1997). [2] O. Axelsson, Iterative Solution Methods,, Cambridge University Press, (1996). doi: 10.1017/CBO9780511624100. [3] 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. [4] F. R. K. Chung, Spectral Graph Theory,, American Mathematical Society, (1997). [5] 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. [6] A. Edelman, Large dense numerical linear algebra in 1993: The Parallel Computing Influence,, Technical Report, (1993). [7] U. Helmke and J. B. Moore, Optimization and Dynamical Systems,, Communications and Control Engineering, (1994). doi: 10.1007/978-1-4471-3467-1. [8] R. A. Horn and C. R. Johnson, Matrix Analysis,, Cambridge University Press, (1985). doi: 10.1017/CBO9780511810817. [9] 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. [10] 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. [11] 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. [12] S. Lojasiewicz, Sur les trajectoires du gradient dune fonction analytique,, \emph{Seminari di Geometria, (1984), 115. [13] D. G. Luenberger, Optimization by Vector Space Methods,, John Wiley and Sons, (1969). [14] R. Mehmood and J. Crowcroft, Parallel Iterative Solution Method of Large Sparse Linear Equation Systems,, Technical Report, (2005). [15] B. Mohar, The Laplacian spectrum of graphs,, \emph{Graph Theory, (1991), 871. doi: 10.1.1.96.2577. [16] 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). [17] S. Mou and A. S. Morse, A fixed-neighbor,distributed algorithm for solving a linear algebraic equation,, \emph{European Control Conference}, (2013), 2269. [18] 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. [19] 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. [20] 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. [21] 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. [22] 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. [23] 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.
 [1] 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 [2] 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 [3] 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 [4] 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 [5] 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 [6] 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 [7] 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 [8] 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 [9] 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 [10] 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 [11] 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 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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 [19] 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 [20] Viktor Levandovskyy, Gerhard Pfister, Valery G. Romanovski. Evaluating cyclicity of cubic systems with algorithms of computational algebra. Communications on Pure & Applied Analysis, 2012, 11 (5) : 2023-2035. doi: 10.3934/cpaa.2012.11.2023

Impact Factor: