 |
 |
 |
 |
Journal articles
Perturbation Analysis of the QR Factor R in the Context of LLL Lattice Basis Reduction
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.
Cited literature [21 references]
https://hal-ens-lyon.archives-ouvertes.fr/ensl-00529425
Contributor : Gilles Villard <>
Submitted on : Thursday, April 7, 2011 - 4:28:46 PM
Last modification on : Tuesday, December 8, 2020 - 9:57:51 AM
Long-term archiving on: : Friday, July 8, 2011 - 2:38:04 AM
Contributor : Gilles Villard <>
Submitted on : Thursday, April 7, 2011 - 4:28:46 PM
Last modification on : Tuesday, December 8, 2020 - 9:57:51 AM
Long-term archiving on: : Friday, July 8, 2011 - 2:38:04 AM
File
qrperturb2011.pdf
Files produced by the author(s)