Exponential convergence of a distributed algorithm for solving linear algebraic equations

In a recent paper, a distributed algorithm was proposed for solving linear algebraic equations of the form Ax=b assuming that the equation has at least one solution. The equation is presumed to be solved by m agents assuming that each agent knows a subset of the rows of the matrix Ab, the current estimates of the equation's solution generated by each of its neighbors, and nothing more. Neighbor relationships are represented by a time-dependent directed graph N(t) whose vertices correspond to agents and whose arcs characterize neighbor relationships. Sufficient conditions on N(t) were derived under which the algorithm can cause all agents' estimates to converge exponentially fast to the same solution to Ax=b. These conditions were also shown to be necessary for exponential convergence, provided the data about Ab available to the agents is “non-redundant”. The aim of this paper is to relax this “non-redundant” assumption. This is accomplished by establishing exponential convergence under conditions which are the weakest possible for the problem at hand; the conditions are based on a new notion of graph connectivity. An improved bound on the convergence rate is also derived.