加速超大型 ODE 系统的求解

计算科学
2021-12-12 06:26:37

我需要解决许多非常大的一阶 ODE 系统,它们描述了一些化学反应。变量的数量(在每个系统中)大约为n105. 我正在使用ALGLIB向量 ODE 求解器,它在后台实现Cash-Karp 自适应 ODE 求解器

化学方程式通常被认为是僵硬的,建议使用隐式方法。不幸的是,隐式方法无法处理如此数量的变量,因为它们需要反转巨大的矩阵。这反过来又需要n3操作只是开始,那是在考虑舍入误差之前。上次当我“玩”一个订单较小的矩阵时(n104),我需要大约 50 位数的精度才能获得合理正确的结果。当前处理器本身并不支持这种精度,并且所有这些都有效地排除了这种数量变量的隐式方法。

另一方面,自适应显式方法,如 ALGLIB 中使用的方法,计算误差并将步长减少到非常小的数字。这通常会使解决时间变得异常长(比如几个月)。

我的猜测是,当某些变量开始接近零时会发生这种情况。由于所有变量都必须是严格的非负数(它们是某些物质的浓度),一旦它们中的一些接近于零,那么相对误差就会立即变得非常大,算法就会减小步长。事实上,该算法通常会超调零,从而使一些变量为负数。在那之后,一切都会爆炸。因此,在计算导数时,我将所有小于零的变量视为精确零。这使得算法稳定,但仍然没有删除它可能会过多地减少步长的事实。

单个 ODE 系统的并行化不能很好地工作,或者,容我说,根本不能工作。这是因为 ODE 求解器反复调用一个相当快速的函数来计算导数。此类函数仅基于纯数学,并且对于此类函数(即使输入数组为n105大小)并行化开销只是扼杀了目的。相反,并行化是通过同时生成多个模型来实现的,其中每个模型在单个线程下运行。这可以通过产生多个线程或多个外部进程来完成(每个线程/进程运行一个“模型”)。两者都有一些优点和缺点,这与问题无关。底线是并行化单个模型会降低性能。

系统具有运动积分:系统中的总数或“原子”(所有变量的总和乘以某些权重)必须是常数。并且由于所有变量都是严格非负的,这导致了导数的上限。

我想知道如何才能更快地解决此类 ODE 系统。

2个回答

如果您想要一个处理任意精度的并行线性代数库,我对Elemental有好运这可能允许您使用隐式方法。

我使用自己的fork将 MPFR 替换为 GMP(大约快 2 倍,但并非所有操作都有效)。LLNL还有另一个分叉,但我不知道它的效果如何。

Elemental 支持大量的操作。这里有一些文档我也有文档存储库的副本,但您必须自己构建它。最初的开发者几年前就停止了工作,所以支持基本上是自助服务。

按照@BillGreene 提出的想法,我将一个小的 C# NET5 互操作放到 FORTRAN ODE Solver DLSODE:https ://github.com/kkkmail/OdePackInterop 。互操作包括 C# 测试和相同的 F# 测试,用于具有 100,001 个变量的类似化学的系统。变量的数量可以通过命令行调整。结果是不言自明的。

有效的方法是在计算导数时将所有负值视为精确零(以下称为非负约束)并使用“功能”校正器迭代器(在 DLSODE 中称为)。“Adams”和“Bdf”求解器方法之间似乎没有太大区别,尽管“Adams”似乎快一点。

另一个校正迭代器候选者“对角雅可比弦”在所有测试中都没有保持运动积分。然而,它很接近,并且运动积分仅在第三位上发生偏差(与功能求解器相比,它以超过 10 位以上的精度保存)。

DLSODE 求解器中的所有其他校正器迭代器和该包中的所有其他求解器都需要完整或带状雅可比行列式,这将显着增加计算时间,更不用说在 NET 和 FORTRAN 之间执行互操作时处理多维数组中的行/列交换的挑战. 随后,他们被排除在外。

2021-03-27 更新

当上面提到的求解器遇到真正的化学问题时,事情发生了变化,这些问题大约有 10^5 个变量。

每个[某些特定]模型的估计平均运行时间(或求解器完成时的实际运行时间)如下(假设模型在单线程中运行):

AlgLib / Cash-Carp / Use non-negativity constraint: 大约 8,000 计算机年。步长变得异常小,这就解释了为什么它停滞不前。

DLSODE / (Adams or BDF) / Functional / Use non-negativity constraint: 大约 2.5 计算机年。它会在没有非消极约束的情况下爆炸。

DLSODE / BDF / "Chord with diagonal Jacobian"/ Use non-negativity constraint:半天到两天之间(取决于型号)。那是唯一一个在合理的时间内完成的。而且它也会在没有非消极约束的情况下爆炸。