UDC

Algorithm 730. An implementation of a divide and conquer algorithm for the unitary eigenproblem. We present a FORTRAN implementation of a divide-and-conquer method for computing the spectral resolution of a unitary upper Hessenberg matrix H. Any such matrix H of order n, normalized so that its subdiagonal elements are nonnegative, can be written as a product of n−1 Givens matrices and a diagonal matrix. This representation, which we refer to as the Schur parametric form of H, arises naturally in applications such as in signal processing and in the computation of Gauss-Szego quadrature rules. Our programs utilize the Schur parametrization to compute the spectral decomposition of H without explicitly forming the elements of H. If only the eigenvalues and first components of the eigenvectors are desired, as in the applications mentioned above, the algorithm requires only O(n2) arithmetic operations. Experimental results presented indicate that the algorithm is reliable and competitive with the general QR algorithm applied to this problem. Moreover, the algorithm can be easily adapted for parallel implementation


References in zbMATH (referenced in 19 articles )

Showing results 1 to 19 of 19.
Sorted by year (citations)

  1. Fasi, Massimiliano; Robol, Leonardo: Sampling the eigenvalues of random orthogonal and unitary matrices (2021)
  2. Kuian, Mykhailo; Reichel, Lothar; Shiyanovskii, Sergij: Optimally conditioned Vandermonde-like matrices (2019)
  3. Aurentz, Jared L.; Mach, Thomas; Vandebril, Raf; Watkins, David S.: Fast and stable unitary QR algorithm (2015)
  4. Calvetti, D.; Reichel, L.; Xu, H.: A CS decomposition for orthogonal matrices with application to eigenvalue computation (2015)
  5. Cruz-Barroso, Ruymán; Delvaux, Steven: Orthogonal Laurent polynomials on the unit circle and snake-shaped matrix factorizations (2009)
  6. David, Roden J. A.; Watkins, David S.: An inexact Krylov-Schur algorithm for the unitary eigenvalue problem (2008)
  7. Delvaux, Steven; Van Barel, Marc: Eigenvalue computation for unitary rank structured matrices (2008)
  8. Milovanović, Gradimir V.; Cvetković, Aleksandar S.; Stanić, Marija P.: Trigonometric orthogonal systems and quadrature formulae (2008)
  9. Jagels, Carl; Reichel, Lothar: Szegő-Lobatto quadrature rules (2007)
  10. Kim, Sun-Mi; Reichel, Lothar: Anti-Szegő quadrature rules (2007)
  11. Gemignani, Luca: A unitary Hessenberg (QR)-based algorithm via semiseparable matrices (2005)
  12. Calvetti, Daniela; Kim, Sun-Mi; Reichel, Lothar: The restarted QR-algorithm for eigenvalue computation of structured matrices (2002)
  13. Ammar, G. S.; Calvetti, D.; Gragg, W. B.; Reichel, L.: Polynomial zerofinders based on Szegő polynomials (2001)
  14. Bunse-Gerstner, A.; Faßbender, H.: Error bounds in the isometric Arnoldi process (1997)
  15. Ammar, G. S.; Calvetti, D.; Reichel, L.: Continuation methods for the computation of zeros of Szegő polynomials (1996)
  16. Ammar, G. S.; Reichel, L.; Sorensen, D. C.: Corrigendum: Algorithm 730. An implementation of a divide and conquer algorithm for the unitary eigenproblem (1994)
  17. Elsner, Ludwig; He, Chunyang: Perturbation and interlace theorems for the unitary eigenvalue problem (1993)
  18. Jagels, Carl; Reichel, Lothar: On the construction of Szegő polynomials (1993)
  19. Ammar, G. S.; Reichel, L.; Sorensen, D. C.: An implementation of a divide and conquer algorithm for the unitary eigenproblem (1992)