A fast, preconditioned conjugate gradient Toeplitz solver (Q1205912)

The paper describes a fast Toeplitz solver based on the preconditioned conjugate gradient (CG) method. First it describes a factorization of an arbitrary Hermitian, positive definite matrix \(A=(A+\mu I)(I-\mu(A+\mu I)^{-1})\), where \(\mu\) is a parameter. If the extreme eigenvalues of \(A\) are known this factorization can be made optimal as far as the condition numbers are concerned, i.e. the condition numbers of each of the two factors equal the square root of the condition number \(\kappa\) of \(A\). Then this technique is applied to the solution of Toeplitz systems. Fast Fourier transform is used to compute matrix-vector products. There is a detailed analysis which shows (theoretically) how the shift \(\mu\) has to be chosen to get optimal condition numbers for the CG. Practical experience how really to choose \(\mu\) is presented as well as numerical results for a real time series example. The results show less effort than the unpreconditioned CG for \(n\) sufficiently large, say \(n>2^{10}\), but slightly increased residuals. For the example other techniques like the methods of \textit{G. Strang} [Stud. Appl. Math. 74, 171-176 (1986; Zbl 0621.65025)] or of \textit{T. F. Chan} [SIAM J. Sci. Stat. Comput. 9, No. 4, 766-771 (1988; Zbl 0646.65042)] are used which yield a different behaviour (non-competitive, better). This leads to the conclusion that for large, well-conditioned problems the technique may be quite useful compared with other superfast methods (complexity \({\mathcal O}(n\log n\kappa^{1/4})\) instead of \(8n\log^ 2n)\).