计算机代数软件，用于最小化一组多项式中的运算次数

Question

我有多项式系统，相当简单的多项式表达式，但相当长 优化我的手牌。表达式按集合分组，在给定的集合中，多个变量中有共同的术语。

我想知道是否有一个计算机代数系统，例如 Mathematica、Matlab 或 sympy，可以优化多个具有常用项的多项式，以最大程度地减少运算次数。如果这样的系统能够最大限度地减少中间项的数量以减少寄存器的数量，那就太好了。

如果这样的系统不存在，我将使用 Python 符号代数 Sympy 自己做一个。如果您正在开发此类软件包或有兴趣开发或使用此类软件包，请告诉我。

这是一个虚构的示例

x0 = ((t - q*A)*x + B)*y
y0 = ((t - q*A)*y + B)*z
z0 = ((t - q*A)*z + B)*x

，因此您显然可以因式分解 (t - qA) 项。现在，如果您使用常见术语的各种组合来使术语数量非常大，那么用手来完成就变得很困难。我的方程涉及多达 40 个项，集合的大小约为 20 个。希望有帮助，

谢谢

Answer 1

sympy 是您要找的吗？我确实相信它支持多项式，尽管我不知道它是否支持您可能想要的所有功能（不过，调整它以添加您认为它可能缺少的功能必须比从头开始编写自己的功能更容易；-） 。

Answer 2

您考虑过Maxima吗？

它是一个令人印象深刻的符号计算包，是免费的、开源的，并且拥有强大而活跃的社区，可以在处理非显而易见的公式时提供宝贵的帮助。它适用于所有三个主要操作系统，并且具有预编译的 Windows 二进制文件。

您有多种可用于表达式和方程组（例如您的方程组）的代数操作命令：expand、factor、simple、ratsimp、linsolve 等。

此页面 (Maxima for Symbolic Computation）应该可以帮助您入门 - 下载、安装、一些示例，然后指出其他资源来指导您，包括快速命令参考/备忘单，以及一些编写您自己的脚本的指南。

Answer 3

Mathematica 当然可以对多项式方程组（例如您的方程组）进行各种变换，其中一些变换可能是为了减少项数。这对于您来说是否是正确的答案还有待商榷，因为您似乎没有可用的副本。我预计 Maple 和大多数其他 CAS 也是如此。

但你提到的

减少寄存器数量

表明您实际上正在尝试为编译进行一些数据流分析。您可能还想查看有关该主题的文献。其中一些文献确实提到了表达式的类似计算机代数的变换。

Answer 4

我迟到了，但无论如何，Maxima 中有一个优化函数（https:// /maxima.sourceforge.io），它标识常见的子表达式并发出可以评估的代码块。对于问题陈述中显示的示例，我得到：

(%i11) optimize ([x0 = ((t-A*q)*x+B)*y,
                  y0 = ((t-A*q)*y+B)*z,
                  z0 = x*((t-A*q)*z+B)]);

(%o11) block([%1], 
             %1 : t - A q, 
             [x0 = (%1 x + B) y, 
              y0 = (%1 y + B) z,
              z0 = x (%1 z + B)])

如您所见，t - A*q 被拉出并分配给虚构变量 %1 （百分号是 Maxima 中允许的符号字符），然后将其重新用于计算其他结果。

<代码>？在输入提示处优化显示了一些有关它的文档。