Preconditioning Block Toeplitz Matrices

We investigate the spectral behavior of preconditioned block Toeplitz matrices with small non-Toeplitz blocks. These matrices have a quite different behavior than scalar or mulitlevel Toeplitz matrices. Based on the connection between Toeplitz and Hankel matrices we derive some negative results on eigenvalue clustering for ill-conditioned block Toeplitz matrices. Furthermore, we identify Block Toeplitz matrices that are easy to solve by the preconditioned conjugate gradient method. We derive some useful inequalities that give information on the location of the spectrum of the preconditioned systems. The described analysis also gives information on preconditioning ill-conditioned Toeplitz Schur complement matrices and Toeplitz normal equations. Electronic Transactions on Numerical Analysis