许多小矩阵逆的内存/速度权衡

计算科学 线性代数 线性求解器 io 无基质
2021-12-18 17:54:03

问题

在有限元代码的情况下,我有许多小的(30x30 阶)矩阵逆(或 LU 分解),每个有限元一个。这些矩阵逆永远不会改变,并且必须在无矩阵求解器的上下文中重复应用于向量。

存储所有这些逆是代码的内存瓶颈,因为它们必须应用于网格中的每个有限元。另一方面,“即时”计算逆运算(使用 LAPACK 或 Numpy)是不切实际的,因为这些逆运算必须在稀疏迭代求解的每次迭代中应用,因此每个时间步都需要

(CG 迭代次数)*(元素数量)*(反演时间)

这太昂贵了,即使对于远小于我感兴趣的问题的问题也是如此。

(可能的)解决方案

我正在考虑执行一次矩阵求逆或 LU 分解,然后将它们存储到磁盘,而不是将它们保存在内存中。然后想法是一次一个或一个块地将逆向读入内存,并应用它们,避免重复的倒置。但我知道从磁盘读取可能很昂贵。

有没有好的或可接受的方法来做到这一点?我看过的大多数核心论文都在考虑直接解决或更复杂的问题,所以我也希望能提供任何指向相关参考的指针。

编辑:代码是 Python 和 C 的混合体,我发现一些帖子表明 HDF5 库可能是滚动我自己的缓存的一个很好的替代方案,如上所述。

2个回答

没有比将它们放入内存更快的存储方法了。如果您的问题是您无法将所有元素矩阵逆存储在内存中,那么您有两个选择:(i)为您使用的机器购买更多内存,(ii)使用更多机器。还有(iii)解决较小的问题。尝试将矩阵外部化到磁盘会使事情变得非常慢,因为磁盘至少比内存慢一个数量级。磁盘也比机器之间的通信慢得多。

但值得退后一步。如果您的求解器方案需要存储大量的局部矩阵逆,那么这可能不是一个很好的求解器。我在这里假设在您的方案中,存储逆矩阵比存储局部矩阵开始时更昂贵 - 例如,因为局部矩阵是稀疏的,但逆矩阵不是。一般来说,我 20 年有限元计算的经验是,如果你的内存用完了,那么你的 CPU 时间也已经用完了。所以我有点惊讶运行时也没有出现在你的担忧清单上。

一种想法是存储矩阵逆的低秩近似A1UV使用 SVD。如果AR30×30, 然后UR30×k & VRk×30, 在哪里k4,5是排名。使用UV近似作为求解系统的前置条件Ax=b使用 GMRES。您可以使用不同的k作为一个调优参数,在内存和收敛速度之间进行权衡。