A divide and conquer method for unitary and orthogonal eigenproblems
Loading...
Authors
Gragg, William B.
Reichel, Lother
Subjects
unitary eigenproblem, orthogonal eigenproblem, divide and conquer, parallel algorithm, Pisarenko frequencies, Gauss-Szego quadrature.
Unitary eigenproblem
Orthogonal eigenproblem
Divide and conquer
Parallel algorithm
Pisarenko frequencies
Gauss-szego quadrature
Unitary eigenproblem
Orthogonal eigenproblem
Divide and conquer
Parallel algorithm
Pisarenko frequencies
Gauss-szego quadrature
Advisors
Date of Issue
1989-02
Date
1989-02
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
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
Type
Technical Report
Description
Series/Report No
Department
Mathematics
Identifiers
NPS Report Number
NPS-53-89-007
Sponsors
This report was prepared in conjunction with research conducted for
the National Science Foundation and for the Naval Postgraduate School
Research Council and funded by the Naval Postgraduate School Research
Council.
Funder
O&MN, Direct Funding
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
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.