\`x^2+y_1+z_12^34\`
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.

    Citation:

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

    C. Anderson, Solving linear eqauations on parallel distributed memory architectures by extrapolation, Technical Report, Royal Institute of Technology, 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, IEEE Transactions on Automatic Control, 59 (2014), 1524-1538.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, IEEE Transactions on Automatic Control, 57 (2012), 592-606.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, Springer, London, 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, IEEE Transactions on Automatic Control, 59 (2014), 1131-1146.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, IEEE Transactions on Information Theory, 58 (2012), 1-52.doi: 10.1109/TIT.2012.2191450.

    [11]

    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.

    [12]

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

    [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, University of Cambridge, 2005.

    [15]

    B. Mohar, The Laplacian spectrum of graphs, Graph Theory, Combinatorics and Applications, (1991), 871-898.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, Systems and Control Letters, Submitted, 2015.

    [17]

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

    [18]

    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.

    [19]

    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.

    [20]

    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.

    [21]

    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.

    [22]

    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.

    [23]

    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.

  • 加载中
SHARE

Article Metrics

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

Access History

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return