大型密集矩阵的 LU 分解

计算科学 优化 算法 C++ 矩阵
2021-12-06 04:26:26

我想生成大尺寸密集矩阵()的 LU 分解,我目前使用的 LU 分解基于自适应交叉近似,并且需要很长时间才能执行更大的任何人都可以建议一些可以很好地并行化(使用 OpenMP)并花费更短时间的 LU 分解技术吗?N>107N

笔记:

  1. 我用 C++ 编写代码并使用 Xeon 处理器(128 个线程)和 Eigen 库。
  2. 矩阵中的条目通过形式为的核函数填充。e(x1x2)2
  3. 矩阵的存储不是问题,我正在使用 Xeon 处理器并且有足够的内存,而且,我没有存储完整的矩阵,每当我需要在矩阵中找到一个条目时,我使用内核函数并生成类型-该单元格的双倍数。
2个回答

你不能。除非你有一些特殊的知识,否则你的因子会很密集,并且会有条目——比你在任何合理的机器上存储的要多(大约一百万 GB)。此外,计算这些因子需要操作,即 CPU 年——比你想要的要长等待。LUN2=O(1014)O(N3)=O(1021)3104

您遇到的问题根本无法通过 LU 分解来解决。你需要想出其他策略来做你想做的事——例如,用 Krylov 空间方法求解线性系统,计算显式格林函数,或者使用关于稀疏性的知识。

我不确定您使用的是哪种类型的 LU 框架,因为可以将 ACA 应用于各种不同的设置。明确地说,你现在正在研究的方法,我要提议的方法并没有给你一个 LU 分解。它是某种形式的 LU 分解的近似值

由于您使用的是非奇异内核,我想您可以尝试压缩整个矩阵。通常,这些方法应用于奇异内核,然后当您以多级方式将矩阵细分为块并且其中大多数是可压缩的时,您就有了分层模式。这些块将使用一些快速技术(如 ACA)来计算。值得一提的是,ACA不太理想,控制精度有问题等等。然后,你可以分解矩阵。我描述的方法几乎是分层矩阵(H-matrix) 方法,由 W. Hackbusch 博士开发http://www.hmatrix.org/

简而言之,这种方法允许O(kmax3Nlog2N)LU分解和O(kmax3NlogN)用于反向替换并且通过 OpenMP 可以很好地并行化。注意,这里kmax是最高等级,对于 ACA,这意味着骨架的数量。当然,这假设您有一个很好的平衡分区。详细信息和限制可在许多论文中找到H-矩阵论文。

看看这种方法,以及他们可用的Hlib 库,可供公众使用。其他建议可能包括我知道(但不太熟悉)的其他几个框架,例如 HSS,以及更多来自计算电磁学的框架:

  1. J. Shaeffer,“PC 上的百万加未知 MOM LU 因式分解”,2015 年高级应用电磁学国际会议 (ICEAA),都灵,2015 年,第 62-65 页。doi: 10.1109/ICEAA.2015.7297075

  2. S. Kapur 和 DE Long,“N 体问题:IES3:高效静电和电磁模拟”,IEEE 计算科学与工程,第一卷。5,没有。4,第 60-67 页,10 月至 12 月。1998.doi: 10.1109/MCSE.1998.7102081