Toeplitz-circulant preconditioners for toeplitz systems and their applications to queueing networks with batch arrivals

Raymond H. CHAN*, Wai Ki CHING

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

36 Citations (Scopus)

Abstract

The preconditioned conjugate gradient method is employed to solve Toeplitz systems Tnx b where the generating functions of the n-by-n Toeplitz matrices Tn are functions with zeros. In this case, circulant preconditioners are known to give poor convergence, whereas band-Toeplitz preconditioners offer only linear convergence and can handle only real-valued functions with zeros of even orders. We propose here preconditioners which are products of band-Toeplitz matrices and circulant matrices. The band-Toeplitz matrices are used to cope with the zeros of the given generating function and the circulant matrices are used to speed up the convergence rate of the algorithm. Our preconditioner can handle complex-valued functions with zeros of arbitrary orders. We prove that the preconditioned Toeplitz matrices have singular values clustered around for large n. We apply our preconditioners to solve the stationary probability distribution vectors of Markovian queueing models with batch arrivals. We show that if the number of servers is fixed independent of the queue size n, then the preconditioners are invertible and the preconditioned matrices have singular values clustered around for large n. Numerical results are given to illustrate the fast convergence of our methods.

Original languageEnglish
Pages (from-to)762-772
Number of pages11
JournalSIAM Journal on Scientific Computing
Volume17
Issue number3
DOIs
Publication statusPublished - May 1996
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 1996 Society for Industrial and Applied Mathematics.

Keywords

  • circulant matrix
  • preconditioning
  • queueing network
  • Toeplitz matrix

Fingerprint

Dive into the research topics of 'Toeplitz-circulant preconditioners for toeplitz systems and their applications to queueing networks with batch arrivals'. Together they form a unique fingerprint.

Cite this