ALGORITHM 730 - AN IMPLEMENTATION OF A DIVIDE-AND-CONQUER ALGORITHM FOR THE UNITARY EIGENPROBLEM (VOL 20, PG 161, 1994)

We present a FORTRAN implementation of a divide-and-conquer method for computing the spectral resolution of a unitary upper Hessenberg matri x 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 s uch as in signal processing and in the computation of Gauss-Szego quad rature rules. Our programs utilize the Schur parametrization to comput e the spectral decomposition of H without explicitly forming the eleme nts of H. If only the eigenvalues and first components of the eigenvec tors are desired, as in the applications mentioned above, the algorith m requires only O(n2) arithmetic operations. Experimental results pres ented 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.