Gröbner 基和多项式系统解决方案的基准

计算科学 参考请求 多项式 符号计算
2021-12-16 04:49:36

在最近的问题Solving system of 7 个非线性代数方程symbolically中,Brian Borchers 通过实验证实 Maple 可以求解 Matlab/Mupad 无法处理的多项式系统。过去我从该领域的工作人员那里听说 Maple 对 Gröbner 基和相关算法有一个高质量的实现(我认为这是这里使用的)。

所以我很想建议“Matlab 在这类问题上很慢,改用 Maple”,但我想有数据来支持这个说法。

是否有一组基准结果比较不同计算机代数系统中 Gröbner 基实现和多项式系统解决方案的速度和有效性?(Maple、Mathematica、Matlab 的符号工具箱等)。

3个回答

我在这里发布了一些基准: http ://www.cecm.sfu.ca/~rpearcea/mgb.html (存档副本

这些是针对总学位订单的。要解决系统问题,您通常需要做更多的工作。时间是针对 2015 年的典型中端台式机(Haswell Core i5 四核)。

单核上最快的系统是 Magma,它使用浮点算法和 SSE/AVX。Magma 是最强大的系统,因为它很好地实现了 FGLM 和 Groebner walk(未测试)。这些算法用于将总度数基础转换为具有三角形形式的字典基础。然后,您通常会将多项式分解为最低变量。

mgb 是 Maple 2016 中的 C 库,它实现了总度数和消除顺序的 F4 算法。当它使用多核时,其性能可与 Magma 相媲美。

FGb 是 Faugere 对 F4 的实现。这里测试的版本来自他的网站,比 Maple 中的版本快。

Giac 是一个具有 F4 实现的开源系统。有一篇论文描述它http://arxiv.org/abs/1309.4044

Singular 是一个开源系统,用于代数几何中的许多计算。这里的基准测试使用“modStd”,它是 Buchberger 算法的多模块版本。您可以看到 Buchberger 算法与 F4 没有竞争力。基本原因是 F4 摊销了所有单项式操作的成本。除此之外,Singular 对 FGLM 和 Groebner Walk 以及其他对求解有用的算法有相当好的实现。

谷歌搜索benchmark polynomial systems导致了一些成功,包括曼海姆大学的计算机代数基准计划可悲的是,其中大多数都已过时或已失效。最活跃的似乎是SymbolicData Wiki,但据我所知,它只收集基准问题,而不是基准结果

Axiom、Macsyma、Maple、Mathematica、MuPAD 和 Reduce 求解多项式系统的一些比较(可追溯到 1996 年)可以在Hans-Gert Gräbe,关于 Axiom、Macsyma、Maple、Mathematica、MuPAD 的多项式系统求解工具中找到,和减少,预印本 11/96 des Instituts für Informatik,德国莱比锡大学,1996 年 12 月结论是 Axiom、Maple 和 Reduce 获胜是因为他们使用了 Gröbner 基地(其他人此时没有),Maple 稍微领先于其他人。

SINGULAR 网站上还有一个旧比较,显示 SINGULAR 2.0(截至 2015 年 12 月为 4.0.2)击败 Maple 等。

另一方面,最近的出版物(Yao Sun、Dongdai Lin 和 Dingkang Wang。2015。关于使用 M4RI 的线性代数例程实现基于签名的 Gröbner 基算法。ACM Commun. Comput. Algebra 49, 2(2015 年 8 月) , 63-64比较了作者对 Gröbner 基算法的实现与 Maple、Singular 和 Magma 的实现,其中 Magma 比其他两个包快一个数量级(并且与作者的实现并列)。

因此,它似乎很大程度上取决于问题(大小和结构)以及哪个软件包最快的软件版本。尽管如此,使用积极开发的专用计算机代数系统(如 Singular、Magma 或 Maple)而不是通用符号计算软件的建议是合理的。这对于数字软件中的工具箱来说是双倍的,这增加了另一个级别的开销,并且通常是它们所基于的独立软件(MuPAD,以前的 Maple,在 Matlab 的工具箱的情况下)之后的几个版本。

永远记住,除了问题的大小之外,任何基准测试的结果都取决于定义多项式环的基域(有理数或整数模素数的某个幂)。

FGb 库是 F5 算法的积极开发和高性能实现。可以在以下位置找到将 FGb 与 Magma 进行比较的基准:

Faugère, J.-C. (2010)。FGb:计算 Gröbner 基的库(第 84-87 页)。doi:10.1007/978-3-642-15582-6_17