Fast Iterative Solvers for Toeplitz-Plus-Band Systems

The authors consider the solutions of Hermitian Toeplitz-plus-band systems (An + Bn)x = b, where An are n-by-n Toeplitz matrices and Bn are n-by-n band matrices with bandwidth independent of n. These systems appear in solving integrodifferential equations and signal processing. However, unlike the case of Toeplitz systems, no fast direct solvers have been developed for solving them. In this paper, the preconditioned conjugate gradient method with band matrices as preconditioners is used. The authors prove that if An is generated by a nonnegative piecewise continuous function and Bn is positive semidefinite, then there exists a band matrix Cn, with bandwidth independent of n, such that the spectra of Cn-1 (An + Bn) are uniformly bounded by a constant independent of n. In particular, we show that the solution of (An + Bn)x = b can be obtained in O(n log n) operations.