系数函数很慢

Question

请考虑:

Clear[x]
expr = Sum[x^i, {i, 15}]^30;

CoefficientList[expr, x]; // Timing
Coefficient[Expand@expr, x, 234]; // Timing
Coefficient[expr, x, 234]; // Timing

{0.047, Null}

{0.047, Null}

{4.93, Null}

帮助说明:

Coefficient 无论是否以扩展形式明确给出expr,都可以正常工作.

是否有一个原因,Coefficient需要在最后一种情况下这么慢？

Answer 1

这是一个hack,可以使您的代码快速,但我不保证它始终正常工作:

ClearAll[withFastCoefficient];
SetAttributes[withFastCoefficient, HoldFirst];
withFastCoefficient[code_] :=
   Block[{Binomial},
     Binomial[x_, y_] := 10 /; ! FreeQ[Stack[_][[-6]], Coefficient];
     code]

使用它,我们得到:

In[58]:= withFastCoefficient[Coefficient[expr,x,234]]//Timing
Out[58]= {0.172,3116518719381876183528738595379210}

我们的想法是,Coefficient在Binomial内部使用来估计术语的数量,然后Expand在术语数量小于的情况下扩展(调用)1000,您可以使用它来检查Trace[..., TraceInternal->True].当它不扩展时,它会计算大量由零支配的大系数列表的总和,对于一系列表达式,这显然比扩展慢.我做的是愚弄Binomial返回一个小数字(10),但我也尝试使它只会影响Binomial内部调用Coefficient:

In[67]:= withFastCoefficient[f[Binomial[7,4]]Coefficient[expr,x,234]]
Out[67]= 3116518719381876183528738595379210 f[35] 

但是,我不能保证没有示例Binomial代码中的其他地方将被错误地计算.

编辑

当然,一个总是存在的更安全的替代方案是重新定义Coefficient使用 Villegas - Gayley技巧,扩展其中的表达并再次调用它:

Unprotect[Coefficient];
Module[{inCoefficient},
   Coefficient[expr_, args__] :=
      Block[{inCoefficient = True},
         Coefficient[Expand[expr], args]] /; ! TrueQ[inCoefficient]
];
Protect[Coefficient];

编辑2

我的第一个建议有一个优点,我们定义了一个宏,它修改了本地函数的属性,但缺点是它不安全.我的第二个建议是更安全,但Coefficient全局修改,因此它将一直扩展,直到我们删除该定义.我们可以借助于两个世界中最好的东西 Internal`InheritedBlock,它创建给定函数的本地副本.这是代码:

ClearAll[withExpandingCoefficient];
SetAttributes[withExpandingCoefficient, HoldFirst];
withExpandingCoefficient[code_] :=
   Module[{inCoefficient},
      Internal`InheritedBlock[{Coefficient},
         Unprotect[Coefficient];
         Coefficient[expr_, args__] :=
            Block[{inCoefficient = True},
               Coefficient[Expand[expr], args]] /; ! TrueQ[inCoefficient];
         Protect[Coefficient];
         code
      ]
   ];

用法与第一种情况类似:

In[92]:= withExpandingCoefficient[Coefficient[expr,x,234]]//Timing
Out[92]= {0.156,3116518719381876183528738595379210}

但主要Coefficient功能不受影响:

In[93]:= DownValues[Coefficient]
Out[93]= {}

Answer 2

Coefficient除非认为绝对必要,否则不会扩大.这确实可以避免记忆爆炸.我相信自第3版以来就一直这样(我想我大约在1995年左右开始工作).

避免扩展也可以更快.这是一个简单的例子.

In[28]:= expr = Sum[x^i + y^j + z^k, {i, 15}, {j, 10}, {k, 20}]^20;

In[29]:= Coefficient[expr, x, 234]; // Timing

Out[29]= {0.81, Null}

但是下一个似乎在版本8中挂起,并且在开发Mathematica(Expand改变的地方)中需要至少半分钟.

Coefficient[Expand[expr], x, 234]; // Timing

可能应该添加一些启发式方法来寻找不会爆炸的单变量.虽然看起来不是一个高优先级的项目.

Daniel Lichtblau

Answer 3

expr = Sum[x^i, {i, 15}]^30; 

scoeff[ex_, var_, n_] /; PolynomialQ[ex, var] := 
   ex + O[var]^(n + 1) /. 
    Verbatim[SeriesData][_, 0, c_List, nmin_, nmax_, 1] :> 
     If[nmax - nmin != Length[c], 0, c[[-1]]]; 

Timing[scoeff[expr, x, 234]]

看起来也很快.