2389
Comment: converted to 1.6 markup

← Revision 5 as of 20140310 04:03:33 ⇥
0
useless page

Deletions are marked like this.  Additions are marked like this. 
Line 1:  Line 1: 
In Hama, we use [[http://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithmJacobieigenvalue algorithm]] to calculate all eigenvalues and eigenvectors of a real symmetric matrix. = Description = Let A be a symmetric matrix, and G = G(i,j,θ) be a Givens rotation matrix. Then: A'=G^T A G , is symmetric and similar to A. As they are similar, A and A′ have the same Frobenius norm ·F (the sum of squares of all components), however we can choose θ such that A′(ij) = 0, in which case A′ has a larger sum of squares on the diagonal: A'(ij) = cos(2 * θ) * A(ij) + (1/2) * sin(2 * θ) * (A(ii)  A(jj)) Set this equal to 0, and rearrange: tan(2 * θ) = (2 * A(ij)) / (A(jj)  A(ii)) In order to optimize this effect, A(ij) should be the largest offdiagonal component, called the pivot. The Jacobi eigenvalue method repeatedly finds the pivot and performs rotations until the matrix becomes almost diagonal. Then the elements in the diagonal are approximations of the (real) eigenvalues of A. = Methods = The implementation of Jacobi eigenvalue method in Hama are described as below: 1. Find the pivot: Get the largest offdiagonal element of the matrix. We use a M/R job to find the pivot p and its index in the matrix(pivot_row, pivot_col). These are all done in !PivotMapper and !PivotReducer. 1.#2 Compute the rotation parameters. 1. Rotate the matrix using the rotation matrix. As the rotation matrix is a 2X2 matrix, each rotation just effects 4 elements of the matrix. The rotations can not effect each other, so we can do the rotations parallely. The Pseudocode described as below: i. for i := 1 to k−1 do rotate(i,k,i,l) endfor i. for i := k+1 to l−1 do rotate(k,i,i,l) endfor i. for i := l+1 to n do rotate(k,i,l,i) endfor Rotate(k,l,i,j):(''S'' is the matrix, ''c & s'' is the parameters of the rotation matrix computed in step 2) S(kl) = c * S(kl)  s * S(ij) S(ij) = s * S(kl) + c * S(ij) The Implementation of M/R job to rotate the matrix is a tricky. We do not rotate the matrix actually in Mapper & Reducer. We do this rotation during we scan over the matrix table. Plz check the code in !RotationInputFormat. 1.#4 Rotate the eigenvectors matrix. 1. Repeats until the matrix becomes almost diagonal, or the loops reach the limit specified by the user. 