3.4 Algorithm
The simplest way to compute ℙ(Hn ≥ a) is to use the algorithm 2 in our particular case. As the number of non zero terms in R is then a2, the resulting complexity is O(n × a2). Using the proposition 4, it possible to get the same result a bit faster on very long sequence by computing the first two largest eigenvalues magnitudes λ and ν (complexity in O(a2) with Arnoldi algorithms) and to use them to compute a p-value.
As the absolute error is in O(να) we obtain a require ε error level using a α proportional to log(ε)/log(ν) which results in a final complexity in O(log(ε)/log(ν) × a2). Unfortunately, this last method requires to use delicate linear algebra techniques and is therefore more difficult to implement. Another better possibility is to use the corollary 5 to get the following fast and easy to implement algorithm:
algorithm 3: local score p-value
x a real column vector of size a, (pi)i≥1 and (λi)i≥3 to sequences of real and i an integer
initialization x = [g(a),...,g(1)]', p1 = g(a), and i = 0
main loop while (i <n and (λi) has not yet converged towards λ)
    • i = i + 1
    • x = R × x (sparse product)
    • pi = pi-1 + x1
    • λi = (pi - pi-1)/(pi-1 - pi-2) (if defined)
end • p = pi
    • if (i <n) then p = p + (pi - pi-1)
    • return p
At any step i of the main loop we have pi = ℙ(Hi ≥ a) and the final value taken by i is the α of proposition 4. One should note that only the last three terms of (pi)i≥1 and (for a simple convergence testing) the last two terms of (λi)i≥3 are required by the algorithm.