Band Preconditioners for Non-Symmetric Real Toeplitz Systems with Unknown Generating Function

Abstract

Toeplitz systems appear in a variety of applications in real life such as signal processing, image processing and restoration and discretization of PDEs. The fast convergence to the accurate solution of the system seems to be necessary, taking into account that the dimension of the arising systems is very large. It is well known that iterative methods and especially Krylov subspace methods are the most efficient methods for this kind of problems. Toeplitz matrices are generated by 2p-periodic generating functions. In many applications the generating function has roots at some points and this is transferred to the Toeplitz matrix, which becomes ill-conditioned. As it is widely known, this can be overcome by using an appropriate preconditioner. Symmetric and positive definite Toeplitz systems were extensively studied by many researchers. Real, non-symmetric and positive definite or non-definite Toeplitz systems also appear in applications and attract the interest of researchers. In some problems the generating function is not known a priori.In this paper, we study a preconditioning technique for non-symmetric, real Toeplitz systems with unknown generating function. We focus on ill-conditioned systems of such form and we aim to present extensively the band Toeplitz preconditioner's construction procedure by the entries of the initial system. From the entries of the coefficient matrix Tn we estimate the unknown function, forming its Fourier expansion, on an equally spaced grid Gn in (-p, p). Then, we propose a procedure to estimate possible roots of the generating function and their multiplicities, in order to form the trigonometric polynomial that eliminates the roots. After eliminating the roots, we apply the well-known Remez algorithm for further approximation. An algorithm describing step-by-step this procedure is presented. Theoretical results concerning the spectra clustering are also given. Suitable numerical examples are demonstrated to show the validity and efficiency of the proposed preconditioning technique, using the Preconditioned Generalized Minimal Residual method (PGMRES). © 2021 IEEE.