Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Perturbation Analysis of the QR factor R in the context of LLL lattice basis reduction


Authors: Xiao-Wen Chang, Damien Stehlé and Gilles Villard
Journal: Math. Comp. 81 (2012), 1487-1511
MSC (2010): Primary 11H06, 65F25; Secondary 11Y99, 65F35
Published electronically: February 17, 2012
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 factorization of the basis matrix. In order to circumvent the use of rational/exact arithmetic with large bit-sizes, it is tempting to consider using floating-point arithmetic with small precision to compute 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 columnwise perturbations.

Our results are very useful to devise LLL-type algorithms relying on
floating-point approximations.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11H06, 65F25, 11Y99, 65F35

Retrieve articles in all journals with MSC (2010): 11H06, 65F25, 11Y99, 65F35


Additional Information

Xiao-Wen Chang
Affiliation: School of Computer Science, McGill University Montreal, Quebec, Canada H3A 2A7
Email: chang@cs.mcgill.ca

Damien Stehlé
Affiliation: CNRS, Université de Lyon, Laboratoire LIP, CNRS-ENSL-INRIA-UCBL, 46 Allée d’Italie, 69364 Lyon Cedex 07, France
Email: damien.stehle@ens-lyon.fr

Gilles Villard
Affiliation: CNRS, Université de Lyon, Laboratoire LIP, CNRS-ENSL-INRIA-UCBL, 46 Allée d’Italie, 69364 Lyon Cedex 07, France
Email: gilles.villard@ens-lyon.fr

DOI: http://dx.doi.org/10.1090/S0025-5718-2012-02545-2
PII: S 0025-5718(2012)02545-2
Keywords: lattice reduction, LLL, QR factorization, perturbation analysis
Received by editor(s): September 4, 2009
Received by editor(s) in revised form: March 17, 2011
Published electronically: February 17, 2012
Additional Notes: Xiao-Wen Chang’s work was supported by NSERC of Canada Grant RGPIN217191-07
Damien Stehlé’s work was partly funded by the LaRedA ANR project
Gilles Villard’s work was partly funded by the Gecko ANR project
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.