An algorithm and architecture based on orthonormal mu-rotations for computing the symmetric EVD

In this paper an algorithm and architecture for computing the eigenvalue 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 CORDIC and share the property that performing the rotation requires a minimal number of shift-add operations. We present various methods of construction 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 purely in orthonormal mu-rotations on the matrix data. The complexity of the used type of orthonormal mu-rotation decreases during the diagonalization of the matrix. A significant reduction of the number of required 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.