PARALLEL ALGORITHMS TO COMPUTE THE EIGENVALUES AND EIGENVECTORS OFSYMMETRIC TOEPLITZ MATRICESFootnote∗

∗This paper was partially supported by the CICYT project TIC96-1062-C03: “Parallel Algorithms for the computation of the eigenvalues of sparse and structured malrices”

References

• G. Ammar and W. Graag , Superfast solution of real positive definite Toeplitz systems , SIAM J. Matrix Anal. Appl. , 9 ( 1988 ), 61 – 76 .
   Web of Science ®Google Scholar
• J.M. Badia , Algoritmos Paralelos para el Calculo dc los Valores Propios de Matrices Estructuradas , Ph.D. Thesis , Univ. Politécnica de Valencia ( 1996 ) .
   Google Scholar
• J.M. Badia A.M. Vidal Parallel bisection algorithms for solving the symmetric tridiagonal eigenproblem , in High Performance Algorithms for Structured Matrix Problems , P. Arbenz, M. Paprzycki and A. Sameh Eds. (to appear) .
   Google Scholar
• J.M. Badia and A.M. Vidal , Algoritmos Paralelos para el Calculo de los Valores y Vectores Propios de Matrices Toeplitz Simetricas en una Red de Transputers , DSIC-II/48/93, Dpt. Sistemas Inform´ticos y Computacion . Universidad Politécnica de Valencia ( 1993 ) .
   Google Scholar
• J.M. Badia and A.M. Vidal , Divide and conquer algorithms to solve the eigenproblem of symmetric Toeplitz matrices on multicomputers , DSIC-II/2/94 , Dpt. Sistemas Inform´ticos y Computacion. U.P.V. ( 1994 ).
   Google Scholar
• J.M. Badia and A.M. Vidal , Parallel computation of the eigenstructure of Toeplitz-plus-Hankel matrices on multicomputers , in Lecture Notes in Computer Science , vol. 879 , Jack Dongarra and Jerzy Wasniewski Eds ., Springer-Verlag ( 1994 ) , 33 – 40 .
   Google Scholar
• J.M. Badia and A.M. Vidal , Efficient solution of the eigenproblem of banded symmetric Toeplitz matrices on multicomputers, 3rd . Euromicro Workshop on Parallel and Distributed Processing ( San Remo , Italy , 1995 ), 416 – 423 .
   Google Scholar
• G. Baker , Accelerated bisection techniques for tri- and quintadiagonal matrices , Int. J. for Num. Meth. in Eng. , 35 ( 1992 ), 203 – 218 .
   Google Scholar
• R.H. Barlow and D.J. Evans , Aparallel organization of the bisection algorithm , Comput. J. , 22 ( 1977 ). 267 – 269 .
   Google Scholar
• A. Baserman and P. Weidner , A parallel algorithm for determining all eigenvalues of large real symmetric tridiagonal matrices , Parallel Computing , 18 ( 1992 ), 1129 – 1141 .
   Google Scholar
• H.J. Bernstein , An accelerated bisection method for the calculation of eigenvalues of a symmetric tridiagonal matrix , Numer. Math. , 43 ( 1984 ), 153 – 160 .
   Google Scholar
• H.J. Bernstein and M. Goldstein , Parallel implementation of bisection for the calculation of eigenvalues of tridiagonal symmetric matrices , Computing , 37 ( 1986 ), 85 – 91 .
   Web of Science ®Google Scholar
• D. Bini and M. Capovani , Spectral and computational properties of banded symmetric Toeplitz matrices , Lin. Alg. Appl , 52 – 53 ( 1983 ), 99 – 126 .
   Google Scholar
• D. Bini and F. Di Benedetto , Solving the generalized eigenvalue problem'for rational Toeplitz matrices , SIAM J. Matrix Anal. Appl. , 11 ( 4 ) ( 1990 ), 537 – 552 .
   Web of Science ®Google Scholar
• D. Bini and B. Mcini , On cyclic reduction applied to a class of Toeplitz-like matrices arising in queuing problems , Second International Workshop on Numerical Solutions of Markov Chains ( Raleigh , N.C ., 1995 ), 21 – 38 .
   Google Scholar
• R. Bitmead and B. Anderson , Asymptotically fast solution of Toeplitz and related systems of equations , Lin. Alg. Appl. , 34 ( 1980 ), 103 – 116 .
   Web of Science ®Google Scholar
• R.P. Brent , F.G. Gustavson and D.Y.Y. Yun , Fast solution of Toeplitz systems of equations and computation of Pade approximants , Journal of Algorithms , 1 ( 1980 ), 259 – 295 .
   Google Scholar
• J. Bunch , Stability of methods for solving Toeplitz systems of equations , SIAM J. Sci. Stat. Comp. , 6 ( 1985 ), 349 – 364 .
   Web of Science ®Google Scholar
• J.R. Bunch , The weak and strong stability of algorithms in numerical linear algebra , Lin. Alg. Appl. , 88 – 89 ( 1987 ), 49 – 66 .
   Google Scholar
• A. Cantoni and F. Butler , Eigenvalues and eigenvectors of symmetric centrosymmetric matrices , Lin. Alg. Appl. , 13 ( 1976 ), 275 – 288 .
   Web of Science ®Google Scholar
• G. Cybenko , On the eigenstructure of Toeplitz matrices , IEEE Trans. Aco., Spe. Sig. Proc , ASSP-32( 4 ) ( 1984 ), 918 – 921 .
   Google Scholar
