2
$\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
$\endgroup$
  • $\begingroup$ Is your matrix symmetric? $\endgroup$ – Bill Greene May 4 '17 at 16:15
  • $\begingroup$ It is skew-Hermiten $\endgroup$ – Galuoises May 5 '17 at 15:15
7
$\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.

$\endgroup$
  • $\begingroup$ Thank you so much. I have been able to find min/max eigenvalue using Spectra using Spectra::GenEigsSolver $\endgroup$ – Galuoises May 5 '17 at 15:17
  • $\begingroup$ By setting Spectra::SELECT_EIGENVALUE as in spectralib.org/doc/group__enumerations $\endgroup$ – Galuoises May 5 '17 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 '17 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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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