TOEPLITZ-CIRCULANT PRECONDITIONERS FOR TOEPLITZ-SYSTEMS AND THEIR APPLICATIONS TO QUEUING-NETWORKS WITH BATCH ARRIVALS

The preconditioned conjugate gradient method is employed to solve Toep litz systems T(n)x = b where the generating functions of the n-by-n To eplitz matrices T-n are functions with zeros. In this case, circulant preconditioners are known to give poor convergence, whereas band-Toepl itz preconditioners offer only linear convergence and can handle only real-valued functions with zeros of even orders. We propose here preco nditioners which are products of band-Toeplitz matrices and circulant matrices. The band-Toeplitz matrices are used to cope with the zeros o f the given generating function and the circulant matrices are used to speed up the convergence rate of the algorithm. Our preconditioner ca n handle complex valued functions with zeros of arbitrary orders. We p rove that the preconditioned Toeplitz matrices have singular values cl ustered around 1 for large n. We apply our preconditioners to solve th e stationary probability distribution vectors of Markovian queueing mo dels with batch arrivals. We show that if the number of servers is fix ed independent of the queue size n, then the preconditioners are inver tible and the preconditioned matrices have singular values clustered a round 1 for large n. Numerical results are given to illustrate the fas t convergence of our methods.