Preconditioners for ill-conditioned Toeplitz matrices (Q1307244)

The authors consider the iterative solution of systems of equations \(A_N(f) x = b\), where the sequence \(\{A_N(f)\}_{N=1}^\infty\) of positive definite Hermitian ill-conditioned Toeplitz matrices is generated by a non-negative \(2\pi\)-periodic continuous function \(f\). The construction of Hermitian and positive definite preconditioners is described. It is proved that the number of iterations of the preconditioned conjugate gradient (pcg) method needed to obtain an approximate solution with a fixed relative accuracy is independent of \(N\). Due to the fact that the multiplication of a Toeplitz matrix with a vector can be performed with \(O(N \log N)\) arithmetical operations, the computational cost of the pcg method is \(O(N \log N)\). Furthermore, the construction of preconditioners for symmetric Toeplitz matrices, non Hermitian Toeplitz matrices, and doubly symmetric block Toeplitz matrices with Toeplitz blocks is discussed. Finally, numerical experiments confirming the theoretical results are presented.