PSLQ Algorithm

An Algorithm which finds Integer Relations between real numbers $x_1$, ..., $x_n$ such that

$$a_1x_1+a_2x_2+\ldots+a_nx_n=0,$$

with not all $a_i=0$. This algorithm terminates after a number of iterations bounded by a polynomial in $n$ and uses a numerically stable matrix reduction procedure (Ferguson and Bailey 1992), thus improving upon the Ferguson-Forcade Algorithm. It is based on a partial sum of squares scheme (like the PSOS Algorithm) implemented using LQ decomposition. A much simplified version of the algorithm was developed by Ferguson et al. and extended to complex numbers.

See also Ferguson-Forcade Algorithm, Integer Relation, LLL Algorithm, PSOS Algorithm

References

Bailey, D. H.; Borwein, J. M.; and Girgensohn, R. ``Experimental Evaluation of Euler Sums.'' Exper. Math. 3, 17-30, 1994.

Bailey, D. and Plouffe, S. ``Recognizing Numerical Constants.'' http://www.cecm.sfu.ca/organics/papers/bailey/.

Ferguson, H. R. P. and Bailey, D. H. ``A Polynomial Time, Numerically Stable Integer Relation Algorithm.'' RNR Techn. Rept. RNR-91-032, Jul. 14, 1992.

Ferguson, H. R. P.; Bailey, D. H.; and Arno, S. ``Analysis of PSLQ, An Integer Relation Finding Algorithm.'' Unpublished manuscript.