How does one calculate the amount of time required for computation?

For example, to compute the zeroes of the Riemann zeta function using the Euler-Maclaurin summation method one has to do O(T) work. The Euler-Maclaurin summation method for zeta is given by $\zeta(s)= \sum^{N-1}_{n=1} \frac{1}{n^{s}} + \frac{N^{1-s}}{s-1}+\frac{N^{-s}}{2}+\frac{B_2}{2}sN^{-s-1} +\ldots + \\ \frac{B_{2v}}{(2v)!} \frac{(s+2v-2)!}{(s-1)!}N^{-s-2v+1} + R_{2v}$

where

$R_{2v}=-\frac{s(s+1) \ldots (s+2v-1)}{(2v+1)!} \int^\infty_N B_{2v+1}(x-[x]-\frac{1}{2}x^{-s-2v-1} \mathrm{d} x.$

may be computed in O(t) time. The Riemann-Siegel formula counterpart may be computed in $O\sqrt(t)$ time. I haven't the first clue of why this is true and this concept of time taken for computations. Anybody care to direct me somewhere which would give an explanation? Thanks.

-

(this article is a kind of follow up of this introduction to $\zeta$ and this discussion about partial sums)

Let's compare the two proposed methods to evaluate $\zeta\left(s\right)$ with $s=\frac 12+i\,t\$ (Euler-Maclaurin may be applied everywhere, Riemann-Siegel may be used too if $\,\Re(s)\not =\frac 12$ but this is less documented) :

• Using Euler-Maclaurin you will need to compute the sum of at least the $\,N\approx \dfrac t{2\pi}\$ first terms to get an accurate result (ignoring the 'cost' of the few required Bernoulli terms and neglecting the remainder $R_{2v}$) from your expression : $$\zeta(s)= \sum^{N-1}_{n=1} \frac{1}{n^{s}} + \frac{N^{1-s}}{s-1}+\frac{N^{-s}}{2}+\frac{B_2}{2}sN^{-s-1} +\ldots + R_{2v}$$ To illustrate this let's add $3000$ terms ($\displaystyle 1,\,2^{-1/2-it},\,3^{-1/2-it},\cdots$) in the complex plane with the first term at the right at $1+0\,i$ and finishing near the middle at $0+0\,i\$ because I choose $t$ to be the first value larger than $10000$ such that $\zeta\left(\frac 12+i\,t\right)=0\,$. This gave the picture :

At this point let's apply the functional equation to the $N$ first terms of the series for $\zeta$ (consider every power term at $1-s$ instead of $s$ and multiply by $\gamma(1-s)$ as exposed at Wikipedia or at the bottom of this text) then we will get :

(in the simple case $\,\Re(s)=\frac 12\,$ this is merely a 'mirror effect' applied to the first picture : complex numbers are replaced by their conjugates and a global rotation depending smoothly of $t$ is applied)

Now let's superpose the second picture turned $180^\circ$ to the first one :

and observe the superposition of the first values (at the right on the first picture) to the final 'nodes' (at the left of the first picture).

• This is the whole point of the Riemann-Siegel formula : the last terms from a sum of $N$ terms contribute 'as much' as the first ones so that we need only to compute the sum up to the point where the two contributions are equal and this is about $\sqrt{N}$ terms.
Concretely you will need about $\,m\approx \sqrt{\dfrac t{2\pi}}\$ terms instead of the $\dfrac t{2\pi}$ terms from Euler-Maclaurin to evaluate $\zeta$ at $\frac 12+i\,t$.
More exactly the $m$ first terms of the sum for $\zeta(s)$ will be added to the $m$ first terms of the sum for $\zeta(s)$ using the functional equation : $\,\zeta(s)=\gamma(1-s)\zeta(1-s)\$ with $\displaystyle\gamma(s)=\pi^{1/2-s}\frac{\Gamma(s/2)}{\Gamma((1-s)/2)}$ to give the "approximate functional equation" : $$\zeta(s)=\sum_{n=1}^m\frac 1{n^s}+\gamma(1-s)\sum_{n=1}^m\frac 1{n^{1-s}} + R(s)$$ with and a not so easy to evaluate remainder : $$R(s)=\frac{\Gamma(1-s)}{2\pi i}\int_{C_m}\frac{(-x)^{s-1}e^{-mx}}{e^x-1}dx$$ (an approximation of this integral is needed for a precise evaluation)

The $\gamma$ notation used in the approximate functional equation is from Carl Erickson's very interesting and recommended article " A Geometric Perspective on the Riemann Zeta Function's Partial Sums".

For a formal derivation of these expressions your may consult too Titchmarsh's book about zeta or the chap.7 of Edwards' excellent book with a direct link to similar formulas here.

The details of actual computations are clearly exposed by Takusagawa and Gourdon&Sebah (for more see Edwards' book or Pugh's thesis.

-
Nice curlicues! –  Guess who it is. Apr 12 '13 at 13:00
Thanks @J.M. I have a generator for that ! –  Raymond Manzoni Apr 12 '13 at 13:15
Only very slightly related: have you by any chance seen Berry's papers on Riemann-Siegel? I have them, but haven't had the time to read them. My understanding was that he made a few tweaks to the formula to make it more efficient, but I haven't had the chance to test out that claim. –  Guess who it is. Apr 12 '13 at 13:22
Nice wall-paper. Look familiar? math.harvard.edu/~elkies/M229.09/index.html –  Andrew Sep 11 '13 at 22:00
@Andrew: The basic motif is deeper than you think. See this picture from Feynman's Masterpiece 'QED: The Strange Theory of Light and Matter. Quantum Electodynamics behaves this way as well as the other fundamental interactions QCD and Weak interactions ! (concerning gravity I don't know...) –  Raymond Manzoni Sep 11 '13 at 22:16