3
$\begingroup$

There is a technique we developed for series acceleration using the Wilf-Zeilberger method. Here is a simple Maple code in this regard, you need to download this too.

The idea is you start with a WZ-pair $(F,G)$ and you get an infinite family of hypergeometric series that help compute your constant. Take for example, the Riemann zeta $\zeta(3)=\sum_{n=1}^{\infty}\frac1{n^3}$ which is slow in its rate of convergence. We are able to generate an endless list, call these $s$-step accelerations. The first few include: $$\zeta(3)=\frac52\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{\binom{2n}n\binom{n}nn^3} \tag {1-step}$$ $$\zeta(3)=\frac14\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{\binom{3n}n\binom{2n}nn^3}\frac{56n^2-32n+5}{(2n-1)^2} \tag {2-step}$$ $$\zeta(3)=\frac1{18}\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{\binom{4n}n\binom{3n}nn^3}\frac{5265n^4-7182n^3+3717n^2-828n+68}{(3n-1)^2(3n-2)^2} \tag {3-step}$$ This continues ad infinitum.

(1) At each step, we gain large binomial denominator (desirable);

(2) At each step, we incur a rational polynomial with increasing degrees.

Question. In view of the competing gain-loss, (1) and (2), does the computational complexity or efficiency improve or gets worse?

Caveat. I don't know much about Complexity Theory, hence my question here. Thank you for help.

$\endgroup$
1
$\begingroup$

This seems simple enough to test explicitly. For each of the series, compute several truncated sums and plot error vs. number of operations required.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I would imagine that computing the number of operations required isn't easy in general, especially if there are tricks which you don't know. How many operations does it take to compute (4n choose n) * (3n choose n), for example? Probably some ways are better than others. $\endgroup$ – Kevin Buzzard Jan 16 '17 at 19:53
  • 1
    $\begingroup$ Actually, I think that for the case in question it's a complete no-brainer. For the 3-step sum by the time you've taken 20 terms you're correct to about 37 decimal places, and for the first sum it would take something like $10^{12}$ terms to get that far. I am pretty confident that you can compute 80 choose 20 in fewer than $10^{12}$ steps :-) $\endgroup$ – Kevin Buzzard Jan 16 '17 at 20:01

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.