5
$\begingroup$

I am working with an Eigen::SparseMatrix matrix of type double. I would like to find the largest and the smallest eigenvalues.

A solution of the problem is to convert it to dense and then find its eigenvalues. Finally the maximum and the minimum in the spectrum.

Is there a better efficient way to do it? Let say

  1. Possibly without converting it to dense
  2. Possibly without computing all the spectrum
Improve this question
$\endgroup$
2
  • $\begingroup$ Is your matrix symmetric? $\endgroup$
    – Bill Greene
    May 4, 2017 at 16:15
  • $\begingroup$ It is skew-Hermiten $\endgroup$
    – Galuoises
    May 5, 2017 at 15:15

2 Answers 2

Reset to default
8
$\begingroup$

There are two relatively convenient options for calculating selected (e.g. a few largest or smallest) eigenvalues using Eigen.

The first is Spectra, a header-only C++ library based on Eigen that uses algorithms similar to ARPACK (implicitly-restarted Arnoldi) to calculate a few eigensolutions.

Since it is header-only, you simply download and include the appropriate header files. The site contains several example problems to get you started.

A second option, if your matrix is symmetric, is an interface to a subset of ARPACK, that is part of the standard Eigen distribution, and is very easy to use. Here is a small snippet of code to give you the basic idea of how to use this interface

#include <unsupported/Eigen/ArpackSupport>
typedef Eigen::SparseMatrix<double> SparseMat;
typedef Eigen::SimplicialLDLT<SparseMat> SparseChol;
typedef Eigen::ArpackGeneralizedSelfAdjointEigenSolver <SparseMat, SparseChol> Arpack;
Arpack arpack;
// define sparse matrix A
SparseMat A;
//...
// calculate the two smallest eigenvalues
int nbrEigenvalues = 2;
arpack.compute(A, nbrEigenvalues, "SM");
cout << "arpack eigenvalues\n" << arpack.eigenvalues().transpose() << endl;

The downside of this approach is that you need to have an ARPACK library built for your particular system. If you need to build ARPACK yourself, I suggest this version, ARPACK-NG, because it has many bug fixes compared with the original and more support for building on different platforms.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you so much. I have been able to find min/max eigenvalue using Spectra using Spectra::GenEigsSolver $\endgroup$
    – Galuoises
    May 5, 2017 at 15:17
  • $\begingroup$ By setting Spectra::SELECT_EIGENVALUE as in spectralib.org/doc/group__enumerations $\endgroup$
    – Galuoises
    May 5, 2017 at 15:22
  • $\begingroup$ Unfortunately I cannot try your code in Arpack-Ng because I have serious issues to let the package work in MacOSX Sierra at the moment. $\endgroup$
    – Galuoises
    May 5, 2017 at 15:24
1
$\begingroup$

You can use arpack [1], that implements the Arnoldi algorithm for computing eigenpairs. Since arpack communicates with client code only through matrix vector product, you can use your own matrix type (including eigen sparse matrix). There is also a version with C++ bindings [2] that may be easier to use with eigen. To compute the smallest eigenvalue, it may be interesting to factorize the matrix using a sparse factorization algorithm (SuperLU for non-symmetric, CHOLDMOD for symmetric), and use the factorization to compute the largest eigenvalues of M^-1 instead of the smallest eigenvalue of M (a technique known as spectral transform, that I used a while ago in [3], can have a dramatic impact on performances in some cases). The whole algorithm (including coupling with SUPERLU) is implemented in my OpenNL library [4]

[1] http://www.caam.rice.edu/software/ARPACK/

[2] http://www.ime.unicamp.br/~chico/arpack++/

[3] http://alice.loria.fr/index.php/publications.html?Paper=ManifoldHarmonics@2008

[4] OpenNL:http://alice.loria.fr/index.php/software/4-library/23-opennl.html

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.