Name
Title | ||
|---|---|---|
Perturbation Analysis of the QR factor R in the context of LLL lattice basis reduction. |
Abstract | ||
|---|---|---|
In 1982, Arjen Lenstra, Hendrik Lenstra Jr. and Laszlo Lovasz 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1090/S0025-5718-2012-02545-2 | MATHEMATICS OF COMPUTATION |
Keywords | Field | DocType |
lattice reduction,LLL,QR factorization,perturbation analysis | Discrete mathematics,Lattice (order),Perturbation theory,Matrix (mathematics),Factorization,Euclidean geometry,Mathematics,QR decomposition,Lattice reduction | Journal |
Volume | Issue | ISSN |
81 | 279 | 0025-5718 |
Citations | PageRank | References |
9 | 0.74 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiao-Wen Chang | 1 | 208 | 24.85 |
| Damien Stehlé | 2 | 1269 | 73.95 |
| Gilles Villard | 3 | 565 | 48.04 |