The extension of the concept of the generating function to a class of preconditioned Toeplitz matrices. (English) Zbl 0933.65038
The author investigates the asymptotic distribution of the spectra of Hermitian Toeplitz matrices and applies the results to the spectral analysis of preconditioned Toeplitz matrices in terms of the generating function of these matrices. The impact on the convergence behavior of the related preconditioned conjugate gradient method is analyzed and the special case of block Toeplitz matrices is addressed as well.
Reviewer: R.H.W.Hoppe (München)
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 15A12 | Conditioning of matrices |
| 15A42 | Inequalities involving eigenvalues and eigenvectors |
Keywords:
Toeplitz matrices; generating function; spectral analysis; preconditioning; conjugate gradient methodReferences:
| [1] | Avram, F., On bilinear forms on Gaussian random variables and Toeplitz matrices, Probab. Theory Related Fields, 79, 37-45 (1988) · Zbl 0648.60043 |
| [2] | Axelsson, O.; Barker, V., Finite Element Solution of Boundary Value Problems, Theory and Computation (1984), Academic: Academic New York · Zbl 0537.65072 |
| [3] | Axelsson, O.; Lindskög, G., The rate of convergence of the preconditioned conjugate gradient method, Numer. Math., 52, 499-523 (1986) · Zbl 0564.65017 |
| [4] | Axelsson, O.; Neytcheva, M., (Bainov, D., The algebraic multilevel iteration methods—theory and applications. The algebraic multilevel iteration methods—theory and applications, Proceedings of the 2nd International Colloquium on Numerical Analysis (Aug. 1993), Plovdiv: Plovdiv Bulgaria), 13-23 · Zbl 0845.65012 |
| [5] | Bini, D.; Capovani, M., Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl., 52/53, 99-126 (1983) · Zbl 0549.15005 |
| [6] | Bini, D.; Di Benedetto, F., A new preconditioner for the parallel solution of positive definite Toeplitz linear systems, (Crete, Greece. Crete, Greece, Proceedings of the 2nd SPAA Conference (July 1990)), 220-223 |
| [7] | Bini, D.; Favati, P., On a matrix algebra related to the discrete Hartley transform, SIAM J. Matrix Anal. Appl., 14, 500-507 (1993) · Zbl 0773.65029 |
| [8] | Chan, R. H., Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions, IMA J. Numer. Anal., 11, 333-345 (1991) · Zbl 0737.65022 |
| [9] | Chan, R. H.; Ching, W., Toeplitz-circulant preconditioners for Toeplitz systems and their applications to queueing network with batch arrivals, SIAM J. Sci. Comput., 17, 762-772 (1996) · Zbl 0859.65030 |
| [10] | Chan, R. H.; Nagy, J.; Plemmons, R., Circulant preconditioned least squares iterations, SIAM J. Matrix Anal. Appl., 15, 80-97 (1994) · Zbl 0799.65046 |
| [11] | Chan, R. H.; Strang, G., Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Statist. Comput., 10, 104-119 (1989) · Zbl 0666.65030 |
| [12] | R. H. Chan and P. Tang, Fast band-Toeplitz preconditioners for Hermitian Toeplitz systems, SIAM J. Sci. Comput. 15:164-171.; R. H. Chan and P. Tang, Fast band-Toeplitz preconditioners for Hermitian Toeplitz systems, SIAM J. Sci. Comput. 15:164-171. · Zbl 0797.65022 |
| [13] | Chan, T. F., An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput., 9, 766-771 (1988) · Zbl 0646.65042 |
| [14] | Cheney, E., Introduction to Approximation Theory (1966), McGraw-Hill: McGraw-Hill New York · Zbl 0161.25202 |
| [15] | Di Benedetto, F., Analysis of preconditioning techniques for ill-conditioned Toeplitz matrices, SIAM J. Sci. Comput., 16, 682-697 (1995) · Zbl 0830.65032 |
| [16] | Di Benedetto, F.; Fiorentino, G.; Serra, S., C. G. preconditioning for Toeplitz matrices, Comput. Math. Appl., 25, 35-45 (1993) · Zbl 0782.65063 |
| [17] | Gohberg, I.; Feldman, I., Convolution Equations and Projection Methods for Their Solution, (Transl. Math. Monogr., 41 (1974), Amer. Math. Soc: Amer. Math. Soc Providence) · Zbl 0951.47021 |
| [18] | Golub, G. H.; Van Loan, C. F., Matrix Computations (1983), Johns Hopkins U.P: Johns Hopkins U.P Baltimore · Zbl 0559.65011 |
| [19] | Grenander, U.; Szegö, G., Toeplitz Forms and Their Applications (1984), Chelsea: Chelsea New York · Zbl 0611.47018 |
| [20] | Iokhvidov, I. S., Hankel and Toeplitz Forms: Algebraic Theory (1982), Birkhäuser: Birkhäuser Boston · Zbl 0197.02705 |
| [21] | Kac, M.; Murdoch, W.; Szegö, G., On the extreme eigenvalues of certain Hermitian forms, J. Rational Mech. Anal., 13, 767-800 (1953) · Zbl 0051.30302 |
| [22] | Krein, M. G., On some new Banach algebras and Wiener-Levy theorems for Fourier Series and integrals, Amer. Math. Soc. Transl., 93, 177-199 (1970) · Zbl 0214.14202 |
| [23] | Oppenheim, A., Applications of Digital Signal Processing (1978), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J |
| [24] | Parter, S. V., Extreme eignevalues of Toeplitz forms and applications to elliptic difference equations, Trans. Amer. Math. Soc., 99, 153-162 (1996) |
| [25] | Parter, S. V., On the distribution of singular values of Toeplitz matrices, Lin. Algebra Appl., 80, 115-130 (1986) · Zbl 0601.15006 |
| [26] | M. Pourahamadi, Remarks on the extreme eigenvalues of Toeplitz matrices, Internat. J. Math. Math. Sci. 11:23-26.; M. Pourahamadi, Remarks on the extreme eigenvalues of Toeplitz matrices, Internat. J. Math. Math. Sci. 11:23-26. · Zbl 0638.47023 |
| [27] | Serra, S., Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems, BIT, 34, 579-594 (1994) · Zbl 0823.65030 |
| [28] | Serra, S., (Luk, F., Conditioning and solution of Hermitian (block) Toeplitz systems by means of preconditioned conjugate gradient methods. Conditioning and solution of Hermitian (block) Toeplitz systems by means of preconditioned conjugate gradient methods, Proceedings in Advanced Signal Processing Algorithms, Architectures, and Implementations—SPIE conference (July 1995)), 326-337, San Diego |
| [29] | Serra, S., Preconditioning strategies for Hermitian Toeplitz systems with nondefinite generating functions, SIAM J. Matrix Anal. Appl., 17, 4, 1007-1019 (1996) · Zbl 0877.65025 |
| [30] | S. Serra, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Linear Algebra Appl., in press.; S. Serra, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Linear Algebra Appl., in press. · Zbl 0892.15014 |
| [31] | Serra, S., On the extreme spectral properties of Toeplitz matrices generated by \(L^1\) functions with several minima (maxima), BIT, 36, 135-142 (1996) · Zbl 0851.15008 |
| [32] | Serra, S., Optimal, quasi-optimal and superlinear preconditioners for asymptotically ill-conditioned positive definite Toeplitz matrices, Math. Comp., 66, 651-665 (1997) · Zbl 0864.65019 |
| [33] | Serra, S., Sulle proprietà spettrali di matrici precondizionate di Toeplitz, Boll. Un. Mat. Ital., 11-7, 463-483 (1997) · Zbl 0892.15015 |
| [34] | S. Serra, Superlinear PCG methods for symmetric Toeplitz systems, Math. Comp., to appear.; S. Serra, Superlinear PCG methods for symmetric Toeplitz systems, Math. Comp., to appear. · Zbl 1043.65066 |
| [35] | S. Serra, New PCG based methods for Hermitian Toeplitz systems, Calcolo, in press.; S. Serra, New PCG based methods for Hermitian Toeplitz systems, Calcolo, in press. |
| [36] | Stoer, J.; Burlish, R., (Introduction to Numerical Analysis, Vol. 1 (1970), Springer-Verlag: Springer-Verlag Berlin) |
| [37] | Szegö, G., Orthogonal polynomials, Amer. Math. Soc. Colloq. Publ., 23 (1939) · JFM 65.0278.03 |
| [38] | P. Tilli, On the asymptotic distribution of the eigenvalues of Hermitian Toeplitz matrices with Toeplitz blocks, Math. Comp., in press.; P. Tilli, On the asymptotic distribution of the eigenvalues of Hermitian Toeplitz matrices with Toeplitz blocks, Math. Comp., in press. · Zbl 0870.65031 |
| [39] | P. Tilli, Singular values and eigenvalues of non-Hermitian block Toeplitz matrices, Linear Algebra Appl., in press.; P. Tilli, Singular values and eigenvalues of non-Hermitian block Toeplitz matrices, Linear Algebra Appl., in press. · Zbl 0906.15012 |
| [40] | Tyrtyshnikov, E.; Zamarashkin, N., Spectra of multilevel Toeplitz matrices: Advanced theory via simple matrix relationships (1996), private communication · Zbl 0890.15006 |
| [41] | Tyrtyshnikov, E., A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl., 232, 1-43 (1996) · Zbl 0841.15006 |
| [42] | Widom, H., Szegö limit theorem: The higher dimensional matrix case, J. Funct. Anal., 39, 182-198 (1980) · Zbl 0465.47034 |
| [43] | Widom, H., On the eigenvalues of certain Hermitian operators, Trans. Amer. Math. Soc., 88, 491-522 (1958) · Zbl 0101.09202 |
| [44] | Widom, H., On the singular values of Toeplitz matrices, Z. Anal. Anwendungen, 8, 221-229 (1989) · Zbl 0692.47028 |
| [45] | Widom, H., (Hirshman, I., Toeplitz matrices. Toeplitz matrices, Studies in Real and Complex Analysis (1965), Math. Assoc. Amer) · Zbl 0173.42501 |
| [46] | Zygmund, A., Trigonometric Series (1959), Cambridge U.P: Cambridge U.P Cambridge · JFM 58.0280.01 |
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.
