低 RAM 消耗 C++ 特征求解器

我是新手C++编程，但我有一个任务来计算特征值和特征向量（标准特征问题Ax=lx）对于对称矩阵（和厄米矩阵））对于尺寸非常大的矩阵：二项式(L,L/2) where L大约是18-22。现在我正在具有大约 7.7 GB 可用内存的机器上进行测试，但最终我将可以访问具有 64GB RAM 的 PC。

我已经开始了Lapack++。一开始我的项目假设只针对对称实矩阵解决这个问题。

这个图书馆很棒。非常快且占用内存小。它可以选择计算特征向量并将其放入输入矩阵 A 以节省内存。有用！我以为Lapack++eigensolver 可以处理埃尔米特矩阵，但由于未知原因而不能处理（也许我做错了什么）。我的项目已经发展，我应该也能够计算埃尔米特矩阵的这个问题。

所以我尝试将库更改为犰狳图书馆。它工作得很好，但它并不那么好Lapack++它取代了mat A所有eigenvec，但当然支持埃尔米特矩阵。

L=14 的一些统计

• Lapack++RAM 126MB 时间 7.9s 特征值 + 特征向量

• 犰狳RAM 216MB 时间 12s 特征值

• 犰狳RAM 396MB 时间 15s 特征值+特征向量

我们来做一下计算：double变量是关于8B。我的矩阵有大小二项式(14,7) = 3432，所以在理想情况下它应该有3432^2*8/1024^2 = 89 MB.

我的问题是：是否可以修改或强制犰狳做一个漂亮的把戏Lapack++? 犰狳 uses LAPACK and BLAS例程。或者也许有人可以推荐使用另一个库解决这个问题的另一种方法？

附： 我的矩阵非常稀疏。它有大约2 * 二项式(L,L/2)非零元素。 我尝试用以下方法计算这个SuperLUCSC 格式，但效果不是很好，L=14 -> RAM 185MB，但时间为 135 秒。

Lapackpp 和 Armadillo 都依赖 Lapack 来计算复矩阵的特征值和特征向量。 Lapack 库提供了不同的方法来对复杂厄米矩阵执行这些操作。

• 功能zgeev() http://www.netlib.org/lapack/explore-html/dd/dba/zgeev_8f.html不关心矩阵是 Hermitian 矩阵。该函数由 Lapackpp 库针对类型矩阵调用LaGenMatComplex在函数中LaEigSolve http://lapackpp.sourceforge.net/html/laslv_8h.html#086357d17e9cdcaec69ab7db76998769。功能eig_gen() http://arma.sourceforge.net/docs.html#eig_genArmadillo 库的 调用此函数。

• 功能zheev() http://www.netlib.org/lapack/explore-html/d6/dee/zheev_8f.html致力于复杂的埃尔米特矩阵。它首先调用 ZHETRD 将 Hermitian 矩阵简化为三对角形式。根据是否需要特征向量，然后使用二维码算法 https://en.wikipedia.org/wiki/QR_algorithm计算特征值和特征向量（如果需要）。功能eig_sym() http://arma.sourceforge.net/docs.html#eig_sym犰狳库的调用此函数，如果该方法std被选中。

• 功能zheevd() http://www.netlib.org/lapack/explore-html/d6/dae/zheevd_8f.html做同样的事情zheev()如果不需要特征向量。否则，它会使用分治算法（请参阅zstedc() http://www.netlib.org/lapack/explore-3.1.1-html/zstedc.f.html<code>）。功能eig_sym() http://arma.sourceforge.net/docs.html#eig_sym犰狳库的调用此函数，如果该方法dc被选中。由于事实证明分治法对于大型矩阵更快，因此它现在是默认方法。

Lapack 库中提供了具有更多选项的函数。 （看zheevr() http://www.netlib.org/lapack/explore-html/d9/dd2/zheevr_8f.html or zheevx http://www.netlib.org/lapack/explore-html/dd/d95/zheevx_8f.html）。如果你想保持密集矩阵格式，你也可以尝试ComplexEigenSolver本征图书馆。

这是使用 C 包装器进行的一点 C++ 测试LAPACKE拉帕克图书馆。它是由g++ main.cpp -o main2 -L /home/...../lapack-3.5.0 -llapacke -llapack -lblas

#include <iostream>

#include <complex>
#include <ctime>
#include <cstring>

#include "lapacke.h"

#undef complex
using namespace std;

