5

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

-d*d*l*l*qb*b*l*l*q+2*d*f*j*l*q+2*b*f*h*l*qf*f*j*j*qb *b*j*j*q+2*b*d*h*j*qf*f*h*h*qd*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*lf*j) 替换它们的总和。我相信这里可以做很多这样的事情。我不相信（但也许我错了）任何编译器都能够找到这种优化，或者可能是更高级的优化。我试图让 maxima（一个 CAS）为我做这件事，但没有任何结果（因为我是 maxima 的初学者，我可能错过了一个神奇的命令）。所以，我的第一个问题是：我们可以使用什么工具/算法来优化多项式表达式以提高计算速度？

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

此致，

PS：这篇文章与“计算机代数软件以最小化一组多项式中的运算数量”有一些相似之处，但是其中给出的答案指向 CAS 程序，而不是说我们如何使用它们来实现我们的目标。

4

1 回答 1

0

As a first attempt I'd probably try the greedy approach.

So using your first example we start with this:

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

Now try to find the most repeated pattern in the terms. This is q, which luckily is present in all of them. Let's remove it and that leaves us with

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

Now do the same thing again, this time we get l and the problem splits in two subproblems.

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

Repeat recursively until there's no repetition left and tracing your steps back you can recursively reconstruct a simplified version of the expression:

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

As you can already see, the solution won't necessarily be optimal but it's easy to implement and may be good enough. If you need a better one then you probably need to explore more combinations and rank them according to the number of multiplications you save but the general concept is the same.

于 2015-01-30T19:47:01.627 回答