A divide and conquer method for unitary and orthogonal eigenproblems
Abstract
Let H epsilon C be a unitary upper Hessenberg matrix whose eigenvalues, and possibly also eigenvectors, are to be determined. We describe how this eigenproblem can be solved by a divide and conquer method, in which the matrix H is split into two smaller unitary right Hessenberg matrices H1 and H2 by a rank-one modification of H. The eigenproblems for H1 and H2 can be solved independently, and the solutions of these smaller eigenproblems define a rational function, whose zeros on the unit circle are the eigenvalues of H. The eigenvectors of H can be determined from the eigenvalues of H and the eigenvectors of H1 and H2. The outlined splitting of unitary upper Hessenberg matrices into smaller such matrices is carried out recursively. This gives rise to a divide and conquer method that is suitable for implementation on a parallel computer. When H epsilon R sub nxn is orthogonal, the divide and conquer scheme simplifies and is described separately. Our interest in the orthogonal eigenproblem stems from applications in signal processing. Numerical examples for the orthogonal eigenproblem conclude the paper
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.NPS Report Number
NPS-53-89-007Related items
Showing items related by title, author, creator and subject.
-
Constructing a unitary Hessenberg matrix from spectral data
Gragg, William B.; Ammar, Gregory S.; Reichel, Lother (Monterey, California. Naval Postgraduate School, 1988-11); NPS-53-89-005We consider the numerical construction of a unitary Hessenberg matrix from spectral data using an inverse QR algorithm. Any unitary upper Hessenberg matrix H with nonnegative subdiagonal elements can be represented by 2n ... -
Expeditionary Mine Countermeasures (ExMCM) C4I Requirements (Continuation)
Das, Arijit (Monterey, California: Naval Postgraduate SchoolMonterey, California. Naval Postgraduate School, 2019-12); NPS-19-N065-AThe ExMCM is a broad program providing an innovative approach to the Mine Warfare mission area, required to operate with both U.S Navy and U.S. Marine Corps forces. The large number of sonar imagery files (from the MK18 ... -
A parallel divide and conquer algorithm for the generalized real symmetric definite tridiagonal eigenproblem
Borges, Carlos F.; Gragg, William B. (Monterey, California. Naval Postgraduate School, 1993); NPS-MA-93-009We develop a parallel divide and conquer algorithm, by extension, for the generalized real symmetric definite tridiagonal eigenproblem. The algorithm employs techniques first proposed by Gu and Eisenstat to prevent loss ...