Research Of Eigenvalue Decomposition Implementation For Symmetric Matrix

Eigenvalue decomposition of Matrix is significant for many areas in both science research and engineering,such as principal component analysis,artificial vision and so on.So,it's very important that researching the hardware implementation of the eigenvalue decomposition and finding a better hardware implementation.In present algorithms of matrix eigenvalue decomposition,the power method is very suitable for sparse matrix and inverse power method is used to calculate the eigenvector if the eigenvalue of the matrix is calculated,while subspace iteration method is very suitable for calculate the eigenvalue of large sparse matrices as the extend of power method.For symmetric matrices,there are three methods to calculate their eigenvalue,Jacobi rotation method,one-side rotation method and QR method.Jacobi rotation method uses the matrix orthogonal transformation to diagonalize the matrix to calculate the eigenvalue,what's more it's very convenient to get the eigenvector of the corresponding eigenvalue.The one-side rotation method is the extend of the Jacobi method,it only uses the one-side rotation to calculate the square of the eigenvalue and then get the eigenvalue.The QR method is based on QR decomposition and it decomposes the matrix to a upper triangular matrix,then calculate the eigenvalue of the matrix.For the hardware implementation of Jacobi algorithm,two architectures are demonstrated after analysis:serial computing architecture and parallel computing architecture.Serial computing architecture is divided to two ways,first way:finding the max element of the non-diagonal elements of the matrix and then putting Jacobi rotation to the corresponding rows and columns,second way puts the Jacobi rotation to the rows and columns in turn according to the all over method.The parallel computing architecture is an array architecture,it is consisted with diagonal processing units and non-diagonal processing units,one processing unit process four matrix elements and exchange its data with the neighbor processing units.The CORDIC algorithm is used to transform theθangel rotation of the vector[x,y]to successive±arctan2^-i(i = 0,1,...b) angel rotation.Then one Jacobi rotation is transformed to the iterations of only adding and shifting flowed by a scaling.It is very suitable for the hardware implementation of the Jacobi algorithm.Two computing architectures were implemented by Verilog HDL with using CORDIC algorithm.The performance of these methods were compared after Verification and data collection.And finally,the parallel method is proved the best method to implement the Jacobi algorithm.