Band Toeplitz preconditioners for non-symmetric real Toeplitz systems by preconditioned GMRES method

[摘要] In this paper we study n x n real, non-symmetric, ill conditioned Toeplitz systems of the form T-n(f)x = b. The corresponding generating function is a complex valued one of the form f = f(1) + if(2), where i = root-1, is known a priori and has roots. We note that f(1) is a 2 pi-periodic even function while f(2) is a 2 pi-periodic odd one. In order to solve the above system efficiently, we use the Preconditioned Generalized Minimal Residual (PGMRES) method and the Preconditioned Conjugate Gradient method applied to the Normal Equations (PCGN). We present a specific preconditioning technique that combines elimination of the roots of f and best uniform approximation or interpolation by trigonometric polynomials. The proposed preconditioner is a band Toeplitz matrix T-n(p) generated by the trigonometric polynomial p = gq. The trigonometric polynomial g is an appropriate complex polynomial having the same zeros as f while q is the trigonometric polynomial derived by the uniform approximation or interpolation of the function L-g. Using T-n(p)as a preconditioner, we achieve a good clustering of the singular values of the preconditioned matrix in a small interval around 1, as well as a good clustering of the eigenvalues in a small domain in the right half-plane of the complex plane, far from zero. Moreover, we describe on how the presented preconditioning technique can be extended to the two level Toeplitz systems. Finally, we show, by various numerical experiments, that the proposed preconditioning technique can solve a Toeplitz system of the above form in a small number of iterations. (C) 2019 Published by Elsevier B.V.

[发布日期] 2020-08-01

[效力级别]  Proceedings Paper

[关键词] Non-symmetric Toeplitz matrices;Band preconditioners;Krylov subspace methods