Search

In this paper we study the preconditioning of n×n non-symmetric, real Toeplitz systems, when the generating function of the coefficient matrix Tn is not known a priori, but we know that a generating function f exists related to the matrix sequence {;Tn};, Tn=Tn(f), with f smooth enough. The proposed preconditioner is derived as a combination of a band Toeplitz and a circulant matrix. We give details for the construction of the proposed preconditioner, by the entries of Tn and we study the cluster of the eigenvalues, as well as of the singular values, of the sequences of the coefficient matrices related to the reconditioned systems. Theoretical results prove the efficiency of the Preconditioned Generalized Minimal Residual method (PGMRES) and the reconditioned Conjugate Gradient method of Normal Equations (PCGN). Such efficiency is also shown in demonstrating numerical examples, using the proposed preconditioning technique.

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 2π-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 T n we estimate the unknown function, forming its Fourier expansion, on an equally spaced grid G n in (−π, π). 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).