AN ALGORITHM AND ARCHITECTURE BASED ON ORTHONORMAL MU-ROTATIONS FOR COMPUTING THE SYMMETRICAL EVD

In this paper an algorithm and architecture for computing the eigenval ue decomposition (EVD) of a symmetric matrix is presented. The EVD is computed using a Jacobi-type method, where the angle of the rotations is approximated by an angle alpha(k), corresponding to an orthonormal mu-rotation. These orthonormal mu-rotations are based on the idea of C ORDIC and share the property that performing the rotation requires a m inimal number of shift-add operations. We present various methods of c onstruction for such orthonormal mu-rotations of increasing complexity . Moreover, the computations to determine which angle alpha(k) to use in the approximation of the optimal angle, can itself be expressed pur ely in orthonormal mu-rotations on the matrix data. The complexity of the used type of orthonormal mu-rotation decreases during the diagonal ization of the matrix. A significant reduction of the number of requir ed shift-add operations is achieved. All types of fast, orthonormal mu -rotations (and the computation to determine the optimal angle) can be implemented as a cascade of only four basic types of shift-add stages . These stages can be executed on a modified sequential floating-point CORDIC architecture, making the presented algorithm highly suited for VLSI-implementation.