×

Preconditioners for non-Hermitian Toeplitz systems. (English) Zbl 1051.65053

Summary: We construct new \(\omega \)-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 \(\mathcal O(N^{\alpha })\) the corresponding preconditioned conjugate gradient (PCG) method requires at most \(\mathcal O(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 to 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 queueing models with batch arrival.

MSC:

65F35 Numerical computation of matrix norms, conditioning, scaling
65F10 Iterative numerical methods for linear systems
60K25 Queueing theory (aspects of probability theory)
65C50 Other computational problems in probability (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chan, SIAM Review 38 pp 427– (1996) · Zbl 0863.65013 · doi:10.1137/S0036144594276474
[2] Chan, SIAM Journal on Scientific Computing 17 pp 762– (1996) · Zbl 0859.65030 · doi:10.1137/S1064827594266581
[3] Chan, SIAM Journal on Numerical Analysis 30 pp 1193– (1993) · Zbl 0787.65017 · doi:10.1137/0730062
[4] Di Benedetto, Linear Algebra and its Applications 285 pp 229– (1998) · Zbl 0935.65036 · doi:10.1016/S0024-3795(98)10115-5
[5] Ku, SIAM Journal on Matrix Analysis and Applications 14 pp 521– (1993) · Zbl 0773.65019 · doi:10.1137/0614037
[6] Potts, Linear Algebra and its Applications 281 pp 265– (1998) · Zbl 0934.65053 · doi:10.1016/S0024-3795(98)10042-3
[7] Sonneveld, SIAM Journal on Scientific and Statistical Computing 10 pp 36– (1989) · Zbl 0666.65029 · doi:10.1137/0910004
[8] Matrix Analysis. Cambridge University Press: Cambridge, 1985. · Zbl 0576.15001 · doi:10.1017/CBO9780511810817
[9] Parter, Linear Algebra and its Applications 80 pp 115– (1986) · Zbl 0601.15006 · doi:10.1016/0024-3795(86)90280-6
[10] Tyrtyshnikov, Linear Algebra and its Applications 232 pp 1– (1996) · Zbl 0841.15006 · doi:10.1016/0024-3795(94)00025-5
[11] Iterative Solution Methods. Cambridge University Press: Cambridge, 1996.
[12] Tyrtyshnikov, Linear Algebra and its Applications 216 pp 1– (1995) · Zbl 0821.65013 · doi:10.1016/0024-3795(93)00092-E
[13] Approximation theory and numerical linear algebra. In Algorithms for Approximation II, (eds.). Chapman & Hall: London, 1990.
[14] Iterative Methods for Sparse Linear Systems. PWS Publ.: Boston, 1996.
[15] Wang, IEEE Transactions on Acoustics Speech and Signal Processing 32 pp 803– (1994) · Zbl 0577.65134 · doi:10.1109/TASSP.1984.1164399
[16] Potts, BIT 39 pp 513– (1999) · Zbl 0938.65067 · doi:10.1023/A:1022322820082
[17] Carlson, Mathematics of Computation 66 pp 215– (1997) · Zbl 0854.65054 · doi:10.1090/S0025-5718-97-00789-8
[18] Oda, IEEE Transactions on Communications 39 pp 737– (1991) · doi:10.1109/26.87164
[19] Seila, American Journal of Mathematical and Management Sciences 10 pp 17– (1990) · Zbl 0725.62052 · doi:10.1080/01966324.1990.10737275
[20] Matrix Computations (3rd edn). John Hopkins University Press: Baltimore, 1996. · Zbl 0865.65009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.