Abstract :
The eigenvalue and singular-value distributions for matrices S−1nAn and C−1nAn are examined, where An, Sn, and Cn are Toeplitz matrices, simple circulants, and optimal circulants generated by the Fourier expansion of some function f. Recently it has been proven that a cluster at 1 exists whenever f is from the Wiener class and strictly positive. Both restrictions are now weakened. A proof is given for the case when f may take the zero value, and hence the circulants are to have unbounded inverses. The main requirements on f are that it belong to L2 and be in some sense, sparsely vanishing. Specifically, if f is nonnegative and circulants Sn (or Cn) are positive definite, then the eigenvalues of S−1nAn (or C−1nAn) are clustered at 1. If f is complex-valued and Sn (or Cn) are nonsingular, then the singular values of S−1nAn (or C−1nAn) are clustered at 1 as well. Also proposed and studied are the improved circulants. It is shown that (improved) simple circulants can be much more advantageous than optimal circulants. This depends crucially on the smoothness properties of f. Further, clustering-on theorems are given that pertain to multilevel Toeplitz matrices preconditioned by multilevel simple and optimal circulants.
