我有一个 nxn 协方差矩阵（所以，实数，对称，密集，nxn）。'n' 可能非常非常大！我想解决这个矩阵的完整特征值（+特征向量）问题。有人能告诉我最快的算法是什么吗？
PS 我想使用 OpenCL 实现 GPGPU。典型尺寸为 10000x10000 甚至更大。这就是为什么我正在寻找最快的算法
PSS 我想编写自己的实现（仅用于教育）所以请不要建议已经存在的库
实对称nxn矩阵的完全特征值问题的算法
计算科学
线性代数
算法
本征系统
2021-12-11 22:00:09
2个回答
10000 x 10000 并不是很大。这种大小的双精度矩阵需要 800 兆字节的内存。您至少需要尽可能多的内存来保存结果特征向量的矩阵，并且您需要额外的工作存储空间，但这完全在具有 8 GB 或更多内存的典型台式机的能力范围内。它也适合高端 GPGPU 上的图形内存。
就时间而言，这也不算太糟糕。我刚刚在台式机（使用 MATLAB/LAPACK 并运行 8 个内核）上计算了随机对称 100000 x 10000 矩阵的特征值和特征向量，运行大约需要 3 分钟。
如果您只需要对这种大小的少量矩阵进行此计算，那么将其移至 GPGPU 可能不值得您花费时间和精力。但是，如果您打算 24/7 全天候进行这些计算，那么花一些精力来加快它们可能是合适的。
这是一种您可以使用高端 GPGPU 加速的计算，但如果它在更基本的显卡上表现不佳，请不要感到惊讶。这里的问题是您的显卡可能没有足够的内存，而且双精度性能并不是许多 GPGPU 的强项。
由于特征值计算通常可通过 LAPACK 库获得，我建议您寻找已针对您的 GPGPU 优化的 LAPACK 库的实现。特别是，查看 MAGMA 库的 OpenCL 版本：
关于您关于完整对称特征问题的最快算法的问题...
计算有两个主要阶段。首先是使用（阻塞）Householder 反射简化为三对角形式。这在矩阵维度上以立方时间运行，您可以轻松编写自己的非阻塞版本，而阻塞版本稍微复杂一些。
计算结果三对角矩阵的特征值可以使用最前沿的算法（MRRR或分而治之）或使用传统的QR或QL迭代在伪二次时间内完成。棘手的部分是您不仅必须进行迭代（这是“微不足道的”），还必须处理通货紧缩和各种其他优化，这些优化可以轻松地将事情加速一个数量级或更多。我只链接到传统东西的（等效）Lapack 代码，MRRR 的代码非常微妙并且经常会失败，而分治法中求解世俗方程以将各部分粘合在一起的步骤也非常微妙。即使对于普通的 CPU 执行，对这些东西进行编码也是非常重要的；我无法想象在 GPU 上会有多困难。