Perturbation Analysis of the QR Factor R in the Context of LLL Lattice Basis Reduction

Xiao-Wen Chang 1 Damien Stehlé 2, 3, * Gilles Villard 2, 3, *
* Auteur correspondant
3 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In 1982, Arjen Lenstra, Hendrik Lenstra Jr. and László Lovász introduced an efficiently computable notion of reduction of basis of a Euclidean lattice that is now commonly referred to as LLL-reduction. The precise definition involves the R-factor of the QR factorisation of the basis matrix. A natural mean of speeding up the LLL reduction algorithm is to use a (floating-point) approximation to the R-factor. In the present article, we investigate the accuracy of the factor R of the QR factorisation of an LLL-reduced basis. Our main contribution is the first fully rigorous perturbation analysis of the R-factor of LLL-reduced matrices under column-wise perturbations. Our results should be very useful to devise LLL-type algorithms relying on floating-point approximations.
Type de document :
Article dans une revue
Mathematics of Computation, American Mathematical Society, 2012, 81 (279), pp.1487-1511
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00529425
Contributeur : Gilles Villard <>
Soumis le : jeudi 7 avril 2011 - 16:28:46
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : vendredi 8 juillet 2011 - 02:38:04

Fichier

qrperturb2011.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00529425, version 2

Collections

Citation

Xiao-Wen Chang, Damien Stehlé, Gilles Villard. Perturbation Analysis of the QR Factor R in the Context of LLL Lattice Basis Reduction. Mathematics of Computation, American Mathematical Society, 2012, 81 (279), pp.1487-1511. 〈ensl-00529425v2〉

Partager

Métriques

Consultations de la notice

792

Téléchargements de fichiers

190