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.
Type de document :
Communication dans un congrès
Fields Institute Workshop on Hybrid Methodologies for Symbolic-Numeric Computation, Nov 2011, David R. Cheriton School of Computer Science, Waterloo, Ontario, Canada
Liste complète des métadonnées

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00994751
Contributeur : Gilles Villard <>
Soumis le : jeudi 22 mai 2014 - 08:31:33
Dernière modification le : jeudi 11 janvier 2018 - 06:23:43

Identifiants

  • HAL Id : ensl-00994751, version 1

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

66