Euclidean lattice basis reduction: algorithms and experiments for disclosing integer relations

We review polynomial time approaches for computing simultaneous integer relations among real numbers. A variant of the LLL lattice reduction algorithm (A. Lenstra, H. Lenstra, L. Lovász, 1982), the HJLS (J. Hastad, B. Just, J. Lagarias, J. and C.P. Schnorr, 1989) and the PSLQ (H. Ferguson, D. Bailey, 1992) algorithms are de facto standards for solving the problem. We investigate the links between the various approaches and present intensive experiment results. We especially focus on the question of the precision for the underlying floating-point procedures used in the currently fastest known algorithms and software libraries. Part of this work is done in collaboration with Stehlé in relation with the fplll library, and with D. Stehlé and J. Chen for the HJLS/PSLQ comparison