Search code examples
performancewolfram-mathematicaexpand

Coefficient function is slow

Please consider:

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}

Help states:

Coefficient works whether or not expr is explicitly given in expanded form.

Is there a reason why Coefficient needs to be so slow in the last case?

Solution

  • Coefficient will not expand unless it deems it absolutely necessary to do so. This does indeed avoid memory explosions. I believe it has been this way since version 3 (I think I was working on it around 1995 or so).

    It can also be faster to avoid expansion. Here is a simple example.

    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}

    But this next appears to hang in version 8, and takes at least a half minute in the development Mathematica (where Expand was changed).

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

    Possibly some heuristics should be added to look for univariates that will not explode. Does not seem like a high priority item though.

    Daniel Lichtblau