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

• Published in: Integration (Amsterdam) 1995-12, Vol.20 (1), p.21-39
• Main Authors: Götze, Jürgen, Hekstra, Gerben J.
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Approximate rotations; Computer science; control theory; systems; Eigenvalue decomposition (EVD); Electronics; Exact sciences and technology; Floating-point CORDIC architecture; Integrated circuits; Jacobi method; Orthonormal μ-rotations; Semiconductor electronics. Microelectronics. Optoelectronics. Solid state devices; Theoretical computing
• ISSN: 0167-9260; 1872-7522
• DOI: 10.1016/0167-9260(95)00016-X

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 α κ , corresponding to an orthonormal μ-rotation. These orthonormal μ-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 contsruction for such orthonormal μ-rotations of increasing complexity. Moreover, the computations to determine which angle α κ to use in the approximation of the optiimal angle, can itself be expressed purely in orthonormal μ-rotations on the matrix data. The complexity of the used type of orthonormal μ-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 μ-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.