×

High performance algorithms for Toeplitz and block Toeplitz matrices. (English) Zbl 0859.65017

The authors give several high performance variants of the classical Schur algorithms to factor symmetric block Toeplitz matrices. Specifically, they discuss routines to factor symmetric positive definite, positive semidefinite, and indefinite matrices. QR factorization algorithms for rank deficient matrices are discussed. A variety of numerical examples is also given.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65Y20 Complexity and performance of numerical algorithms

Software:

TOEPLITZ; toms729gw
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arushanian, O. B.; Samarin, M. K.; Voevoedin, V. V.; Tyrtyshnikov, E. E.; Garbow, B. S.; Boyle, J. M.; Cowell, W. R.; Dritz, K. W., The Toeplitz Package Users’ Guide, (Technical report (1983), Argonne National Laboratory)
[2] Bischof, C.; Van Loan, C., The WY representation for products of Householder matrices, SIAM J. Sci. Stat. Comput., 8, s2-s13 (1987) · Zbl 0628.65033
[3] Cabay, S.; Meleshko, R., A weakly stable algorithm for Padé approximants and the inversion of Hankel matrices, SIAM J. Matrix Anal. Appl., 14, 735-765 (1993) · Zbl 0779.65009
[4] Chan, T. F.; Hansen, P. C., A look-ahead Levinson algorithm for indefinite Toeplitz systems, SIAM J. Matrix Anal. Appl., 13, 490-506 (1992) · Zbl 0752.65020
[5] Chun, J.; Kailath, T.; Lev-Ari, H., Fast parallel algorithms for QR and triangular factorization, SIAM J. Sci. Stat. Comput., 8, 899-913 (1987) · Zbl 0632.65023
[6] Chun, J.; Kailath, T., Generalized Displacement Structure for Block Toeplitz, Toeplitz Block and Toeplitz Derived Matrices (1988), Informations Systems Lab., Stanford University: Informations Systems Lab., Stanford University CA · Zbl 0734.65020
[7] P. Concus and P. Saylor, A modified direct preconditioner for indefinite symmetric Toeplitz systems, Linear Algebra Appl.; P. Concus and P. Saylor, A modified direct preconditioner for indefinite symmetric Toeplitz systems, Linear Algebra Appl. · Zbl 0854.65023
[8] Cybenko, G.; Berry, M., Hyperbolic Householder algorithms for factoring structured matrices, SIAM J. Matrix Anal. Appl., 11, 499-520 (1990) · Zbl 0726.65025
[9] Delosme, J.-M.; Ipsen, I. C.F.; Paige, C. C., The Cholesky Factorization, Schur Complements, Correlation Coefficients, Angles between Vectors, and the QR Factorization, (Technical report (1988), Yale University)
[10] Delsarte, Ph.; Genin, Y.; Kamp, Y., Pseudo-Carathéodory functions and Hermitian Toeplitz matrices, Philips J. Res., 41, 1-54 (1986) · Zbl 0607.30033
[11] Eldén, L.; Park, H., Accurate Least Squares Solutions for Toeplitz Matrices, (Technical report (1994), Linkoping University: Linkoping University Sweden) · Zbl 0808.65041
[12] Freund, R. W.; Zha, H., Formally biorthogonal polynomials and a look-ahead Levinson algorithm for general Toeplitz systems, Linear Algebra Appl., 188, 255 (1993) · Zbl 0777.65011
[13] Gallivan, K.; Thirumalai, S.; Van Dooren, P., On Solving Block Toeplitz Matrices Using a Block Schur Algorithm, (Proceedings, 1994 International Conference on Parallel Processing. Proceedings, 1994 International Conference on Parallel Processing, Technical report (1994), CSRD, University of Illinois at Urbana-Champaign), 274-281, a shorter version appears in · Zbl 0826.65017
[14] Gallivan, K.; Thirumalai, S.; Van Dooren, P., A block Toeplitz look-ahead Schur algorithm, (Moonen, M.; De Moor, B., SVD in Signal Processing III, Algorithms, Architectures and Applications (1995), Elsevier: Elsevier Amsterdam), 199-206 · Zbl 0826.65017
[15] Gohberg, I.; Kailath, T.; Olshevsky, V., Gaussian Elimination with Partial Pivoting for Structured Matrices, (Technical report (1994), Information Systems Lab., Stanford University) · Zbl 0848.65010
[16] Golub, Gene H.; Van Loan, Charles F., Matrix Computations (1989), John Hopkins Univ. Press · Zbl 0733.65016
[17] Gutknecht, M., A completed theory of the unsymmetric Lanczos process and related algorithms, ii, SIAM J. Matrix Anal. Appl., 15, 15-58 (1994) · Zbl 0809.65028
[18] Gutknecht, M.; Hochbruck, M., Look-Ahead Levinson and Schur Algorithms for Non-Hermitian Toeplitz Systems, (Technical report (1994), IPS, ETH Zurich) · Zbl 0823.65023
[19] Hansen, P. C.; Chan, T. F., FORTRAN subroutines for general Toeplitz systems, ACM Trans. Math. Software, 18, 3, 256-273 (1992) · Zbl 0894.65010
[20] Hansen, P. C.; Gesmar, H., Fast orthogonal decomposition of rank deficient Toeplitz matrices, Num. Algorithms, 4, 151-166 (1993) · Zbl 0779.65027
[21] Heinig, G., Inversion of generalized Cauchy matrices and other classes of structured matrices, (Bojanczyk, A.; Cybenko, G., Linear Algebra for Signal Processing. Linear Algebra for Signal Processing, The IMA Volumes in Mathematics and its Applications, Vol. 69 (1995), Springer-Verlag) · Zbl 0823.65020
[22] Kailath, T.; Sayed, A., Fast algorithms for generalized displacement structures, (Kimura, H.; Kodoma, S., Recent Advances in Mathematical Theory of Systems. Recent Advances in Mathematical Theory of Systems, Proc. MTNS-91 (1992)), 27-32
[23] Kailath, T.; Kung, S.-Y.; Morf, M., Displacement ranks of matrices and linear equations, J. Math. Appl., 68, 395-407 (1979) · Zbl 0433.15001
[24] Pal, D.; Kailath, T., Fast triangular factorization and inversion of Hermitian, Toeplitz related matrices with arbitrary rank profile, SIAM J. Matrix Anal. Appl., 14, 4, 1016-1042 (1993) · Zbl 0787.65013
[25] Parlett, B., Reduction to tridiagonal form and minimal realizations, SIAM J. Matrix Anal. Appl., 13, 567-593 (1992) · Zbl 0754.65040
[26] Rader, C. M.; Steinhardt, A. O., Hyperbolic Householder transformations, IEEE Trans. Acoust. Speech Signal Process., 34, 1589-1602 (1986) · Zbl 0629.93063
[27] Rader, C. M.; Steinhardt, A. O., Hyperbolic Householder transforms, SIAM J. Matrix Anal. Appl., 9, 269-290 (1988) · Zbl 0647.65027
[28] Sayed, A.; Kailath, T., A look-ahead block Schur algorithm for Toeplitzlike matrices, SIAM J. Matrix Anal. Appl., 16, 2 (1995) · Zbl 0824.65010
[29] Schreiber, R.; Van Loan, C., A storage-efficient WY representation for products of Householder transformations, SIAM J. Sci. Stat. Comput., 10, 1, 53-57 (1989) · Zbl 0664.65025
[30] Schur, I., Uber potenzreihen die im Inneren des Einheitskreises beschrankt sind, J. Reine Angew. Math., 147, 205-232 (1917) · JFM 46.0475.01
[31] Stewart, M.; Van Dooren, P., Stability Issues in the Factorization of Structured Matrices, (Technical report (1994), CSRD, University of Illinois at Urbana-Champaign), Submitted for publication · Zbl 0884.65023
[32] Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Oxford Univ. Press: Oxford Univ. Press Oxford, England · Zbl 0258.65037
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.