An implementation of a divide and conquer algorithm for the unitary eigen problem

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. —Authors' Abstract

REFERENCES

• 1: AMMAR, G. S., GRAGG, W. B., AND REICHEL, L. Determination of Pisarenko frequency estimates as eigenvalues of an orthogonal matrix. In Advanced Algorithms and Architectures for Signal Processing H, SPIE vol. 826, F. Luk, Ed., 1987, pp. 143-145.
• 2: Peter Arbenz , Gene H. Golub, On the spectral decomposition of Hermitian matrices modified by low rank perturbations, SIAM Journal on Matrix Analysis and Applications, v.9 n.1, p.40-58, Jan. 1988 [doi>10.1137/0609004]
• 3: CUPPEN, J. J.M. A divide and conquer method for the symmetric tridiagonal eigenproblem. Numer. Math. 36 (1981), 177 195.
• 4: J. J. Dongarra , D. C. Sorensen, A fully parallel algorithm for the symmetric eigenvalue problem, SIAM Journal on Scientific and Statistical Computing, v.8 n.2, p.139-154, March 1, 1987 [doi>10.1137/0908018]
• 5: GRAGG, W.B. Positive definite Toeplitz matrices, the Arnoldi process for isometric operators and Gaussian quadrature on the unit circle (in Russian). In Numerical Methods tn Ltnear Algebra, E. S. Nikolaev, Ed., Moscow Univ. Press, Moscow, 1982, 16-32.
• 6: GRAGG, W. B., AND REICHEL, L. A divide and conquer algorithm for the unitary eigenproblem. In Hypercube Multiprocessors 1987, M. T. Heath, Ed., SIAM, Philadelphia, 1987, 639-647.
• 7: GRAGG, W. B., AND REICHEL, L. A divide and conquer method for unitary and orthogonal eigenproblems. Numer. Math. 57 (1990), 695-718.
• 8: GRENANDER, U., AND SZEG6, G. Toeplitz Forms and Their Applications. Chelsea, New York, 1984.
• 9: Lise C. F. Ipsen , Elizabeth R. Jessup, Solving the symmetric tridiagonal eigenvalues problem on the hypercube, SIAM Journal on Scientific and Statistical Computing, v.11 n.2, p.203-229, March 1990 [doi>10.1137/0911013]
• 10: JONES, W. B., NJ~STAD, O., AND THRON, W. J. Moment theory, orthogonal polynomials, quadrature, and continued fractions associated with the unit circle. Bull. London Math. Soc. 21 (1989), 113-152.
• 11: A S Krishnakumar , M Morf, Eigenvalues of a symmetric tridiagonal matrix: A divide-and-conquer approach, Numerische Mathematik, v.48 n.3, p.349-368, March. 1986 [doi>10.1007/BF01389480]
• 12: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 13: REICHEL, L., AND AMMAR, G. S. Fast approximation of dominant harmonics by solving an orthogonat eigenvalue problem. In Mathematics in Signal Processing' H, J. G. McWhirter, Ed., Clarendon Press, Oxford, 1990, 575 591.
• 14: SMITH, B. T., BOYLE, J. M., IK~BE, Y., KLEMA, V. C., AND MOLER, C.B. Matrix Eigensystem Routines EISPACK Guide. 2nd Ed., Springer, Berlin, 1970.
• 15: D. C. Sorensen , Ping Tak Peter Tang, On the orthogonality of eigenvectors computed by divide-and-conquer techniques, SIAM Journal on Numerical Analysis, v.28 n.6, p.1752-1775, Dec. 1991 [doi>10.1137/0728087]

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, Measurement, Performance, Reliability

Keywords:
fast algorithm, unitary eigenvalue problem