Toeplitz-circulant preconditioners for Toeplitz systems and their applications to queueing networks with batch arrivals
Publication in refereed journal

香港中文大學研究人員

引用次數
替代計量分析
.

其它資訊
摘要The preconditioned conjugate gradient method is employed to solve Toeplitz systems T(n)x = b where the generating functions of the n-by-n Toeplitz matrices T-n 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 1 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 1 for large n. Numerical results are given to illustrate the fast convergence of our methods.
著者Chan RH, Ching WK
期刊名稱SIAM Journal on Scientific Computing
出版年份1996
月份5
日期1
卷號17
期次3
出版社SIAM PUBLICATIONS
頁次762 - 772
國際標準期刊號1064-8275
電子國際標準期刊號1095-7197
語言英式英語
關鍵詞circulant matrix; preconditioning; queueing network; Toeplitz matrix
Web of Science 學科類別Mathematics; Mathematics, Applied; MATHEMATICS, APPLIED

上次更新時間 2020-29-11 於 00:34