

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object gov.sandia.cognition.util.AbstractCloneableSerializable gov.sandia.cognition.math.matrix.decomposition.EigenvectorPowerIteration
@PublicationReference(author="Wikipedia", title="Power iteration", type=WebPage, year=2009, url="http://en.wikipedia.org/wiki/Power_iteration") public class EigenvectorPowerIteration
Implementation of the Eigenvector Power Iteration algorithm. The core
algorithm finds the eigenvector corresponding to the largestmagnitude
eigenvalue by repeated iteration from an initial guess: (v=A*v). The
rate of convergence of this algorithm is determined by the ratio of
successive eigenvalues. In practice, I usually see convergence to extremely
accurate estimates in less than ten iterations. Because this method only
involves a simple matrixvector multiplication, it can be readily used with
very large, sparse matrices (which is what Google does). The algorithm
requires that the input matrix ("A") be symmetric, but it will converge even
when there are negative eigenvalues, repeated eigenvalues, and (in my
experience) poorly conditioned matrices. The algorithm is known to have
convergence problems in some cases, but I have not seen them occur.
We have also provided another method that will estimate the eigenvectors
corresponding to the eigenvalues with the top "numEigenvectors" magnitudes.
This algorithm works by finding eigenvectors in sequence with the Power
Iteration algorithm and then subtracting the space spanned by the justfound
eigenvector: (A=Av*v'). Rinse, lather, repeat. Because of the subtraction,
this is not appropriate for large sparse matrices, as the result will almost
certainly be nonsparse. In practice, I have found this approach to be
MUCH more computationally efficient than using LAPACK to compute a full EVD
of a Matrix. However, we require that the matrix be symmetric (but can have
negative or repeated eigenvalues), whereas LAPACK can compute the EVD of a
general asymmetric real matrix.
Finally, we also provide a method for estimating the eigenvalue for a matrix
and eigenvector.
Field Summary  

static int 
DEFAULT_MAXIMUM_ITERATIONS
Default maximum iterations for power iteration, 100. 
static double 
DEFAULT_STOPPING_THRESHOLD
Default stopping threshold for power iteration, 1.0E5. 
Constructor Summary  

EigenvectorPowerIteration()
Creates a new instance of EigenvectorPowerIteration. 
Method Summary  

static double 
estimateEigenvalue(Matrix A,
Vector v)
Finds the eigenvalue associated with the given Matrix and eigenvector. 
static Vector 
estimateEigenvector(Vector initial,
Matrix A,
double stoppingThreshold,
int maxIterations)
Estimates the eigenvector corresponding to the largest magnitude eigenvalue. 
static ArrayList<Vector> 
estimateEigenvectors(Matrix A,
int numEigenvectors)
Estimates the top eigenvectors of the given matrix using the power iteration algorithm. 
static ArrayList<Vector> 
estimateEigenvectors(Matrix A,
int numEigenvectors,
double stoppingThreshold,
int maxIterations)
Estimates the top eigenvectors of the given matrix using the power iteration algorithm. 
Methods inherited from class gov.sandia.cognition.util.AbstractCloneableSerializable 

clone 
Methods inherited from class java.lang.Object 

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Field Detail 

public static final double DEFAULT_STOPPING_THRESHOLD
public static final int DEFAULT_MAXIMUM_ITERATIONS
Constructor Detail 

public EigenvectorPowerIteration()
Method Detail 

public static ArrayList<Vector> estimateEigenvectors(Matrix A, int numEigenvectors)
A
 The matrix to estimate the eigenvectors for. It must be symmetric.
It will be modified by the algorithm.numEigenvectors
 The number of eigenvectors to compute.
public static ArrayList<Vector> estimateEigenvectors(Matrix A, int numEigenvectors, double stoppingThreshold, int maxIterations)
A
 The matrix to estimate the eigenvectors for. It must be symmetric.
It will be modified by the algorithm.numEigenvectors
 The number of eigenvectors to compute.stoppingThreshold
 The stopping threshold for the power iteration algorithm. The
algorithm will stop its computation of an eigenvector when themaxIterations
 The maximum number of iterations for the power iteration algorithm.
public static Vector estimateEigenvector(Vector initial, Matrix A, double stoppingThreshold, int maxIterations)
initial
 Initial estimate of the eigenvector. This is generally a uniform
(constant nonzero) Vector.A
 The matrix to estimate the eigenvectors for. It must be symmetric.
It will be modified by the algorithm.stoppingThreshold
 The stopping threshold for the power iteration algorithm. The
algorithm will stop its computation of an eigenvector when themaxIterations
 The maximum number of iterations for the power iteration algorithm.
public static double estimateEigenvalue(Matrix A, Vector v)
A
 Matrix to estimate the eigenvalue of. May have negative, repeated,
positive, or zero eigenvaluesv
 Eigenvector associated with the unknown eigenvalue


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 