18

我正在寻找一个大矩阵的逆矩阵，常见大小为 1000 x 1000，但有时超过 100000 x 100000（由于时间和内存，目前正在失败）。我知道正常的情绪是“不要采取相反的方式，找到其他方法来做到这一点”，但目前这是不可能的。其原因是由于使用了期望得到矩阵逆的软件。（注意：我正在研究改变这种情况的方法，但这需要很长时间）

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

似乎 eigen 库不使用并发方法来计算逆（尽管对于逆的 LU 分解部分确实如此），据我所知，ATLAS 和 LAPACK 在这个限制方面是相似的。（我目前正在使用 openMP 和不使用 openMP 测试 eigen 的速度差异。）

第一个问题是谁能解释如何通过并行化优化矩阵求逆。在这里找到了一篇讲矩阵求逆并行算法的文章，但是没看懂。这篇文章似乎在谈论另一种方法？我也不确定 scaLAPACK 或 PETSc 是否有用？

第二个问题，我阅读了这篇关于使用 GPU 提高性能的文章，但我从未为 GPU 编码，因此不知道要传达什么，但底部的图表看起来相当惊人。这怎么可能，如果这是真的，我该如何开始实施这样的事情。

我还发现了这篇文章，还没有时间通读以了解它，但它似乎很有希望，因为内存是我们软件的当前问题。

有关这些文章或一般问题的任何信息都会有很大帮助。如果这个问题看起来含糊不清，我再次道歉，如有必要，我会尝试扩展更多内容。

4

5 回答 5

8

第一个问题是谁能解释如何通过并行化优化矩阵求逆。

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

第二个问题...

如果你有 GPU 并且你有能力将你的代码转换成你的 GPU 支持的编程模型，就使用它们。如果您从未为 GPU 编写过代码并且可以访问商品类型的 CPU 集群，那么与使用新技术相比，使用集群会更快地掌握速度。

至于你提到的上一篇文章，它在一个变化非常快的领域已经有 10 年的历史了（尝试找到一篇关于使用 GPU 进行矩阵求逆的 10 年历史的研究论文）。我无法评论它的卓越性或其他属性，但在我看来，您提到的问题大小似乎完全在现代集群的核心（使用旧术语）计算能力范围内。如果您的矩阵非常大，它们是否也是稀疏的？

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

于 2012-06-27T15:56:48.140 回答
5

100000 x 100000 在双精度下是 80GB。您需要一个支持磁盘上的内存映射矩阵的库。我不能推荐一个特定的图书馆，而且我没有通过快速的谷歌搜索找到任何东西。但是来自 Numerical Recipes 的代码肯定是不够的。

于 2012-06-27T15:55:30.187 回答
5

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

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

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

于 2012-06-28T12:33:14.800 回答
2

GPU 上的 LU 解压缩可以比 CPU 上快约 10 倍。尽管现在这种情况正在发生变化，但 GPU 传统上是围绕单精度算术设计的，等等较旧的硬件单精度算术通常比双精度算术快得多。此外，存储要求和性能将受到矩阵结构的极大影响。稀疏的 100,000 x 100,000 矩阵 LU decomp 是一个需要解决的合理问题，并且不需要太多内存。

除非您想成为专家并花大量时间调整硬件更新，否则我强烈建议您使用商业库。我建议使用 CULA 工具。他们既有稀疏的也有密集的 GPU 库，实际上他们的免费库提供了 SGETRF——一个单精度（密集）LU decomp 例程。您必须为他们的双精度库付费。

于 2012-07-01T05:33:59.210 回答
1

我知道这是旧帖子 - 但实际上 - OpenCL（你根据你的显卡下载相关的）+ OpenMP + 矢量化（不是按那个顺序）是要走的路。

无论如何 - 对我来说，我对矩阵的经验实际上与将双双数组复制进出系统的开销以及在任何计算开始之前用 0 填充或初始化矩阵的开销有关 - 特别是当我正在创建 .xll 时用于 Excel。

如果我要重新排列顶部的优先级 -

  1. 尝试对代码进行矢量化（Visual Studio 2012 和 Intel C++ 具有自动矢量化功能 - 我不确定 MinGW 或 GCC，但我认为编译器有一些标志可以分析您的 for 循环以生成正确的汇编代码以使用而不是普通寄存器来保存数据，填充处理器的向量寄存器。我认为 Excel 正在这样做，因为当我在运行它们的 MINVERSE() 时监视 Excel 的线程时，我注意到只使用了 1 个线程。我不太懂汇编语言 -所以我不知道如何手动矢量化......（还没有时间去学习这个，但是很想这样做！）
  2. 与 OpenMP (omp pragma) 或 MPI 或 pthreads 库 (parallel_for) 并行化 - 非常简单 - 但是......这里有一个问题 - 我意识到如果你的矩阵类首先是完全单线程的 - 然后并行化操作，如 mat multiply或逆是可报废的 - 因为并行化会由于初始化或复制到或仅访问非并行化矩阵类而降低速度。但是......并行化有帮助的地方是 - 如果您正在设计自己的矩阵类并并行化其构造函数操作（用 0 等填充），那么您的 LU(A^-1) = I 计算也会更快。优化您的 LU 分解，并优化您对身份特殊情况的前向后向替换在数学上也很简单。（即不
  3. 一旦它被并行化（在外层上） - 需要逐个元素的矩阵运算可以映射到由 GPU（SSSSSS）计算 - 数百个处理器来计算元素 - 击败它！。现在在 ATI 的网站上提供了示例 Monte Carlo 代码——使用 ATI 的 OpenCL——不用担心将代码移植到使用 GeForce 的东西上——你要做的就是在那里重新编译。

但是对于 2 和 3 - 请记住，除非您处理 F* K *G HUGE 矩阵，否则会产生开销，所以没有意义 - 但我看到 100k^2？哇...

基因

于 2014-01-10T03:25:21.330 回答