## Sorting of Eigenvalues and Eigen vectors in the EigenSolver

rajats
Registered Member
Posts
2
Karma
0

### Sorting of Eigenvalues and Eigen vectors in the EigenSolver

Thu Oct 04, 2012 10:21 am
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
204
Karma
2

### Re: Sorting of Eigenvalues and Eigen vectors in the EigenSol

Thu Oct 04, 2012 12:44 pm
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

### Re: Sorting of Eigenvalues and Eigen vectors in the EigenSol

Tue Oct 09, 2012 7:57 am
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?
ggael
Moderator
Posts
2822
Karma
18
OS

### Re: Sorting of Eigenvalues and Eigen vectors in the EigenSol

Tue Oct 09, 2012 11:36 am
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

### Re: Sorting of Eigenvalues and Eigen vectors in the EigenSol

Mon Oct 22, 2012 8:35 am
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;}`

## Who is online

Registered users: akrutzler, andreas_k, Baidu [Spider], Bing [Bot], claydoh, davidemme, einar, ErikTheVirus, Exabot [Bot], Google [Bot], google01103, jensreuterberg, La Ninje, larsend, louis94, maxleoc, mbeenham, mbower, mgentry, nharmony, ovidiub13, rapiteanu, rogerdavis, rumangerst, Sogou [Bot], supaiku, tavet, TheraHedwig, Yahoo [Bot]