Advanced Search
Article Contents
Article Contents

Decentralized gradient algorithm for solution of a linear equation

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 68Q85 ; Secondary: 11D04.


    \begin{equation} \\ \end{equation}
  • [1]

    C. Anderson, Solving linear eqauations on parallel distributed memory architectures by extrapolation, Technical Report, Royal Institute of Technology, 1997.


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


    T. Chang, A. Nedic and A. Scaglione, Distributed constrained optimization by consensus-based primal-dual perturbation method, IEEE Transactions on Automatic Control, 59 (2014), 1524-1538.doi:  10.1109/TAC.2014.2308612.


    F. R. K. Chung, Spectral Graph Theory, American Mathematical Society, 1997.


    J. C. Duchi, A. Agarwal and M. J. Wainwright, Dual averaging for distributed optimization: Convergence analysis and network scaling, IEEE Transactions on Automatic Control, 57 (2012), 592-606.doi: 10.1109/TAC.2011.2161027.


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


    U. Helmke and J. B. Moore, Optimization and Dynamical Systems, Communications and Control Engineering, Springer, London, 1994.doi: 10.1007/978-1-4471-3467-1.


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


    D. Jakovetic, J. M. F. Moura and J. Xavier, Fast distributed gradient methods, IEEE Transactions on Automatic Control, 59 (2014), 1131-1146.doi: 10.1109/TAC.2014.2298712.


    S. Kar, J. M. F. Moura and K. Ramanan, Distributed parameter estimation in sensor networks: Nonlinear observation models and imperfect communication, IEEE Transactions on Information Theory, 58 (2012), 1-52.doi: 10.1109/TIT.2012.2191450.


    K. Kurdyka, T. Mostowski and A. Parusinski, Proof of the gradient conjecture of R. Thom, Annals of Mathematics, 152 (2000), 763-792.doi: 10.2307/2661354.


    S. Lojasiewicz, Sur les trajectoires du gradient dune fonction analytique, Seminari di Geometria, Universita degli Studi di Bologna, 1984, 115-117.


    D. G. Luenberger, Optimization by Vector Space Methods, John Wiley and Sons, 1969.


    R. Mehmood and J. Crowcroft, Parallel Iterative Solution Method of Large Sparse Linear Equation Systems, Technical Report, University of Cambridge, 2005.


    B. Mohar, The Laplacian spectrum of graphs, Graph Theory, Combinatorics and Applications, (1991), 871-898.doi:


    S. Mou, A. S. Morse, Z. Lin, L. Wang and D. Fullmer, A distributed algorithm for efficiently solving linear equations and its applications, Systems and Control Letters, Submitted, 2015.


    S. Mou and A. S. Morse, A fixed-neighbor,distributed algorithm for solving a linear algebraic equation, European Control Conference, (2013), 2269-2273.


    S. Mou, J. Liu and A. S. Morse, A distributed algorithm for solving a linear algebraic equation, the 51st Annual Allerton Conference on Communication, Control and Computing, (2013), 267-274.


    S. Mou, J. Liu and A. S. Morse, A distributed algorithm for solving a linear algebraic equation, IEEE Transactions on Automatic Control, 60 (2015), 5409-5414.doi: 10.1109/TAC.2015.2414771.


    A. Nedic, A. Ozdaglar and P. A. Parrilo, Constrained consensus and optimization in multi-agent networks, IEEE Transactions on Automatic Control, 55 (2010), 922-938.doi: 10.1109/TAC.2010.2041686.


    A. Nedic and A. Olshevsky, Distributed optimization over time-varying directed graphs, IEEE Transactions on Automatic Control, 60 (2014), 601-615.doi: 10.1109/TAC.2014.2364096.


    J. J. Sylvester, On the relation between the minor determinants of linearly equivalent quadratic functions, Phylosophical Magazine, 1 (1851), 295-305.doi: 10.1080/14786445108646735.


    C. Wang, K. Ren, J. Wang and Q. Wang, Harnessing the cloud for securely outsourcing large-scale systems of linear equations, IEEE Transactions on Parallel and Distributed Systems, 24 (2013), 1172-1181.doi: 10.1109/TPDS.2012.206.

  • 加载中

Article Metrics

HTML views() PDF downloads(311) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint