Iterative methods for the parallel solution of linear systems (Q1095580)

For the parallel solution of a linear system \(x=Px+q\), where the spectral radius of P is \(r<1\), the iteration \(x_{i+1}=\bar Px_ i+\bar q\) with \(\bar P=P^ n\), \(\bar q=\sum_{i<k}P^ iq\) is considered. By explicit computation of \(\bar P\) for \(k=0(1/\log r^{-1})\), the iteration provides approximations to x of given accuracy in \(0(\log^ 2n)\) operations on \(0(n^ 3)\) processors when \(r=1-0(n^{-\ell})\) for some \(\ell\).