This paper explores a seemingly counter-intuitive idea: the possibility of accelerating the solution of certain linear equations by adding even more equations to the problem. The basic insight is to trade-off problem size by problem structure. We test this idea on Toeplitz equations, in which case the expense of a larger set of equations easily leads to circulant structure. The idea leads to a very simple iterative algorithm, which works for a certain class of Toeplitz matrices, each iteration requiring only two circular convolutions. In the symmetric definite case, numerical experiments show that the method can compete with the preconditioned conjugate gradient method (PCG), which achieves O (n log n) performance. Because the iteration does not converge for all Toeplitz matrices, we give necessary and sufficient conditions to ensure convergence (for not necessarily symmetric matrices), and suggest an efficient convergence test. In the positive definite case we determine the value of the free parameter of the circulant that leads to the fastest convergence, as well as the corresponding value for the spectral radius of the iteration matrix. Although the usefulness of the proposed iteration is limited in the case of ill-conditioned matrices, we believe that the results show that the problem size/problem structure trade-off deserves further study.

This paper introduces and analyzes a new preconditioner for Toeplitz matrices that exhibits excellent spectral properties: the eigenvalues of the preconditioned matrix are highly clustered around the unity. When used with the preconditioned conjugate gradient method this results in very fast convergence. The new preconditioner can be regarded as a refinement of preconditioners built by embedding the Toeplitz matrix in a positive definite circulant. Necessary and sufficient conditions that ensure that the positive definite embedding is possible are given.

This paper explores the relationship between Toeplitz and circulant matrices. Upper and lower bounds for all eigenvalues of Hermitian Toeplitz matrices are given, capitalizing on the possibility of embedding a Toeplitz matrix in a circulant, and of expressing any Toeplitz matrix as a sum of two matrices with known eigenvalues. The bounds can be simultaneously found using a single discrete Fourier transform evaluation. Simulation results indicate that the bounds are sharper than other known bounds.