int main()
{
    //int n = 3432;

    int n = 600;

    std::complex<double> *matrix=new std::complex<double>[n*n];
    memset(matrix, 0, n*n*sizeof(std::complex<double>));
    std::complex<double> *matrix2=new std::complex<double>[n*n];
    memset(matrix2, 0, n*n*sizeof(std::complex<double>));
    std::complex<double> *matrix3=new std::complex<double>[n*n];
    memset(matrix3, 0, n*n*sizeof(std::complex<double>));
    std::complex<double> *matrix4=new std::complex<double>[n*n];
    memset(matrix4, 0, n*n*sizeof(std::complex<double>));
    for(int i=0;i<n;i++){
        matrix[i*n+i]=42;
        matrix2[i*n+i]=42;
        matrix3[i*n+i]=42;
        matrix4[i*n+i]=42;
    }

    for(int i=0;i<n-1;i++){
        matrix[i*n+(i+1)]=20;
        matrix2[i*n+(i+1)]=20;
        matrix3[i*n+(i+1)]=20;
        matrix4[i*n+(i+1)]=20;

        matrix[(i+1)*n+i]=20;
        matrix2[(i+1)*n+i]=20;
        matrix3[(i+1)*n+i]=20;
        matrix4[(i+1)*n+i]=20;
    }

    double* w=new double[n];//eigenvalues

    //the lapack function zheev
    clock_t t;
    t = clock();
    LAPACKE_zheev(LAPACK_COL_MAJOR,'V','U', n,reinterpret_cast< __complex__ double*>(matrix), n, w);
    t = clock() - t;
    cout<<"zheev : "<<((float)t)/CLOCKS_PER_SEC<<" seconds"<<endl;
    cout<<"largest eigenvalue="<<w[n-1]<<endl;

    std::complex<double> *wc=new std::complex<double>[n];
    std::complex<double> *vl=new std::complex<double>[n*n];
    std::complex<double> *vr=new std::complex<double>[n*n];

    t = clock();
    LAPACKE_zgeev(LAPACK_COL_MAJOR,'V','V', n,reinterpret_cast< __complex__ double*>(matrix2), n, reinterpret_cast< __complex__ double*>(wc),reinterpret_cast< __complex__ double*>(vl),n,reinterpret_cast< __complex__ double*>(vr),n);
    t = clock() - t;
    cout<<"zgeev : "<<((float)t)/CLOCKS_PER_SEC<<" seconds"<<endl;
    cout<<"largest eigenvalue="<<wc[0]<<endl;

    t = clock();
    LAPACKE_zheevd(LAPACK_COL_MAJOR,'V','U', n,reinterpret_cast< __complex__ double*>(matrix3), n, w);
    t = clock() - t;
    cout<<"zheevd : "<<((float)t)/CLOCKS_PER_SEC<<" seconds"<<endl;
    cout<<"largest eigenvalue="<<w[n-1]<<endl;

    t = clock();
    LAPACKE_zheevd(LAPACK_COL_MAJOR,'N','U', n,reinterpret_cast< __complex__ double*>(matrix4), n, w);
    t = clock() - t;
    cout<<"zheevd (no vector) : "<<((float)t)/CLOCKS_PER_SEC<<" seconds"<<endl;
    cout<<"largest eigenvalue="<<w[n-1]<<endl;

    delete[] w;
    delete[] wc;
    delete[] vl;
    delete[] vr;
    delete[] matrix;
    delete[] matrix2;
    return 0;
}

我的计算机的输出是：

zheev : 2.79 seconds
largest eigenvalue=81.9995
zgeev : 10.74 seconds
largest eigenvalue=(77.8421,0)
zheevd : 0.44 seconds
largest eigenvalue=81.9995
zheevd (no vector) : 0.02 seconds
largest eigenvalue=81.9995

这些测试可以通过使用 Armadillo 库来执行。直接调用 Lapack 库可能会让您获得一些内存，但 Lapack 的包装器在这方面也可以很高效。

真正的问题是您是否需要所有特征向量、所有特征值或仅需要最大特征值。因为最后一种情况确实有有效的方法。看看阿诺尔迪/Lanczos https://en.wikipedia.org/wiki/Lanczos_algorithm迭代算法。如果矩阵是稀疏的，则可能会获得巨大的内存增益，因为仅执行矩阵向量乘积：无需保持密集格式。这就是 SlepC 库中所做的事情，它利用了 Petsc 的稀疏矩阵格式。这是一个 Slepc 的例子 http://slepc.upv.es/documentation/current/src/eps/examples/tutorials/ex1.c.html可以作为起点。