The construction of an algebraically reduced system for the acceleration of preconditioned conjugate gradients (Q1919509)

The preconditioned conjugate gradient method to solve an \(n\)-dimensional symmetric positive definite system \(Ax=b\) is discussed. For the solution, one chooses a \(k\)-dimensional subspace \(S\), generated by the \(A\)-conjugate vectors \(p_0,p_1,\dots,p_{k-1}\). Then the solution \(x\) is split as \(x=y+z\) with \(y\) the \(A\)-projection of \(x\) onto \(S:y=Px\), and \(z\) its \(A\)-orthogonal complement \(z=Rx=(I-P)x\). Then \(z\) is computed by solving iteratively \(Az= R^Tb\), which is equivalent with \(R^TAx=R^Tb\). Usually this iteration will converge faster than the original one on \(x\). The method is traditionally applied to a system that is the cyclic reduction of a discretized selfadjoint partial differential equation. In this paper, an alternative is proposed for this classical use of the method. The success of the method will indeed depend upon the ease of computation of the projection \(y\). This can be made easy by a clever choice of the generating vectors \(p_1,p_2,\dots,p_{k-1}\). This method is illustrated for a system that is a preconditioned cyclically reduced system. The technique corresponds to repeated cyclic reduction by carefully choosing the basis vectors. However, the principles are applicable for any positive definite system.