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

Question

我有一组由计算机代数系统 (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 的初学者，我可能错过了一个神奇的命令)。因此，我的第一个问题是:我们可以使用什么工具/算法来优化多项式表达式以提高计算速度？

在优化一组共享大部分变量的多项式表达式时，事情变得更加复杂。事实上，按表达式优化表达式可能不是最优的，因为编译器可以在优化之前识别公共(public)部分，但如果不作为一个整体执行，则在优化之后就不再识别了。因此，我的第二个问题是:我们可以使用什么工具/算法来优化一组多项式表达式以提高计算速度？

最好的问候，

附言:这篇文章与“computer algebra soft to minimize the number of operations in a set of polynomials”有一些相似之处，但是其中给出的答案指向 CAS 程序，而不是说明我们如何使用它们来实现我们的目标。

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>)

如您所见，解决方案不一定是最佳的，但它易于实现并且可能已经足够好了。如果您需要更好的组合，那么您可能需要探索更多组合并根据您保存的乘法次数对它们进行排序，但总体概念是相同的。