1
$\begingroup$

I have the following for-loop calculating a multiple nested sum

J = 12;
summed = Sum[(k + 4) k (k + 1), {k, 1, m}];
For[j = 1, j <= J, j++, 
summed = Sum[(m + 4 - j) (m - j) (m - j + 1) summed, {m, j + 1, k}];
summed = summed /. k -> m];

I don't think this is the right way to calculate recursive sums in Mathematica but a bigger problem is that for J>200 it becomes slow (several hours on a laptop). I am not sure why it is slow -- every loop increases the polynomial degree by 4 so there is no exponential explosion of terms to sum over.

How to rewrite it and mainly, how to make it fast? Can I hope for J~10000 ?

$\endgroup$
2
  • 1
    $\begingroup$ Please edit your example so that it is a working piece of code. $\endgroup$
    – halirutan
    Jan 20, 2015 at 2:10
  • $\begingroup$ Sorry, it is fixed now. $\endgroup$
    – user155002
    Jan 20, 2015 at 2:17

1 Answer 1

1
$\begingroup$

I rewrote the summation using Nest as follows.

J = 12; j = 0;
Nest[
     (j += 1;
      Sum[(m + 4 - j) (m - j) (m - j + 1) (# /. k -> m), {m, j + 1, k}]) &,
     m (1 + m) (2 + m) (17 + 3 m)/12,
J]

However, your For formulation is just as fast as this Nest.

$\endgroup$
3
  • $\begingroup$ Are high-degree polynomials the reason why it slows down or does Sum try to further simplify it? I realize that it must be slowing down as $j$ increases, I just don't understand why it is so for relatively small values of $J$. $\endgroup$
    – user155002
    Jan 20, 2015 at 12:18
  • $\begingroup$ When Sum is given a range with an undefined upper limit, k in your case, it tries to find the analytic solution, which takes time. The argument to Sum gets more and more complicated, so I assume this is where the slowdown arises. $\endgroup$ Jan 20, 2015 at 18:51
  • $\begingroup$ But the analytic formula for Sum[m^p, {m, j + 1, k}] is HurwitzZeta[-p, 1 + j] - HurwitzZeta[-p, 1 + k] and if I expand it by FunctionExpand[% /. p -> 3000] (to be able to multiply it and sum in the next round of the for-loop) it can do pretty fast. $\endgroup$
    – user155002
    Jan 20, 2015 at 19:04

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.