Abstract In this paper, we first propose product Toeplitz preconditioners (in
an inverse form) for non-Hermitian Toeplitz matrices generated by functions
with zeros. Our inverse product-type preconditioner is of the form. T
preconditioner are as well-conditioned as possible. We prove that under cer-
tain conditions, the preconditioned matrix has eigenvalues and singular values
clustered around 1. Then we use a similar idea to modify the preconditioner
proposed in Ku and Kuo (SIAM J Sci Stat Comput 13:1470–1487, 1992)to
handle the zeros in rational generating functions. Numerical results, including
applications to the computation of the stationary probability distribution of
Markovian queuing models with batch arrival, are given to illustrate the good
performance of the proposed preconditioners.
Keywords Toeplitz matrix · Generating function ·
Rational function · GMRES
1 Introduction
Toeplitz matrices are structured matrices with entries satisfying [T
x = b arise in a variety of applications
in mathematics and engineering, e.g., signal and image processing, queuing
problems, see for instance [7]. A 2π-periodic function f is called the generating
function of a sequence T
integraldisplay
−1. In the following, we denote the Toeplitz matrix T
Toeplitz preconditioners for Toeplitz systems have attracted quite a lot
of attention. For well-conditioned positive definite Hermitian Toeplitz sys-
tems, inverse Toeplitz preconditioners defined as T
clustered around 1 and numerical results indicate that the inverse Toeplitz
preconditioner is more efficient than circulant preconditioners. Later on,
inverse product Toeplitz preconditioners were proposed to precondition ill-
conditioned positive definite Hermitian Toeplitz systems, see for instance,
In this paper, we consider solving non-Hermitian Toeplitz systems
(the set of all 2π-periodic
continuous functions). The solution of non-Hermitian Toeplitz systems has
been investigated by a number of researchers [4, 8, 9, 11, 12, 17, 20, 22, 23].
Circulant preconditioners and skew-circulant preconditioners [8, 9], trigono-
metric preconditioners [12, 22], Toeplitz-circulant preconditioners [4, 11]and
banded Toeplitz preconditioners [17]for(1.1) have been proposed.
For generating function with zeros, Chan and Ching [4] consider decompos-
∈ (−π,π], j = 1,...,α and h(θ) negationslash= 0. They proposed the Toeplitz-
circulant preconditioner