Complexity of Solving Linear Systems in Different Models of Computation
Adam W. Bojańczyk · SIAM Journal on Numerical Analysis · 1984
The computational complexity of solving an $n \times n$ system of linear equations depends on whether the computational model is (a) sequential or parallel, and (b) fixed precision or variable precision. We survey known complexity results for each of the four cases, and introduce a new algorithm for the parallel/variable precision case that is based on Newton’s method. If $n^3$ processors are available, this algorithm has complexity asymptotically equivalent to one scalar multiplication, independent of n. If only $n^2$ processors are available, the complexity is proportional to but still competitive with known alternatives.