Reply to topic

Sorting of Eigenvalues and Eigen vectors in the EigenSolver

rajats
Registered Member
Posts
2
Karma
0
Hi

I am using the EigenSolver Class for computing the Eigenvectors and Eigenvalues (Specifically the dominant Eigenvector (Eigenvalue) ) for a given matrix.

My specific questions in this context are as follows :

1>>>>> Having browsed through the documentation of the EigenSolver class (http://eigen.tuxfamily.org/dox/classEig ... olver.html), I have reached the conclusion that the Eigenvalues (and Eigenvectors) returned by the EigenSolver::compute function are not sorted in any particular order. Is this correct?

2>>>> If the answer to the previous question is yes, given the fact that most real world applications of Eigendecomposition are generally concerned with using the dominant Eigenvector (Eigenvalue) for further computation, is it not a bit strange that the output from the EigenSolver::compute is not sorted.

cheers
jitseniesen
Registered Member
Posts
186
Karma
2
rajats wrote:1>>>>> Having browsed through the documentation of the EigenSolver class (http://eigen.tuxfamily.org/dox/classEig ... olver.html), I have reached the conclusion that the Eigenvalues (and Eigenvectors) returned by the EigenSolver::compute function are not sorted in any particular order. Is this correct?

2>>>> If the answer to the previous question is yes, given the fact that most real world applications of Eigendecomposition are generally concerned with using the dominant Eigenvector (Eigenvalue) for further computation, is it not a bit strange that the output from the EigenSolver::compute is not sorted.


1. Correct.
2. One problem is depending on the situation (basically, continuous versus discrete time), the dominant eigenvalue can be the one with the largest magnitude or the largest real part. Another problem is the sort order is not specified completely. Yet another problem is that we do not want to harm the performance of those users who do not want to sort eigenvalues are in the minority (though that may not be very convincing). However, perhaps we should make it easier to get the dominant eigenvalue/vector.
rajats
Registered Member
Posts
2
Karma
0
I believe that the "Power iteration" can be used to compute the dominant eigenvector (eigenvalue) for a given matrix. Is there an implementation of this method in Eigen?
User avatar ggael
Moderator
Posts
2195
Karma
15
OS
indeed, to compute only the dominants eigenvalues/vectors, you need totally different algorithms than the ones implemented in *EigenSolver. For the inspiration a naive power iteration algorithm:

Code: Select all
template<typename Mat, typename Vec>
typename Mat::Scalar power(const Mat& m, Vec& y)
{
  typedef typename Mat::Scalar Scalar;
  int iters = 0;
  Scalar theta;
  Vec v;
  do {
    v = y.normalized();
    y.noalias() = m * v;
    theta = v.dot(y);
    iters++;
  } while (iters<100 && (y-theta*v).norm() > 1e-5*std::abs(theta));
  return theta;
}
linello
Registered Member
Posts
56
Karma
0
OS
This can be an implementation of power iteration method in Eigen, maybe ggael can help about possible optimizations

Code: Select all
/**
 * @brief powerIteration Compute the dominant eigenvalue and its relative eigenvector of a square matrix
 * @param A The input matrix
 * @param eigenVector The eigenvector
 * @param tolerance Maximum tolerance
 * @param nIterations Number of iterations
 * @return The dominant eigenvalue
 */
template < typename Derived,  typename OtherDerived>
typename Derived::Scalar powerIteration(const MatrixBase<Derived>& A, MatrixBase<OtherDerived>  & eigenVector, typename Derived::Scalar tolerance,  int nIterations)
{
    typedef typename Derived::Scalar Scalar;

    OtherDerived approx(A.cols());
    approx.setRandom(A.cols());
    int counter = 0;
    Scalar error=100;
    while (counter < nIterations && error > tolerance  )
    {
        OtherDerived temp = approx;
        approx = (A*temp).normalized();
        error = (temp-approx).stableNorm();
        counter++;
    }
    eigenVector = approx;

    Scalar dominantEigenvalue = approx.transpose()*A*approx;
#ifdef INFO_LOG
    cerr << "Power Iteration:" << endl;
    cerr << "\tTotal iterations= " << counter << endl;
    cerr << "\tError= " << error << endl;
    cerr << "\tDominant Eigenvalue= " << dominantEigenvalue << endl;
    cerr << "\tDominant Eigenvector= [" << eigenVector.transpose()<< "]" << endl;
#endif
    return dominantEigenvalue;
}

 
Reply to topic

Bookmarks



Who is online

Registered users: Baidu [Spider], Bing [Bot], Exabot [Bot], Google [Bot], google01103, Hans, koriun, La Ninje, MSNbot Media, north, odysseus-art, pesto, SecretCode, Sentynel, Yahoo [Bot], z-uo