实对称nxn矩阵特征值问题的算法

计算科学 线性代数 本征系统 显卡 特征值
2021-12-09 17:20:27

我有一个 nxn 协方差矩阵(所以,实数,对称,密集,nxn ......我的意思是半正定)。'n' 可能非常非常大!我想解决这个矩阵的部分(3 个最大)特征值(+特征向量)问题。有人能告诉我最快的算法是什么吗?它是幂迭代方法(因为它具有 O(n^2) 复杂度)吗?

PS 我想使用 OpenCL 实现 GPGPU。

2个回答

一个 100,0000 x 100,000 的单精度对称密集矩阵需要 20 GB 的内存(仅存储上三角)或 40 GB 的双精度内存。因此,它太大而无法容纳在可用 GPU 的内存中。

为了使用 GPU 加速解决这个问题,您必须开发一种算法,将较小的工作块发送到 GPU。在每次迭代中将部分矩阵复制到 GPU 中不太可能正常工作。相反,您可以尝试并行使用多个 GPU,每个 GPU 在整个算法中存储部分矩阵。例如,您可以使用四个 NVIDIA Tesla K20X 来存储您的单精度矩阵。

针对此类问题要考虑的适当算法是使用矩阵向量乘法的迭代方案。首先查看 ARPACK 中实现的算法。由于 ARPACK 可以使用 BLAS 例程进行矩阵向量乘法,因此您应该能够简单地将 ARPACK 与 BLAS 的某些 GPU 实现链接以获得工作代码。

很多方法可以解决您的问题,而选择合适的方法有时更像是一门艺术。不过,有几件事是绝对正确的:

  • 105×105在科学计算领域并不是不可想象的大,有很多工具可以处理这种大小的问题
  • GPU 加速的特征值求解器仍然相对较新,通常不是首选工具
  • 单个计算节点或 GPU 都装不下,带来了可扩展性的问题
  • 您应该将问题分布在多个节点上以处理内存存储问题,许多库都处理这个问题,黄金标准是SLEPc,它有几个可以试验的例程

症结:目前尚不清楚哪种方法可以最快地找到这些特征值,通常取决于矩阵结构和条件,但可以使用适当的工具来找出。