Repeated Matrix Squaring for the Parallel Solution of Linear Systems

Given a nxn nonsingular linear system Ax=b, we prove that thesolution x can be computed in parallel time ranging from Omega(logn) to O(log^2 n), provided that the condition number, c(A), of A isbounded by a polynomial in n. In particular, if c(A) = O(1), a timebound O(log n) is achieved. To obtain this result, we reduce thecomputation of x to repeated matrix squaring and prove that a numberof steps independent of n is sufficient to approximate x up to arelative error 2^–d, d=O(1). This algorithm has both theoretical andpractical interest, achieving the same bound of previously publishedparallel solvers, but being far more simple.