C ++ High eigendecomposition allocation speed

Question

Within my pipeline, I need to make my own distribution of a large matrix of the order of 6000x6000. The matrix is ​​dense, so if I simplify the task (as much as possible), the sparse method is not allowed.

I am currently playing with toy data. Using the Eigen library for the 513x513 matrix, I need ~ 6.5 seconds, while for the 2049x2049 matrix I need ~ 130 seconds, which sounds prohibitive since the increase is not linear. This was achieved using Eigen::SelfAdjointEigenSolver , while with other methods such as Eigen::EigenSolver or Eigen::ComplexEigenSolver , I did not get a noticeable improvement. The same thing happened when I tried Armadillo with arma::eig_sym even with the "dc" option, which should give a faster, but approximate result. Armadillo has several methods that return only the first X eigenvalues ​​for acceleration, but this is only for sparse methods. At the moment, I can probably get away with the first 10-20 eigenvalues.

Is there a way or library / method that can give me noticeable speedup?

Answer 1

Spectra is used to extract several eigenvalues ​​of a large matrix.

An example code for calculating the largest and smallest 10 eigenvalues ​​might look like this:

 #include <Eigen/Core> #include <Eigen/Eigenvalues> #include <MatOp/DenseGenMatProd.h> #include <MatOp/DenseSymShiftSolve.h> #include <SymEigsSolver.h> #include <iostream> using namespace Spectra; int main() { srand(0); // We are going to calculate the eigenvalues of M Eigen::MatrixXd A = Eigen::MatrixXd::Random(1000, 1000); Eigen::MatrixXd M = A.transpose() * A; // Matrix operation objects DenseGenMatProd<double> op_largest(M); DenseSymShiftSolve<double> op_smallest(M); // Construct solver object, requesting the largest 10 eigenvalues SymEigsSolver< double, LARGEST_MAGN, DenseGenMatProd<double> > eigs_largest(&op_largest, 10, 30); // Initialize and compute eigs_largest.init(); eigs_largest.compute(); std::cout << "Largest 10 Eigenvalues :\n" << eigs_largest.eigenvalues() << std::endl; // Construct solver object, requesting the smallest 10 eigenvalues SymEigsShiftSolver< double, LARGEST_MAGN, DenseSymShiftSolve<double> > eigs_smallest(&op_smallest, 10, 30, 0.0); eigs_smallest.init(); eigs_smallest.compute(); std::cout << "Smallest 10 Eigenvalues :\n" << eigs_smallest.eigenvalues() << std::endl; return 0; } 

Answer 2

I would recommend trying Arpack-Eigen. I know from Octave / Matlab that it can calculate the largest eigenvalue of a random 2049x2049 in a second and the largest 10 in 5-20 seconds, eigs(rand(2049), 10) . Now his documentation help eigs points to ARPACK. Arpack-Eigen https://github.com/yixuan/arpack-eigen allows you to request 10 eigenvalues ​​from a larger matrix as follows: SymEigsSolver< double, LARGEST_ALGE, DenseGenMatProd<double> > eigs(&op, 10, 30); .