A distributed algorithm for efficiently solving linear equations and its applications (Special Issue JCW)

A distributed algorithm is proposed for solving a linear algebraic equation Ax=bAx=b over a multi-agent network, where A∈Rn̄×n and the equation has a unique solution x∗∈Rnx∗∈Rn. Each agent knows only a subset of the rows of [Ab], controls a state vector xi(t)xi(t) of size smaller than nn and is able to receive information from its nearby neighbors. Neighbor relations are characterized by time-dependent directed graphs. It is shown that for a large class of time-varying networks, the proposed algorithm enables each agent to recursively update its own state by only using its neighbors’ states such that all xi(t)xi(t) converge exponentially fast to a specific part of x∗x∗ of interest to agent ii. Applications of the proposed algorithm include solving the least square solution problem and the network localization problem.