Largest eigenvalues (and corresponding eigenvectors) in C++

Question

What is the easiest and fastest way (with some library, of course) to compute k largest eigenvalues and eigenvectors for a large dense matrix in C++? I'm looking for an equivalent of MATLAB's eigs function; I've looked through Armadillo and Eigen but couldn't find one, and computing all eigenvalues takes forever in my case (I need top 10 eigenvectors for an approx. 30000x30000 dense non-symmetric real matrix).

Desperate, I've even tried to implement power iterations by myself with Armadillo's QR decomposition but ran into complex pairs of eigenvalues and gave up. :)

Scofflaw

Answer 1

AFAIK the problem of finding the first k eigenvalues of a generic matrix has no easy solution. The Matlab function eigs you mentioned is supposed to work with sparse matrices.

Matlab probably uses Arnoldi/Lanczos, you might try if it works decently in your case even if your matrix is not sparse. The reference package for Arnlodi is ARPACK which has a C++ interface.

Propaganda

I'm not sure which algorithms it uses, but Matlab's eigs does work radically faster than finding all eigenvalues for a large dense matrix. – Scofflaw

eigs uses Arnoldi, which is designed to output the first k larger eigenvalues. Whether faster or slower than finding all the eigenvalues depends on how big is your k. – Propaganda

Thank you! Arpack does not have the most friendly interface in the world, but it worked. 4m20s on a problem of my size (10 eigenvectors for a matrix of size 30K x 30K) is excellent. – Scofflaw

Answer 2

Did you tried https://github.com/yixuan/spectra ? It similar to ARPACK but with nice Eigen-like interface (it compatible with Eigen!)

I used it for 30kx30k matrices (PCA) and it was quite ok

Robbyrobbyn

Just tried this myself in my app that uses Eigen for all linear algebra related things and this is super convenient: header only (like Eigen) so no build issues, just #include + 4 lines of code and I have my eigenvalues, input and output in Eigen format, and much faster than my own implementation of Lanczos' iteration, 100 eigenvalues (highest or smallest by choice) in 80k x 80k sparse matrix in a few seconds. – Kittenish

Answer 3

Here is how I get the k largest eigenvectors of a NxN real-valued (float), dense, symmetric matrix A in C++ Eigen:

#include <Eigen/Dense>
...
Eigen::MatrixXf A(N,N);
...
Eigen::SelfAdjointEigenSolver<Eigen::MatrixXf> solver(N);
solver.compute(A);
Eigen::VectorXf lambda = solver.eigenvalues().reverse();
Eigen::MatrixXf X = solver.eigenvectors().block(0,N-k,N,k).rowwise().reverse();

Note that the eigenvalues and associated eigenvectors are returned in ascending order so I reverse them to get the largest values first.

If you want eigenvalues and eigenvectors for other (non-symmetric) matrices they will, in general, be complex and you will need to use the Eigen::EigenSolver class instead.

Cruickshank

Answer 4

Eigen has an EigenValues module that works pretty well.. But, I've never used it on anything quite that large.

Highlands

Yes, but I couldn't find anything there that computes top k eigenvalues. Finding all eigenvalues would be very slow. – Scofflaw

I see some example functions here that compute the dominant Eigenvalue/vector. – Highlands