5
$\begingroup$

When looking for the coefficients of an desired series, I found that the Coefficient function is very fast compared to other functions and methods. In the following summary, we find the different methods that I used, which have the same results:

M = 30; 
(*Expand with coefficient*)
Timing[Sum[
   b^i Coefficient[Sum[b^r Subscript[x, r], {r, 0, 100}]^M, b, i], {i,
     0, M}];]
(*Expand with the usual form of multinomial theorem \
https://en.wikipedia.org/wiki/Multinomial_theorem*)
f[j_, i_] := (Subscript[x, j])^i/i!;
Timing[Sum[
   b^r Total[
     M! Times @@ KeyValueMap[f, #] & /@ 
      Counts /@ IntegerPartitions[r, {M}, Range[0, r]]], {r, 0, M}];]

(*Expanding with series function*)
Timing[Normal[
   Series[Sum[b^r Subscript[x, r], {r, 0, 100}]^M, {b, 0, M}]];]
(*Expand with the nth derivative function*)

Timing[Sum[
   b^i (D[1/i! Sum[b^r Subscript[x, r], {r, 0, 100}]^M, {b, i}] /. 
      b -> 0 ) , {i, 0, M}];]

The computation times of each method are respectively:

{0.1875, Null}
{1., Null}
{8.64063, Null}
{95.1094, Null}

The question I am asking is which algorithm is used in the Coefficient function

$\endgroup$

1 Answer 1

4
$\begingroup$

This is not an answer, merely an extended comment

Clear["Global`*"]

For timing comparisons, RepeatedTiming (trimmed mean) is a more accurate (but slower) comparison. For smaller values of M (i.e., M < 12), the second method is quicker.

(*Expand with coefficient*)

t[1][M_] := 
 RepeatedTiming[
   res[1] = 
     Sum[b^i Coefficient[Sum[b^r Subscript[x, r], {r, 0, 100}]^M, b, i], {i, 
       0, M}];][[1]]

(*Expand with the usual form of multinomial theorem \
https://en.wikipedia.org/wiki/Multinomial_theorem*)
f[j_, i_] := (Subscript[x, j])^i/i!;
t[2][M_] := 
 RepeatedTiming[
   res[2] = 
     Sum[b^r Total[
        M! Times @@ KeyValueMap[f, #] & /@ 
         Counts /@ IntegerPartitions[r, {M}, Range[0, r]]], {r, 0, M}];][[1]]

max = 15;

llp = ListLinePlot[(t[#] /@ Range[max]) & /@ {1, 2},
  PlotLegends -> Placed[Automatic, {.3, .6}]]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.