An Optimal Circulant Preconditioner for Toeplitz Systems

Given a Toeplitz matrix A, we derive an optimal circulant preconditioner C in the sense of minimizing \|C - A\|F. It is in general different from the one proposed earlier by Strang “A proposal for Toeplitz matrix calculations, ” Stud. Appl. Math. , 74 (1986), pp. 171–176, except in the case when A is itself circulant. The new preconditioner is easy to compute and in preliminary numerical experiments performs better than Strang’s preconditioner in terms of reducing the condition number of C^ - 1 A and comparably in terms of clustering the spectrum around unity.