PSLQ Algorithm

An algorithm which can be used to find integer relations between real numbers , ..., such that

with not all . Although the algorithm operates by manipulating a lattice, it does not reduce it to a short vector basis, and is therefore not a lattice reduction algorithm. PSLQ is based on a partial sum of squares scheme (like the PSOS algorithm) implemented using QR decomposition. It was developed by Ferguson and Bailey (1992). A much simplified version of the algorithm was subsequently developed by Ferguson et al. (1999), which also extends the algorithm to complex numbers and quaternions. Ferguson et al. (1999) also demonstrated that PSLQ is distinct from the HJLS algorithm.

The PSLQ algorithm terminates after a number of iterations bounded by a polynomial in and uses a numerically stable matrix reduction procedure (Ferguson and Bailey 1992). PSLQ tends to be faster than the Ferguson-Forcade algorithm and LLL algorithm because of clever techniques that allow machine arithmetic to be used at many intermediate steps. The LLL algorithm, by comparison, must use moderate precision, although generally not as much as the HJLS algorithm.

While the LLL algorithm is a more general lattice reduction algorithm than PSLQ, using LLL to obtain integer relations is in some sense a "trick," whereas with PSLQ one gets either a relation or lower bounds on degrees of polynomials and sizes of coefficients for which such a relation must satisfy.