Solving for a Single Component of the Solution to a Linear System, Asynchronously

We present synchronous and asynchronous randomized variants of an 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 ∈ R n. This can equivalently be formulated as solving for xi in x = Gx + z for some G and z such that the spectral radius of G is less than 1. We consider the setting where n is large, yet G is sparse, i.e., each row has at most d nonzero entries. Our algorithm relies on the Neumann series characterization of the component xi . Both variants of our algorithm produce an estimate ˆxi such that |xˆi − xi | ≤ kxk2, and we provide convergence rate guarantees when kGk2 < 1. Our algorithms obtain an approximation for xi in constant time with respect to the size of the matrix when d = O(1) and 1/(1 − kGk2) = O(1). This requires analyzing the product of random matrices which are drawn from distributions that are time and path dependent. We also give general conditions under which the asynchronous algorithm converges asymptotically regardless of the order and frequency of updates.