优化一组多项式以提高计算速度

Question

优化一组多项式以提高计算速度

performancealgorithmoptimizationpolynomialscomputer-algebra-systems

5

我有一组由计算机代数系统（CAS）生成的多项式表达式。例如，这是这个集合中的一个元素。

-d*d*l*l*q-b*b*l*l*q+2*d*f*j*l*q+2*b*f*h*l*q-f*f*j*j*q-b*b*j*j*q+2*b*d*h*j*q-f*f*h*h*q-d*d*h*h*q+b*b*j*j*o*o-2*b*d*h*j*o*o+d*d*h*h*o*o-2*b*b*j*l*n*o+2*b*d*h*l*n*o+2*b*f*h*j*n*o-2*d*f*h*h*n*o+2*b*d*j*l*m*o-2*d*d*h*l*m*o-2*b*f*j*j*m*o+2*d*f*h*j*m*o+b*b*l*l*n*n-2*b*f*h*l*n*n+f*f*h*h*n*n-2*b*d*l*l*m*n+2*b*f*j*l*m*n+2*d*f*h*l*m*n-2*f*f*h*j*m*n+d*d*l*l*m*m-2*d*f*j*l*m*m+f*f*j*j*m*m

我需要在C程序中尽可能快地执行它们。如果仔细观察这些公式中的任何一个，就会发现我们可以优化它们的计算速度。例如，在上面粘贴的多项式中，我立即可以看到术语-d*d*l*l*q、2*d*f*j*l*q和-f*f*j*j*q，因此我可以用-q*square(d*l-f*j)来替换它们的总和。我相信在这里有很多这样的事情可以做。我不相信（但也许我错了）任何编译器都能找到这种优化，或者更高级的编译器。我试图请maxima（一个CAS）为我做这件事，但没有结果（因为我是maxima的初学者，也许我错过了一个神奇的命令）。所以，我的第一个问题是：我们可以使用什么工具/算法来优化多项式表达式的计算速度？

当优化一组共享大部分变量的多项式表达式时，事情变得更加复杂。实际上，逐个优化表达式可能是次优的，因为在优化之前，编译器可以识别出共同的部分，但在整体优化后就不能再识别了。因此，我的第二个问题是：我们可以使用什么工具/算法来优化一组多项式表达式的计算速度？

此致敬礼，

P.S. : 这篇文章与 "计算机代数软件来最小化一组多项式的操作数量" 有一些相似之处，但是那篇文章给出的答案指向了CAS程序，而不是说明我们如何使用它们来实现我们的目标。

- S. Piérard

1

这似乎是一个非常基础和常见的问题，如果大多数计算机代数系统不能至少为您进行部分简化，我会感到非常惊讶。 - biziclop

2

@biziclop，我并不指望在计算机代数系统中找到一个叫做“以最佳方式为计算机写多项式”的方法，因为它们根本不关心执行时间（这是编译器相关人员更关注的领域），而且这也不能帮助数学家们。我提到我尝试过Maxima只是想表达出即使得不到最优解，我仍然会满意接近最优解的算法。 - Sébastien Piérard

@hardmath：这是真的，但在帖子中有一堆这样丑陋的表达方式会有所帮助吗？如果有的话，我可以提供一些其他的，但这只是一个普遍问题的特定案例。我将一个多项式排序，以便读者能够在他拥有的软件中进行复制粘贴，并在回答之前尝试自己的想法。 - Sébastien Piérard

1

我认为这个问题可能是 NP 完全问题——它类似于“通过移位和加法最小化乘以一个常量所需的操作次数”，我记得从大学讲座上说过，这是 NP 完全问题（但对于小的常数仍然可被求解，因此编译器有时会进行穷举测试）。因此，你可能想要编写一种贪心算法，配合回溯，如果效果不好，则尝试找到额外的约束条件，使你能够更早地终止测试（虽然我不确定具体是什么，但这似乎是一个约束满足问题，因此您可以使用标准启发式算法）。 - user541686

1

根据您使用的编译器，它可以在类似这样的情况下进行的优化程度可能会让您感到惊讶。如果您想尝试编写一个程序，以执行高级编译器将要在前期完成的相同类型的简化操作，您应该搜索“DAGs”和“常见子表达式”。 - 500 - Internal Server Error

显示剩余10条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- biziclop · Answer 1

作为第一次尝试，我可能会尝试贪心算法。

因此，使用您的第一个示例，我们从这里开始：

 -1*d*d*l*l*q
 -1*b*b*l*l*q
  2*d*f*j*l*q
  2*b*f*h*l*q
 -1*f*f*j*j*q
 ...

现在尝试找到术语中最重复的模式。这是q，幸运的是它存在于所有术语中。让我们将其删除，这样就只剩下

 -1*d*d*l*l
 -1*b*b*l*l
  2*d*f*j*l
  2*b*f*h*l
 -1*f*f*j*j
 ...

现在再做一遍同样的事情，这次我们得到l，问题分成了两个子问题。

 -1*d*d*l
 -1*b*b*l
  2*d*f*j
  2*b*f*h
  ---------
 -1*f*f*j*j
 ...

重复递归直到没有重复项，并跟踪您的步骤，您可以递归地重构表达式的简化版本：

 q*(l*<first subproblem>+<second subproblem>)

正如你所看到的，这个解决方案不一定是最优的，但它很容易实现，可能已经足够好了。如果你需要一个更好的解决方案，那么你可能需要探索更多的组合，并根据你节省的乘法数量对它们进行排序，但总体概念是相同的。