Коэффициентная функция медленная

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

Вот хак, который может сделать ваш код быстрым, но я не гарантирую, что он всегда будет работать правильно:

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];

EDIT 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

Возможно, следует добавить некоторую эвристику для поиска одномерных переменных, которые не взорвутся. Не похоже на предмет с высоким приоритетом.

Даниэль Лихтблау

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

тоже довольно быстро.

Answer 4

После некоторых экспериментов после ответа Рольфа Мартига, это, похоже, самый быстрый метод для такого типа выражения, как Sum[x^i, {i, 15}]^30:

SeriesCoefficient[expr, {x, 0, 234}]