TY - JOUR
T1 - Inverse product Toeplitz preconditioners for non-Hermitian Toeplitz systems
AU - Lin, Fu Rong
AU - Ng, Michael K.
N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.
PY - 2010/6
Y1 - 2010/6
N2 - 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 TFTL-1TU-1 where TF, TL, and TU are full, band lower triangular, and band upper triangular Toeplitz matrices, respectively. Our basic idea is to decompose the generating function properly such that all factors TF, TL, and TU of the preconditioner are as well-conditioned as possible. We prove that under certain 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.
AB - 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 TFTL-1TU-1 where TF, TL, and TU are full, band lower triangular, and band upper triangular Toeplitz matrices, respectively. Our basic idea is to decompose the generating function properly such that all factors TF, TL, and TU of the preconditioner are as well-conditioned as possible. We prove that under certain 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.
KW - Generating function
KW - GMRES
KW - Rational function
KW - Toeplitz matrix
UR - http://www.scopus.com/inward/record.url?scp=77952010244&partnerID=8YFLogxK
U2 - 10.1007/s11075-009-9335-7
DO - 10.1007/s11075-009-9335-7
M3 - Journal article
AN - SCOPUS:77952010244
SN - 1017-1398
VL - 54
SP - 279
EP - 295
JO - Numerical Algorithms
JF - Numerical Algorithms
IS - 2
ER -