• G. Cybenko and C. Van Loan , Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix , SIAM J. Sci. Slat. Comp. , 7 ( 1 ) ( 1986 ), 123 – 130 .
   Web of Science ®Google Scholar
• M. Dowell and P. Jaratt , The Pegasus method for computing the root of an equation , BIT , 12 ( 1972 ), 503 – 508 .
   Google Scholar
• R.W. Freund and H. Zha , Formally biorthogonal polynomials and a look-ahead Levinson algorithm for general Toeplitz systems , Linear Algebra and its Applications , 188 – 189 ( 1993 ), 255 – 303 .
   Google Scholar
• J.W. Givens , A method of computing eigenvalues and eigenvectors suggested by classical results on symmetric matrices , U.S. Nat. Bur. Standards Applied Mathematics Series , 29 ( 1953 ), 117 – 122 .
   Google Scholar
• G.H. Golub and C.F. Van Loan , Matrix Computations , Johns Hopkins University Press , 1989 .
   Google Scholar
• U. Grenander and G. Szego , Toeplitz Forms and their Application , Chelsea Eds. , New York , ( 1984 ) ,
   Google Scholar
• Gutknecht , Stable row recurrences for the Padée table and generically superfast lookahead solvers for non-Hermitian Toeplitz systems , Lin. Alg, Appl. , 188 – 89 ( 1993 ), 351 – 422 .
   Google Scholar
• M.H. Hayes and M.A. Clements , An efficient algorithm for computing Pisarenko's harmonic decomposition using Levinson's recursion , IEEE Trans. Acoust. Speech Signal Process. , ASSP-34 ( 1986 ), 485 – 491 .
   Google Scholar
• Y.H. Hu and S.Y. Kung , Toeplitz eigensystem solver , IEEE Trans. Aco.. Spe. Sig. Proc. , ASSP-33( 4 ) ( 1985 ), 1264 .
   Google Scholar
• I.C.F. Ipsen and E.R. Jessup , Solving the symmetric tridiagonal eigenvalue problem on the hypercube , SIAM J. Sci. Stat. Comp. , 11 (|i2|) ( 1990 ), 203 – 229 .
   Google Scholar
• E. Jonckheere and C. Ma , Combined sequence of Markov parameters and moments in linear systems , IEEE Trans. Automat. Control , AC-34 ( 1989 ), 379 – 382 .
   Google Scholar
• M. Kac , L. Murdock and G. Szego , On the eigenvalues of certain Hermitian forms , J. Rat. Mech. Anal. , 2 ( 1953 ), 757 – 800 .
   Google Scholar
• W. Kalian and J. Varah , Two working algorithms for the eigenvalues of a symmetric tridiagonal matrix , CS43, Stanford University , 1966 .
   Google Scholar
• T. Kailath , A view of three decades of linear filtering theory , IEEE Trans. Inform. Theory , IT-20 ( 1974 ), 146 – 181 .
   Web of Science ®Google Scholar
• T.Z. Kalamboukis , The symmetric tridiagonal eigenvalue problem on a transputer network , Parallel Computing , 15 ( 1990 ), 101 – 106 .
   Google Scholar
• H. Lev-Ari and T. Kailath , State-space approach to factorization of lossless transfer functions and structured matrices , Lin. Alg. Appl. , 162 – 164 ( 1992 ), 273 – 295 .
   Google Scholar
• N. Levinson , The Weiner RMS (root mean square) error criterion in filter design and prediction , Math. Phys. , 25 ( 1947 ), 261 – 278 .
   Web of Science ®Google Scholar
• B.C. Levy , M.B. Adams and A.S. Willsky , Solution and linear estimation of a 2-D nearest neighbor model , Proc. IEEE , 78 ( 1990 ), 627 – 641 .
   Web of Science ®Google Scholar
• S.S. Lo , B. Philippe and A. Sameh , A multiprocessor algorithm for the symmetric tridiagonal eigenvalue problem , SIAM J. Sci. Stat. Comp. , 8 ( 2 ) ( 1987 ), psl55–s165 p.
   Google Scholar
• J. Makhoul , Linear prediction A tutorial review , Proc. IEEE , 63 ( 1975 ), 561 – 580 .
   Web of Science ®Google Scholar
• R.M.S. Ralha , Parallel solution of the symmetric tridiagonal eigenvalue problem on a transputer network , SEMNI93 , Vol. 2 ( La Coruna , Espana , 1993 ), 1026 – 1033 .
   Google Scholar
• W.F. Trench , Numerical solution of the eigenvalue problem for symmetric rationally generated Toeplitz matrices , SIAM J. Matrix Anal. Appl. , 9 ( 2 ) ( 1988 ), 291 – 303 .
   Web of Science ®Google Scholar
• W.F. Trench , Numerical solution of the eigenvalue problem for Hermitian Toeplitz matrices , SIAM J. Matrix Anal. Appl. , 10 ( 2 ) ( 1989 ), 135 – 146 .
   Web of Science ®Google Scholar
• W.F. Trench , Numerical solution of the eigenvalue problem for efficiently structured Hermitian matrices , Lin. Alg. Appl. , 154 – 156 ( 1991 ), 415 – 432 .
   Google Scholar
• W.F. Trench , Interlacement of the even and odd spectra of real symmetric Toeplitz matrix , Lin. Alg. Appl. , 195 ( 1993 ), 59 – 68 .
   Google Scholar
• ∗This paper was partially supported by the CICYT project TIC96-1062-C03: “Parallel Algorithms for the computation of the eigenvalues of sparse and structured malrices”
   Google Scholar