A networked parallel algorithm for solving linear algebraic equations
Keyou You, Shiji Song, Roberto Tempo · 2016
Solving a system of linear algebraic equations is a fundamental problem, especially when there is a large number of design variables. To this purpose, we consider a collaborative framework with multiple interconnected agents that are distributed among different nodes of a network, and each agent maintains a state vector to compute the solution. Under local interactions, we propose an iterative algorithm for each agent to update the state vector via a convex combination of a consensus mechanism and a projector, which pushes the state vector toward a local constraint set. We show the linear convergence to the solution if the network is strongly connected for fixed graphs or uniformly jointly strongly connected for time-varying graphs. As an important application, we adopt this algorithm to distributedly solve the Google's PageRank problem. Moreover, we discuss the implications and relations to the relevant literature.