我有一个 nxn 协方差矩阵(所以,实数,对称,密集,nxn ......我的意思是半正定)。'n' 可能非常非常大!我想解决这个矩阵的部分(3 个最大)特征值(+特征向量)问题。有人能告诉我最快的算法是什么吗?它是幂迭代方法(因为它具有 O(n^2) 复杂度)吗?
PS 我想使用 OpenCL 实现 GPGPU。
我有一个 nxn 协方差矩阵(所以,实数,对称,密集,nxn ......我的意思是半正定)。'n' 可能非常非常大!我想解决这个矩阵的部分(3 个最大)特征值(+特征向量)问题。有人能告诉我最快的算法是什么吗?它是幂迭代方法(因为它具有 O(n^2) 复杂度)吗?
PS 我想使用 OpenCL 实现 GPGPU。
一个 100,0000 x 100,000 的单精度对称密集矩阵需要 20 GB 的内存(仅存储上三角)或 40 GB 的双精度内存。因此,它太大而无法容纳在可用 GPU 的内存中。
为了使用 GPU 加速解决这个问题,您必须开发一种算法,将较小的工作块发送到 GPU。在每次迭代中将部分矩阵复制到 GPU 中不太可能正常工作。相反,您可以尝试并行使用多个 GPU,每个 GPU 在整个算法中存储部分矩阵。例如,您可以使用四个 NVIDIA Tesla K20X 来存储您的单精度矩阵。
针对此类问题要考虑的适当算法是使用矩阵向量乘法的迭代方案。首先查看 ARPACK 中实现的算法。由于 ARPACK 可以使用 BLAS 例程进行矩阵向量乘法,因此您应该能够简单地将 ARPACK 与 BLAS 的某些 GPU 实现链接以获得工作代码。
有很多方法可以解决您的问题,而选择合适的方法有时更像是一门艺术。不过,有几件事是绝对正确的:
症结:目前尚不清楚哪种方法可以最快地找到这些特征值,通常取决于矩阵结构和条件,但可以使用适当的工具来找出。