Fast Iterative Solvers for Toeplitz-Plus-Band Systems
Raymond H. Chan, Kwok-Po Ng · SIAM Journal on Scientific Computing · 1993
The authors consider the solutions of Hermitian Toeplitz-plus-band systems $(A_n + B_n )x = b$, where $A_n $ are n-by-n Toeplitz matrices and $B_n $ 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 $A_n $ is generated by a nonnegative piecewise continuous function and $B_n $ is positive semidefinite, then there exists a band matrix $C_n $, with bandwidth independent of n, such that the spectra of $C_n^{ - 1} (A_n + B_n )$ are uniformly bounded by a constant independent of n. In particular, we show that the solution of $(A_n + B_n )x = b$ can be obtained in $O(n\log n)$ operations.