加乘运算次数最少的符号化简

Question

最近，我不得不处理很多长符号表达式的算法，比如这个

upperside = (    e * e * n * p * tn * tn + 
             2 * e * e * n * p * tn * tp +  
                 e * e * n * p * tp * tp + 
             2 * e * n * n * p * te * tn + 
             2 * e * n * n * p * te * tp +
                 N * e * n * n * tp * tp + 
             2 * e * n * p * p * te * tn +
             2 * e * n * p * p * te * tp - 
             2 * N * e * n * p * tn * tp + 
                 N * e * p * p * tn * tn +
                 n * n * n * p * te * te + 
             2 * n * n * p * p * te * te + 
                 n * p * p * p * te * te)

重新格式化

^{pr2}$

这些表达式是经过简化后由MATLAB符号程序导出的。很明显，在这种情况下，不可能通过合并因子来简化代数表达式。然而，似乎很有可能简化这个表达式，从而大大减少实际操作的数量。不幸的是，我在MATLAB或Python中找不到这样的选项。在

感谢任何帮助。在

编辑 我们的目标是最小化CPU需要为这些表达式执行的操作。因为运算只涉及加法和乘法，所以我希望像（e+tn）*（te+tp）+n+。。。。我试过对表达式进行因子分解，但不幸的是，表达式不能分解。在

Answer 1

公共子表达式消除（或sympy cse）计算乘积，如：ee和ep和加法。这有助于找到一个非常优化的表达式。我看到一个巨大的表达式，有三种不同的数学方法，计算时间有很大的不同。使用cse后，3种配方在计算时间上几乎相同。而且一些大的因素更快，比最快的非优化算法。在

Answer 2

如果有任何python包可以提供帮助，那么它可能是Sympy：

from sympy import init_printing, symbols, simplify, collect, factor

e,n,p,tn,te,tp,N = symbols("e,n,p,tn,te,tp,N")

upperside = (e * e * n * p * tn * tn + 
         2 * e * e * n * p * tn * tp +
             e * e * n * p * tp * tp + 
         2 * e * n * n * p * te * tn + 
         2 * e * n * n * p * te * tp +
             N * e * n * n * tp * tp + 
         2 * e * n * p * p * te * tn +
         2 * e * n * p * p * te * tp - 
         2 * N * e * n * p * tn * tp + 
             N * e * p * p * tn * tn +
             n * n * n * p * te * te + 
         2 * n * n * p * p * te * te + 
             n * p * p * p * te * te)

print collect(upperside, e*n)

It输出：

^{pr2}$

在page中描述的所有方法中，collect看起来最有希望。在

这里有一种快速而肮脏的方法来迭代所有符号组合并显示找到的最短表达式：

from sympy import init_printing, symbols, collect, pprint
import itertools

init_printing()

e,n,p,tn,te,tp,big_n = symbols("e,n,p,tn,te,tp,big_n")

upperside = (e * e * n * p * tn * tn + 2 * e * e * n * p * tn * tp +
                 e * e * n * p * tp * tp + 2 * e * n * n * p * te * tn + 2 * e * n * n * p * te * tp +
                 big_n * e * n * n * tp * tp + 2 * e * n * p * p * te * tn +
                 2 * e * n * p * p * te * tp - 2 * big_n * e * n * p * tn * tp + big_n * e * p * p * tn * tn +
                 n * n * n * p * te * te + 2 * n * n * p * p * te * te + n * p * p * p * te * te)

my_symbols = [e, n, p, tn, te, tp, big_n]

min_length = float('inf')

for i in range(len(my_symbols)):
  for symbol_subsets in itertools.combinations(my_symbols, i+1):
      collect_by = '*'.join(str(symbol) for symbol in symbol_subsets)
      expression = collect(upperside, collect_by)
      length = len(str(expression))
      if length < min_length:
          min_length = length
          print "With '%s' :" % collect_by
          pprint(expression)
          print

It输出：

With 'e' :
e**2*(n*p*tn**2 + 2*n*p*tn*tp + n*p*tp**2) + e*(big_n*n**2*tp**2 - 2*big_n*n*p*tn*tp + big_n*p**2*tn**2 + 2*n**2*p*te*tn + 2*n**2*p*te*tp + 2*n*p**2*te*tn + 2*n*p**2*te*tp) + n**3*p*te**2 + 2*n**2*p**2*te**2 + n*p**3*te**2

With 'n' :
big_n*e*p**2*tn**2 + n**3*p*te**2 + n**2*(big_n*e*tp**2 + 2*e*p*te*tn + 2*e*p*te*tp + 2*p**2*te**2) + n*(-2*big_n*e*p*tn*tp + e**2*p*tn**2 + 2*e**2*p*tn*tp + e**2*p*tp**2 + 2*e*p**2*te*tn + 2*e*p**2*te*tp + p**3*te**2)

With 'e*n' :
big_n*e*p**2*tn**2 + e**2*n*(p*tn**2 + 2*p*tn*tp + p*tp**2) + e*n**2*(big_n*tp**2 + 2*p*te*tn + 2*p*te*tp) + e*n*(-2*big_n*p*tn*tp + 2*p**2*te*tn + 2*p**2*te*tp) + n**3*p*te**2 + 2*n**2*p**2*te**2 + n*p**3*te**2

With 'e*n*p' :
big_n*e*n**2*tp**2 - 2*big_n*e*n*p*tn*tp + big_n*e*p**2*tn**2 + e**2*n*p*(tn**2 + 2*tn*tp + tp**2) + e*n**2*p*(2*te*tn + 2*te*tp) + e*n*p**2*(2*te*tn + 2*te*tp) + n**3*p*te**2 + 2*n**2*p**2*te**2 + n*p**3*te**2