Hardware efficient architectures for eigenvalue computation

ABSTRACT

Eigenvalue computation is essential in many fields of science and engineering. For high performance and real-time applications, this may need to be done in hardware. This paper focuses on the exploration of hardware architectures which compute eigenvalues of symmetric matrices. We propose to use the Approximate Jacobi Method for general case symmetric matrix eigenvalue problem. The paper illustrates that the proposed architecture is more efficient than previous architectures reported in the literature. Moreover, for the special case of 3 x 3 symmetric matrices, we propose to use an Algebraic Method. It is shown that the pipelined architecture based on the Algebraic Method has a significant advantage in terms of area.

REFERENCES

• 1: G. Farneback, "Fast and accurate motion estimation using orientation tensors and parametric motion models," ICPR Proceedings, vol. 1, pp. 135 -- 139, 2000.
• 2: R. P. Brent, F. T. Luk, and C. Van Loan, "Computation of the singular value decomposition using mesh-connected processors.," Journal of VLSI and Computer Systems, vol. 1, no. 3, pp. 242 -- 270, 1985.
• 3: M. Kim, K. Ichige, and H. Arai, "Design of Jacobi EVD processor based on CORDIC for DOA estimation with MUSIC algorithm," PIMRC Proceedings, vol. 1, pp. 120 -- 4, 2002.
• 4: A. Ahmedsaid, A. Amira, and A. Bouridane, "Improved SVD systolic array and implementation on FPGA," FPT Proceedings, pp. 35 -- 42, 2003.
• 5: J. Gotze , S. Paul , M. Sauer, An Efficient Jacobi-Like Algorithm for Parallel Eigenvalue Computation, IEEE Transactions on Computers, v.42 n.9, p.1058-1065, September 1993 [doi>10.1109/12.241595]
• 6: Waerden and B. L. van der, Algebra. New York; London: Springer-Verlag, 1991. translated by Fred Blum and John R. Schulenberger. Vol.1.
• 7: G. H. Golub and C. F. Van Loan, Matrix computations. Baltimore; London: Johns Hopkins University Press, 3rd ed., 1996.
• 8: J.-M. Delosme, "CORDIC algorithms: theory and extensions," Proceedings of the SPIE - The International Society for Optical Engineering, vol. 1152, pp. 131 -- 45, 1989.
• 9: David M. Mandelbaum, A method for calculation of the square root using combinatorial logic, Journal of VLSI Signal Processing Systems, v.6 n.3, p.233-242, Dec. 1993 [doi>10.1007/BF01608536]