1
$\begingroup$

I am writing a code where I have to multiply large series truncated at some order, say 100. As a result I want again a series up to order 100, and I want to get it in the fastest way.

I have tried a number of approaches and I am wondering wether there is something better:

We start with

s1 = Series[ f1 , {x,0,100}] s2 = Series[ f2 , {x,0,100}]

and then I tried

1) p = s1 s2

2) p = Series[ Normal[s1] Normal[s2] // Expand, {x,0,100}]

3) p =Sum[Sum[s1[[3,l]] s2[[3,k-l]],{l,0,k}] ,{k,0,100}]

now, although a bit counter-intuitive for me, the second method seem to be the fastest. I don't understand why, since in this way I am computing many more terms than needed (from 200 to 100*100=10000). The third method takes much longer, altough is the minimal amount of computation I have to do, the first is somewhat in the middle.

Any explanation of what is going on? And advices on how to improve?

$\endgroup$
  • 2
    $\begingroup$ what is the definition of f1 and f2 ? at least,example is need. $\endgroup$ – Xminer Jul 12 '19 at 12:34
  • $\begingroup$ I think is irrelevant, they are just regular functions expanded at a regular point. If you prefer, just think of having directly s1 and s2 written as (regular) series of the form Sum_{i=0}^100 a_i x^i $\endgroup$ – giulio bullsaver Jul 12 '19 at 12:36
2
$\begingroup$

I tried the following code:

ClearAll[a, b, x, doit];
test[M_] := Module[{s1, s2},
  s1 = Series[Sum[a[n] x^n, {n, 0, M}], {x, 0, M}];
  s2 = Series[Sum[b[n] x^n, {n, 0, M}], {x, 0, M}];
  Print["1: ", Timing[s1*s2][[1]]];
  Print["2: ", Timing[Series[Normal[s1] Normal[s2], {x, 0, M}]][[1]]];
  Print["3: ", Timing[Series[
     Sum[Sum[ a[n - k] b[k], {k, 0, n}] x^n, {n, 0, M}], {x, 0, M}]][[1]]];
  Print["4: ", Timing[Series[
     Sum[ListConvolve[Array[a, n + 1, 0], Array[b, n + 1, 0]][[1]] x^n,
     {n, 0, M}], {x, 0, M}]][[1]]];

];

I tried test[300] twice. With a fresh kernel, the first time I got these timings:

1: 0.796875
2: 0.96875
3: 90.046875
4: 2.390625

and the second time I got these timings:

1: 0.796875
2: 0.8125
3: 3.328125
4: 2.265625

which is approximately consistent except for the 3rd method which was a surprise. Apparently, Mathematica keeps a cache of some computations. The first two methods are very similar in timing and the fastest. There are faster methods, using Compile, for example, if you have numeric coefficients. Some sample code that you can customize is:

f = Compile[{{M, _Integer}, {a, _Integer, 1}, {b, _Integer, 1}},
    Table[Sum[a[[k]] b[[n + 1 - k]], {k, n}], {n, M}]];
test2[M_] := Timing[f[M, Range[M], Range[M]^2]][[1]];
| improve this answer | |
$\endgroup$
  • $\begingroup$ Yeah mathematica keeps a cache, I noticed it as well and was very confusing! $\endgroup$ – giulio bullsaver Jul 12 '19 at 14:07
  • $\begingroup$ and yes we do have numeric coefficient, so Compile could be very useful. Could you provide more details about it? Anyway I am upvoting your answer already, thanks! $\endgroup$ – giulio bullsaver Jul 12 '19 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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