Corrigendum: Algorithm 730: An implementation of a divide and conquer algorithm for the unitary eigenproblem

ABSTRACT

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.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing

General Terms:
Algorithms

Keywords:
fast algorithm, unitary eigenvalue problem