Linear or Square Array for Eigenvalue and Singular Value Decompositions?
Abstract
For many signal and image processing applications, such as high resolution spectral estimation, image data compression etc., eigenvalue and singular value decompositions have emerged as extremely powerful and efficient computational tools. As far as the symmetric eigenvalue problem is concerned, QL and QR algorithms ... have emerged as the most effective way of finding all the eigenvalues of a small symmetric matrix. A full matrix is first reduced to tridiagonal form by a sequence of reflections and then the QL (QR) algorithm swiftly reduces the off diagonal elements until they are negligible. The algorithm repeatedly applies a complicated similarity transformation to the result of the previous transformation, thereby producing a sequence of matrices that converges to a diagonal form. What is more, the tridiagonal form is preserved. Therefore, the QR algorithm can be regarded as the best sequential algorithm available to date. The question is whether or not the QR algorithm may retain that same effectiveness when mapped into a parallel algorithm on a square or linear multiprocessor array. In this note, the authors offer an answer to this question using the computational wavefront notion.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1983
- Accession Number
- ADP002612
Entities
People
- R. J. Gal-ezer
- Sun Yuan Kung
Organizations
- University of Southern California