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.