Mailing-List: contact hama-commits-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: hama-dev@<incubator.apache.org>
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
From: Apache Wiki <wikidiffs@apache.org>
To: hama-commits@incubator.apache.org
Date: Fri, 10 Jul 2009 03:38:13 -0000
Message-ID: <20090710033813.4562.88195@eos.apache.org>
Subject: [Hama Wiki] Update of "EigenValuesAndEigenVectors" by SamuelGuo

Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Hama Wiki" for change notification.

The following page has been changed by SamuelGuo:
http://wiki.apache.org/hama/EigenValuesAndEigenVectors

------------------------------------------------------------------------------
- Describe EigenValuesAndEigenVectors here.
+ In Hama, we use [http://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm|Jacobi eigenvalue 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 off-diagonal 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 off-diagonal 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.
+