C++ Große Eigenkompositionsgeschwindigkeit

Question

Als Teil meiner Pipeline muss ich Eigenkomposition einer großen Matrix in der Größenordnung von 6000x6000 durchführen. Die Matrix ist dicht, also, außer wenn ich das Problem vereinfache (wenn möglich, kann keine spärliche Methode verwendet werden).

Im Moment spiele ich mit Spielzeug Daten. Unter Verwendung der Eigen-Bibliothek für eine 513 × 513-Matrix benötige ich ~ 6,5 Sekunden, während für eine 2049 × 2049-Matrix ~ 130 Sekunden benötigt werden, was unerschwinglich klingt, da der Anstieg nicht linear ist. Dies wurde mit Eigen::SelfAdjointEigenSolver erreicht, während mit anderen Methoden wie Eigen::EigenSolver oder Eigen::ComplexEigenSolver habe ich keine nennenswerte Verbesserung erhalten. Dasselbe passierte, als ich Armadillo mit arma::eig_sym sogar mit der Option "dc" probierte, die ein schnelleres aber ungefähres Ergebnis geben sollte. Armadillo hat einige Methoden, die nur die ersten X Eigenwerte zur Beschleunigung zurückgeben, aber dies ist nur für spärliche Methoden. Im Moment kann ich wahrscheinlich mit den ersten 10-20 Eigenwerten davonkommen.

Gibt es einen Weg oder eine Bibliothek/Methode, die mir eine bemerkenswerte Beschleunigung geben kann?

Answer 1

Ich würde empfehlen, Arpack-Eigen auszuprobieren. Ich weiß von Octave/Matlab, dass es den größten Eigenwert eines zufälligen 2049x2049 innerhalb einer Sekunde und der größten 10 innerhalb von 5-20 Sekunden berechnen kann, eigs(rand(2049), 10). Nun verweist seine Dokumentation help eigs auf ARPACK. Arpack-Eigen https://github.com/yixuan/arpack-eigen können Sie 10 Eigenwerte von größeren Matrix wie folgt anfordern: SymEigsSolver< double, LARGEST_ALGE, DenseGenMatProd<double> > eigs(&op, 10, 30);.

Answer 2

Spectra wird verwendet, um einige Eigenwerte einer großen Matrix abzurufen.

Beispielcode berechnen die größten und kleinsten 10 Eigenwerte wie folgt aussehen kann:

#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; 
}