计算小对称矩阵的所有特征向量和特征值

计算科学 线性代数 矩阵 特征值 拉帕克 密集矩阵
2021-12-17 18:04:05

我的问题是计算许多小的(n < 30)对称正定矩阵的特征向量和特征值。

到目前为止,我正在使用 LAPACK 的 DSYEV。

优先考虑的是速度而不是准确性。是否有更快的算法(可能不是渐近的,但实际上对于小输入)?

2个回答

根据我的经验,这个问题的答案并不明确。它取决于特征值的跨度和相对矩阵结构本身。也就是说,您当前的方法唤起了一个隐式移动的 QR 求解器,它本质上是这种确切类型问题的标准。但是,通过一些实验,您可能会发现适度的性能提升。

几个选项:

  1. 如果您的问题条件良好,请使用单精度计算。

  2. DSYEVR 是用于实对称矩阵的 LAPACK 驱动程序,它使用 MRRR 算法首先计算特征值,然后通过逆类型问题获取请求的特征向量。对于您的特定矩阵,它可能会更快。

  3. 使用并行库。虽然您的问题很小,但在使用相对较少数量的内核时,我仍可能期望适度的性能提升。ScaLAPACK 在这里始终是一个安全的选择,尽管我首先推荐 SLEPc。SLEPc 通过 PETSc 运行,并作为多个 EVP 求解器的包装器,其中许多是并行的,因此通常是可扩展的形式。这将使您有机会即时尝试几种方法并评估它们对您的问题的相对效率。SLEPc 中使用的迭代算法可以采用特征值容差参数,在您的情况下也可以提高性能。

注意:我意识到这个答案并不是特别令人满意。如果您提供有关矩阵性质及其构造的一些详细信息,有人可能会向您传授某种专业知识。

您可能想尝试 Eigen C++ 类库 http://eigen.tuxfamily.org/index.php?title=Main_Page中的 SelfAdjointEigenSolver 类https://eigen.tuxfamily.org/dox/classEigen_1_1SelfAdjointEigenSolver.html

我用一个 30x30 SPD 矩阵进行了一些数值实验,条件数为 1000,根据 Neumaier 在此处 使用索引生成对称正定矩阵描述的程序构建

我使用了一台装有 2.8 GHz AMD Phenom II X4 830 CPU 的 Windows 7 计算机。编译器是 VS 2013。

对于 Lapack ssyev/dsyev 的实验,我使用了 OpenBlas http://www.openblas.net/在之前的实验中,我发现这个库中的 BLAS 操作具有非常好的性能。我怀疑(但没有验证)他们对 ssyev/dsyev 的实现只是使用标准的 Fortran 代码,但该例程的性能在很大程度上取决于底层 BLAS 函数的质量。

在这种情况下,Eigen::SelfAdjointEigenSolver 比 ssyev/dsyev 快得多——每次调用约 0.25 毫秒,而每次调用约 2 毫秒。

当我从双精度切换到单精度时,我只看到了非常小的时间减少。但我注意到计算的特征值存在很大错误。这对 Eigen 和 Lapack 来说都是如此。