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]

Technical Report, Royal Institute of Technology, 1997. Google Scholar

[2]

Cambridge University Press, 1996. doi: 10.1017/CBO9780511624100.  Google Scholar

[3]

IEEE Transactions on Automatic Control, 59 (2014), 1524-1538. doi:  10.1109/TAC.2014.2308612.  Google Scholar

[4]

American Mathematical Society, 1997.  Google Scholar

[5]

IEEE Transactions on Automatic Control, 57 (2012), 592-606. doi: 10.1109/TAC.2011.2161027.  Google Scholar

[6]

Technical Report, 1993. Google Scholar

[7]

Communications and Control Engineering, Springer, London, 1994. doi: 10.1007/978-1-4471-3467-1.  Google Scholar

[8]

Cambridge University Press, 1985. doi: 10.1017/CBO9780511810817.  Google Scholar

[9]

IEEE Transactions on Automatic Control, 59 (2014), 1131-1146. doi: 10.1109/TAC.2014.2298712.  Google Scholar

[10]

IEEE Transactions on Information Theory, 58 (2012), 1-52. doi: 10.1109/TIT.2012.2191450.  Google Scholar

[11]

Annals of Mathematics, 152 (2000), 763-792. doi: 10.2307/2661354.  Google Scholar

[12]

Seminari di Geometria, Universita degli Studi di Bologna, 1984, 115-117.  Google Scholar

[13]

John Wiley and Sons, 1969.  Google Scholar

[14]

Technical Report, University of Cambridge, 2005. Google Scholar

[15]

Graph Theory, Combinatorics and Applications, (1991), 871-898. doi: 10.1.1.96.2577.  Google Scholar

[16]

Systems and Control Letters, Submitted, 2015. Google Scholar

[17]

European Control Conference, (2013), 2269-2273. Google Scholar

[18]

the 51st Annual Allerton Conference on Communication, Control and Computing, (2013), 267-274.  Google Scholar

[19]

IEEE Transactions on Automatic Control, 60 (2015), 5409-5414. doi: 10.1109/TAC.2015.2414771.  Google Scholar

[20]

IEEE Transactions on Automatic Control, 55 (2010), 922-938. doi: 10.1109/TAC.2010.2041686.  Google Scholar

[21]

IEEE Transactions on Automatic Control, 60 (2014), 601-615. doi: 10.1109/TAC.2014.2364096.  Google Scholar

[22]

Phylosophical Magazine, 1 (1851), 295-305. doi: 10.1080/14786445108646735.  Google Scholar

[23]

IEEE Transactions on Parallel and Distributed Systems, 24 (2013), 1172-1181. doi: 10.1109/TPDS.2012.206.  Google Scholar

show all references

References:
[1]

Technical Report, Royal Institute of Technology, 1997. Google Scholar

[2]

Cambridge University Press, 1996. doi: 10.1017/CBO9780511624100.  Google Scholar

[3]

IEEE Transactions on Automatic Control, 59 (2014), 1524-1538. doi:  10.1109/TAC.2014.2308612.  Google Scholar

[4]

American Mathematical Society, 1997.  Google Scholar

[5]

IEEE Transactions on Automatic Control, 57 (2012), 592-606. doi: 10.1109/TAC.2011.2161027.  Google Scholar

[6]

Technical Report, 1993. Google Scholar

[7]

Communications and Control Engineering, Springer, London, 1994. doi: 10.1007/978-1-4471-3467-1.  Google Scholar

[8]

Cambridge University Press, 1985. doi: 10.1017/CBO9780511810817.  Google Scholar

[9]

IEEE Transactions on Automatic Control, 59 (2014), 1131-1146. doi: 10.1109/TAC.2014.2298712.  Google Scholar

[10]

IEEE Transactions on Information Theory, 58 (2012), 1-52. doi: 10.1109/TIT.2012.2191450.  Google Scholar

[11]

Annals of Mathematics, 152 (2000), 763-792. doi: 10.2307/2661354.  Google Scholar

[12]

Seminari di Geometria, Universita degli Studi di Bologna, 1984, 115-117.  Google Scholar

[13]

John Wiley and Sons, 1969.  Google Scholar

[14]

Technical Report, University of Cambridge, 2005. Google Scholar

[15]

Graph Theory, Combinatorics and Applications, (1991), 871-898. doi: 10.1.1.96.2577.  Google Scholar

[16]

Systems and Control Letters, Submitted, 2015. Google Scholar

[17]

European Control Conference, (2013), 2269-2273. Google Scholar

[18]

the 51st Annual Allerton Conference on Communication, Control and Computing, (2013), 267-274.  Google Scholar

[19]

IEEE Transactions on Automatic Control, 60 (2015), 5409-5414. doi: 10.1109/TAC.2015.2414771.  Google Scholar

[20]

IEEE Transactions on Automatic Control, 55 (2010), 922-938. doi: 10.1109/TAC.2010.2041686.  Google Scholar

[21]

IEEE Transactions on Automatic Control, 60 (2014), 601-615. doi: 10.1109/TAC.2014.2364096.  Google Scholar

[22]

Phylosophical Magazine, 1 (1851), 295-305. doi: 10.1080/14786445108646735.  Google Scholar

[23]

IEEE Transactions on Parallel and Distributed Systems, 24 (2013), 1172-1181. doi: 10.1109/TPDS.2012.206.  Google Scholar

[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]

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
[4]

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
[5]

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
[6]

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
[7]

Boris Buffoni, Laurent Landry. Multiplicity of homoclinic orbits in quasi-linear autonomous Lagrangian systems. Discrete & Continuous Dynamical Systems, 2010, 27 (1) : 75-116. doi: 10.3934/dcds.2010.27.75
[8]

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
[9]

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
[10]

Benjamin Boutin, Frédéric Coquel, Philippe G. LeFloch. Coupling techniques for nonlinear hyperbolic equations. Ⅱ. resonant interfaces with internal structure. Networks & Heterogeneous Media, 2021, 16 (2) : 283-315. doi: 10.3934/nhm.2021007
[11]

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
[12]

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
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

Larbi Berrahmoune. Null controllability for distributed systems with time-varying constraint and applications to parabolic-like equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (8) : 3275-3303. doi: 10.3934/dcdsb.2020062
[19]

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
[20]

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

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences