A parallel iterative system solver (Q1064010)

The author examines an iterative method for solution of the linear system \(Au=b\), where the matrix A has real eigenvalues. Writing \(A=D(I-B)\), where D is diagonal and I the identity, the iterative method is given by \[ u^{(n+1)}=u^{(n)}+\tau (\sum^{l-1}_{k=0}\omega_ kB^ k)D^{-1}(b-Au^{(n)}), \] where l,\(\tau\), and \(\{\omega_ k\}_ 0^{l-1}\) are predetermined, fixed parameters. This method is appropriate for pipelined or parallel (SIMD or MIMD) computers. With the parameters \(\omega_ k=1\), \(k=0...(l-1)\), the author generalizes known results for \(l=1,2\) to compute the optimal value of \(\tau\) and the resulting convergence rate in terms of the extreme eigenvalues of B. Based on this analysis, the best choice for l is given as \(l=2\). For the case when \(l=2\), when the matrix B has precisely two distinct real eigenvalues, and when \(\omega_ k=\omega\), \(k=0...(l-1)\), the author computes the optimal value of \(\omega\) and the resulting convergence rate. The optimal value turns out to be \(\omega =1\).