The Comparison

A detailed comparison of these (and many other) implementations of integer relation algorithms would require a much larger collection of experiments and would be a topic for a paper on its own. From the limited data that we have presented one can derive the following observations:

Numerical stability. PSLQ shows more stability, by having a clear-cut line between precisions at which the relation is not found and those where the relation is found. On the other hand, two of the three LLL-based algorithms that we have tried out were quite unstable in this sense.

Running time. Our tests were carried out on two different computers, which nonetheless are comparable in speed and performance.

Interestingly, theoretical results predict an asymptotically similar number of arithmetic operations for both types of algorithms (in both cases n is the dimension of the input vector):

• If B is a basis for the lattice L and b is the maximal length of vectors in B, then the LLL algorithm will find a reduced basis for L using $O(n^4\log b)$ arithmetic operations [32].

• If M_a is the minimum length among all existing integer relations for a given vector a, then the PSLQ algorithm will find a relation for ausing $O(n^4+n^3\log M_a)$ arithmetic operations  [25].

The large difference between the timings observed in Sections 4.3 and 4.2 can be partially accounted for by the fact that Bailey's PSLQ implementation is highly customized and compiled with a fast multiprecision library, whereas the LLL-based methods are implemented in (mostly interpreted) general purpose computer algebra systems. Another fact that apparently plays a great role here is that the numerical stability of PSLQ admits an efficient multi-level implementation using a combination of double precision and multiple precision arithmetic, at two or even three distinct levels of working precision.

Our general experience is that Bailey's PSLQ indeed runs much faster than the LLL implementations, and we definitely recommend using PSLQ for larger input vectors and/or higher numerical precision. For small cases, the LLL-based implementations are sufficient and probably easier to use, as they do not require installation of special software but rather come as parts of widespread mathematical software packages.