A fixed-neighbor, distributed algorithm for solving a linear algebraic equation

This paper presents a distributed algorithm for solving a linear algebraic equation of the form Ax = b where A is an n × n nonsingular matrix and b is an n-vector. The equation is solved by a network of n agents assuming that each agent knows exactly one distinct row of the partitioned matrix [A b], the current estimates of the equation´s solution generated by its neighbors, and nothing more. Each agent recursively updates its estimate of A^-1b by utilizing the current estimates generated by each of its neighbors. Neighbor relations are characterized by a simple, undirected graph G whose vertices correspond to agents and whose edges depict neighbor relations. It is shown that for any nonsingular matrix A and any connected graph G, the proposed algorithm causes all agents´ estimates to converge exponentially fast to the desired solution A^-1b.