American Institute of Mathematical Sciences

Advanced
  • 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

Brian D. O. Anderson 1, , Shaoshuai Mou 2, , A. Stephen Morse 3, and  Uwe Helmke 4,

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.
Keywords: Autonomous systems; distributed algorithms; linear equations..
Mathematics Subject Classification: Primary: 68Q85 ; Secondary: 11D0.
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).   Google Scholar

[2]

O. Axelsson, Iterative Solution Methods,, Cambridge University Press, (1996).  doi: 10.1017/CBO9780511624100.  Google Scholar

[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.  Google Scholar

[4]

F. R. K. Chung, Spectral Graph Theory,, American Mathematical Society, (1997).   Google Scholar

[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.  Google Scholar

[6]

A. Edelman, Large dense numerical linear algebra in 1993: The Parallel Computing Influence,, Technical Report, (1993).   Google Scholar

[7]

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

[8]

R. A. Horn and C. R. Johnson, Matrix Analysis,, Cambridge University Press, (1985).  doi: 10.1017/CBO9780511810817.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

S. Lojasiewicz, Sur les trajectoires du gradient dune fonction analytique,, \emph{Seminari di Geometria, (1984), 115.   Google Scholar

[13]

D. G. Luenberger, Optimization by Vector Space Methods,, John Wiley and Sons, (1969).   Google Scholar

[14]

R. Mehmood and J. Crowcroft, Parallel Iterative Solution Method of Large Sparse Linear Equation Systems,, Technical Report, (2005).   Google Scholar

[15]

B. Mohar, The Laplacian spectrum of graphs,, \emph{Graph Theory, (1991), 871.  doi: 10.1.1.96.2577.  Google Scholar

[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).   Google Scholar

[17]

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

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

C. Anderson, Solving linear eqauations on parallel distributed memory architectures by extrapolation,, Technical Report, (1997).   Google Scholar

[2]

O. Axelsson, Iterative Solution Methods,, Cambridge University Press, (1996).  doi: 10.1017/CBO9780511624100.  Google Scholar

[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.  Google Scholar

[4]

F. R. K. Chung, Spectral Graph Theory,, American Mathematical Society, (1997).   Google Scholar

[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.  Google Scholar

[6]

A. Edelman, Large dense numerical linear algebra in 1993: The Parallel Computing Influence,, Technical Report, (1993).   Google Scholar

[7]

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

[8]

R. A. Horn and C. R. Johnson, Matrix Analysis,, Cambridge University Press, (1985).  doi: 10.1017/CBO9780511810817.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

S. Lojasiewicz, Sur les trajectoires du gradient dune fonction analytique,, \emph{Seminari di Geometria, (1984), 115.   Google Scholar

[13]

D. G. Luenberger, Optimization by Vector Space Methods,, John Wiley and Sons, (1969).   Google Scholar

[14]

R. Mehmood and J. Crowcroft, Parallel Iterative Solution Method of Large Sparse Linear Equation Systems,, Technical Report, (2005).   Google Scholar

[15]

B. Mohar, The Laplacian spectrum of graphs,, \emph{Graph Theory, (1991), 871.  doi: 10.1.1.96.2577.  Google Scholar

[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).   Google Scholar

[17]

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

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055
[2]

Jonathan J. Wylie, Robert M. Miura, Huaxiong Huang. Systems of coupled diffusion equations with degenerate nonlinear source terms: Linear stability and traveling waves. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 561-569. doi: 10.3934/dcds.2009.23.561
[3]

Dominique Chapelle, Philippe Moireau, Patrick Le Tallec. Robust filtering for joint state-parameter estimation in distributed mechanical systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 65-84. doi: 10.3934/dcds.2009.23.65
[4]

Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021002
[5]

Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080
[6]

Pengyu Chen. Non-autonomous stochastic evolution equations with nonlinear noise and nonlocal conditions governed by noncompact evolution families. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020383
[7]

Lin Shi, Xuemin Wang, Dingshi Li. Limiting behavior of non-autonomous stochastic reaction-diffusion equations with colored noise on unbounded thin domains. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5367-5386. doi: 10.3934/cpaa.2020242
[8]

Pengyu Chen, Yongxiang Li, Xuping Zhang. Cauchy problem for stochastic non-autonomous evolution equations governed by noncompact evolution families. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1531-1547. doi: 10.3934/dcdsb.2020171
[9]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444
[10]

Kaixuan Zhu, Ji Li, Yongqin Xie, Mingji Zhang. Dynamics of non-autonomous fractional reaction-diffusion equations on $ \mathbb{R}^{N} $ driven by multiplicative noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020376
[11]

Wenqiang Zhao, Yijin Zhang. High-order Wong-Zakai approximations for non-autonomous stochastic $ p $-Laplacian equations on $ \mathbb{R}^N $. Communications on Pure & Applied Analysis, 2021, 20 (1) : 243-280. doi: 10.3934/cpaa.2020265
[12]

Jing Qin, Shuang Li, Deanna Needell, Anna Ma, Rachel Grotheer, Chenxi Huang, Natalie Durgin. Stochastic greedy algorithms for multiple measurement vectors. Inverse Problems & Imaging, 2021, 15 (1) : 79-107. doi: 10.3934/ipi.2020066
[13]

Andrew Comech, Scipio Cuccagna. On asymptotic stability of ground states of some systems of nonlinear Schrödinger equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1225-1270. doi: 10.3934/dcds.2020316
[14]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067
[15]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065
[16]

Feifei Cheng, Ji Li. Geometric singular perturbation analysis of Degasperis-Procesi equation with distributed delay. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 967-985. doi: 10.3934/dcds.2020305
[17]

Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1447-1468. doi: 10.3934/dcdsb.2020168
[18]

Yanan Li, Zhijian Yang, Na Feng. Uniform attractors and their continuity for the non-autonomous Kirchhoff wave models. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021018
[19]

Denis Serre. Non-linear electromagnetism and special relativity. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 435-454. doi: 10.3934/dcds.2009.23.435
[20]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129

 Impact Factor: 

Tools

Metrics

  • PDF downloads (78)
  • HTML views (0)
  • Cited by (18)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences