Accession Number : ADP002612

Title :   Linear or Square Array for Eigenvalue and Singular Value Decompositions?

Corporate Author : UNIVERSITY OF SOUTHERN CALIFORNIA LOS ANGELES DEPT OF ELECTRICAL ENGINEERING

Personal Author(s) : Kung,S. Y. ; Gal-Ezer,R. J.

Report Date : 1983

Pagination or Media Count : 10

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.

Descriptors :   *Algorithms, *Linear arrays, *Multiprocessors, Eigenvalues, Matrices(Mathematics), Computations, Wavefronts

Distribution Statement : APPROVED FOR PUBLIC RELEASE