优化一组多项式以获得计算速度

Question

我有一组由计算机代数系统(CAS)产生的多项式表达式.例如,这是该集合的一个元素.

-d*d*L*L*QB*B*L*L*Q + 2*d*F*Ĵ*L*Q + 2*b*表F*H*L*QF*F*Ĵ*Ĵ*QB*b*表Ĵ*∫*q + 2*b*表d*H*Ĵ*QF*F*H*H*QD*d*H*H*q + b*b*∫*∫*○*O-2*b*d*H*Ĵ*○*O + d*d*H*H*○*0-2*b*b*∫*L*N*O + 2*b*表d*H*L*n个*O + 2*b*表F*H*Ĵ*N*0-2*d*F*H*H*N*O + 2*b*表d*∫*L*M*0-2*d*d*H*L*M*0-2*b*表F*Ĵ*∫*M*O + 2*d*F*H*Ĵ*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*Ĵ*L*米*N + 2*d*F*H*L*m*n个-2*F*F*H*Ĵ*m*n个+ d*d*L*L*m*m的-2*d*F*Ĵ*L*M*M + F*F*Ĵ*Ĵ*m*m的

我需要尽快在C程序中执行所有这些操作.如果你仔细研究这些公式中的任何一个,很明显我们可以优化它们的计算速度.例如,在上面粘贴的多项式中,我可以立即看到术语-d*d*l*l*q,2*d*f*j*l*q和-f*f*j*j*q,这样我就可以用-q*square(d*lf*j)替换它们的总和.我相信这里可以做很多这样的事情.我不相信(但也许我错了)任何编译器都能找到这个优化,或者更高级的优化.我试图让maxima(一个CAS)为我做这个,但没有任何结果(因为我是极限初学者,我可能错过了一个神奇的命令).所以,我的第一个问题是:我们可以使用什么工具/算法来优化多项式表达式以获得计算速度？

当优化一组共享大多数变量的多项式表达式时,事情变得更加复杂.实际上,通过表达式优化表达式可能是次优的,因为在优化之前编译器可以识别公共部分,但是如果不作为整体执行则不再存在.所以,我的第二个问题是:我们可以使用哪些工具/算法来优化一组多项式表达式以获得计算速度？

最好的祝福,

PS:这篇文章与" 计算机代数软件以及最小化一组多项式中的操作数量 "有一些相似之处,但是那一点给出的答案指向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>)

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