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.