Skip to Main content Skip to Navigation
Conference papers

Some numerical considerations for lattice basis reduction

Gilles Villard 1, 2 
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Fastest algorithms and implementations for LLL basis reduction are highly hybrid symbolic-numeric. A "numerical engine" computes, via a orthogonalization process, the unimodular transformations that will improve the quality of the basis. Then, for example in the case of integer lattice bases, the transformations are applied in exact arithmetic. We focus on several aspects concerning the choice of the precision than can be used for the numerical computations. We present theoretical bounds based on reducedness perturbation results, and on a "fully numerical view" of the algorithms. This leads to new methods for certifying reducedness. We also adopt a practical point of view for looking at approches with a dynamical tuning of the precision, and at the difficulties for heuristically mastering the behavior of the codes when the precision is very low compared to theoretical requirements.
Complete list of metadata
Contributor : Gilles Villard Connect in order to contact the contributor
Submitted on : Thursday, May 22, 2014 - 8:31:33 AM
Last modification on : Friday, September 30, 2022 - 4:12:07 AM


  • HAL Id : ensl-00994751, version 1



Gilles Villard. Some numerical considerations for lattice basis reduction. Fields Institute Workshop on Hybrid Methodologies for Symbolic-Numeric Computation, Nov 2011, David R. Cheriton School of Computer Science, Waterloo, Ontario, Canada. ⟨ensl-00994751⟩



Record views