Premium
Preconditioners for non‐Hermitian Toeplitz systems
Author(s) -
Chan Raymond H.,
Potts Daniel,
Steidl Gabriele
Publication year - 2001
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/1099-1506(200103)8:2<83::aid-nla231>3.0.co;2-x
Subject(s) - toeplitz matrix , circulant matrix , hermitian matrix , mathematics , eigenvalues and eigenvectors , unit circle , sequence (biology) , levinson recursion , pure mathematics , algebra over a field , combinatorics , physics , quantum mechanics , biology , genetics
In this paper, we construct new ω ‐circulant preconditioners for non‐Hermitian Toeplitz systems, where we allow the generating function of the sequence of Toeplitz matrices to have zeros on the unit circle. We prove that the eigenvalues of the preconditioned normal equation are clustered at 1 and that for ( N , N )‐Toeplitz matrices with spectral condition number ( N α ) the corresponding PCG method requires at most ( N log 2 N ) arithmetical operations. If the generating function of the Toeplitz sequence is a rational function then we show that our preconditioned original equation has only a fixed number of eigenvalues which are not equal to 1 such that preconditioned GMRES needs only a constant number of iteration steps independent of the dimension of the problem. Numerical tests are presented with PCG applied to the normal equation, GMRES, CGS and BICGSTAB. In particular, we apply our preconditioners to compute the stationary probability distribution vector of Markovian queuing models with batch arrival. Copyright © 2001 John Wiley & Sons, Ltd.