大型矩阵反演

Question

我正在考虑采用大矩阵的逆矩阵,通常大小为1000 x 1000,但有时超过100000 x 100000(由于时间和内存,目前失败).我知道正常的情绪是"不要反过来,找其他方法去做",但目前这是不可能的.造成这种情况的原因是由于已经制作的软件需要使矩阵反转.(注意:我正在研究如何改变这种情况,但这需要很长时间)

目前我们正在使用数值重新复制的LU分解方法,我目前正在测试特征库.特征库似乎更稳定,速度更快,但我仍在测试阶段的准确性.我已经快速浏览了其他库,例如ATLAS和LAPACK,但尚未对这些库进行任何实质性测试.

似乎特征库不使用并发方法来计算逆(尽管对于逆分的LU分解部分也是如此),并且据我所知,ATLAS和LAPACK在此限制中是相似的.(我目前正在使用openMP测试特征的速度差异而没有.)

第一个问题是任何人都可以解释如何通过并行化优化矩阵求逆.我在这里发现了一篇关于矩阵求逆并行算法的文章,但我不明白.看来这篇文章谈到另一种方法？我也不确定scaLAPACK或PETSc是否有用？

第二个问题,我看了这个文章使用GPU来提高性能的,但我从来没有编码的GPU,因此不知道是什么人所要表达的,但在底部的图表看起来相当惊人.这怎么可能,以及如果要成为现实,我该如何开始实现这样的事情.

我也发现这篇文章,还有时间阅读它来理解,但它似乎很有希望,因为内存是我们软件的当前问题.

有关这些文章或一般问题的任何信息都会有很大帮助.如果这个问题看起来含糊不清,我再次道歉,如果有必要,我会尽量扩大.

Answer 1

第一个问题是任何人都可以解释如何通过并行化优化矩阵求逆.

我猜测这个以及线性代数中的相关主题是并行计算中研究最多的主题之一.如果你在寻找某个地方开始阅读,那么好老的Golub和Van Loan就会有一个关于这个主题的章节.至于Scalapack和Petsc是否有用,肯定是前者,可能是后者.当然,他们都依赖于MPI,但这在这个领域是理所当然的.

第二个问题......

如果您有GPU,请使用GPU,并且可以将代码转换为GPU支持的编程模型.如果您从未编写过GPU编程并且可以访问商用类型CPU的集群,那么使用集群比使用新技术摔跤更快.

至于你提到的最后一篇文章,现在它在一个变化很快的领域已经有10年了(尝试找一篇关于使用GPU进行矩阵求逆的10年前的研究论文).我不能评论它的卓越性或其他属性,但你提到的问题规模似乎完全在内核(使用旧术语)计算的现代集群的能力范围内.如果你的矩阵很大,它们也稀疏吗？

最后,我强烈支持您明确打算使用现有的现成代码,而不是尝试开发自己的代码.

Answer 2

100000 x 100000是双精度80GB.您需要一个支持磁盘上内存映射矩阵的库.我不能推荐一个特定的库,我没有找到任何快速谷歌搜索.但是来自Numerical Recipes的代码肯定不够.

Answer 3

关于第一个问题（如何并行计算逆）：

我假设您通过对矩阵进行 LU 分解来计算逆矩阵，然后使用分解来解决 A*B = I，其中 A 是您的原始矩阵，B 是您求解的矩阵，而 I 是单位矩阵。那么B是逆。

最后一步很容易并行化。沿列划分单位矩阵。如果您有 p 个 CPU 并且您的矩阵是 n×n，那么每个部分都有 n/p 列和 n 行。让我们称这些部分为 I1、I2 等。在每个 CPU 上，求解形式为 A*B1 = I1 的系统，这将得到 B1、B2 等部分，您可以将它们组合成形式 B，即逆形式.