Spectral analysis of nonsymmetric quasi-toeplitz matrices with applications to preconditioned multistep formulas

The eigenvalue spectrum of a class of nonsymmetric preconditioned matrices arising in time-dependent partial differential equations is analyzed and discussed. The matrices generated by the underlying numerical integrators are small rank perturbations of block Toeplitz matrices; circulant-like preconditioners based on the former are considered. The eigenvalue distribution of the preconditioned matrix influences often crucially the convergence of Krylov iterative accelerators. Due to several reasons (lack of symmetry, band structure, and coefficients depending on the size) the classical approach based on smooth generating functions gives very little insight here. Therefore, to characterize the eigenvalues, a difference equation approach exploiting the band Toeplitz and circulant patterns generalizing the well-known results of Trench is proposed.