Asynchronous Approximation of a Single Component of the Solution to a Linear System
Asuman Ozdaglar, Devavrat Shah, Christina Lee Yu · IEEE Transactions on Network Science and Engineering · 2019
We present a distributed asynchronous algorithm for approximating a single component of the solution to a system of linear equations Ax = b, where A is a positive definite real matrix and b ∈ Rn. This can equivalently be formulated as solving for xiin x = Gx + z for some G and z such that the spectral radius of G is less than 1. Our algorithm relies on the Neumann series characterization of the component xi, and is based on residual updates. We analyze our algorithm within the context of a cloud computation model motivated by frameworks, such as Apache Spark, in which the computation is split into small update tasks performed by small processors with shared access to a distributed file system. We prove a robust asymptotic convergence result when the spectral radius ρ(|G|)2additive approximation for xi in constant time with respect to the size of the matrix when the maximum row sparsity d = O(1) and 1/(1 - ||G||2) = O(1), where ||G||2is the induced matrix operator 2-norm.