Trigonometric Preconditioners for Block Toeplitz Systems
Daniel Potts, Gabriele Steidl, Manfred Tasche · Birkhäuser Basel eBooks · 1997
This paper is concerned with the solution of a system of linear equations T M, N X=b, where T M, N denotes a positive definite doubly symmetric block-Toeplitz matrix with Toeplitz blocks arising from a generating function f of the Wiener class. We derive optimal and Strang-type trigonometric preconditioners P M, N of T M, N from the Fejér and Fourier sum of f, respectively. Using relations between trigonometric transforms and Toeplitz matrices, we prove that for all ε > 0 and sufficiently large M, N, at most O(M) + O(N) eigenvalues of lie outside the interval (1 — ε, l + ε) such that the preconditioned conjugate gradient method converges in at most O(M) + O(N) steps.