Name
Abstract | ||
|---|---|---|
We describe a new LLL-type algorithm, H-LLL, that relies on Householder transformations to approximate the underlying Gram-Schmidt orthogonalizations. The latter computations are performed with floating-point arithmetic. We prove that a precision essentially equal to the dimension suffices to ensure that the output basis is reduced. H-LLL resembles the L2 algorithm of Nguyen and Stehlé that relies on a floating-point Cholesky algorithm. However, replacing Cholesky's algorithm by Householder's is not benign, as their numerical behaviors differ significantly. Broadly speaking, our correctness proof is more involved, whereas our complexity analysis is more direct. Thanks to the new orthogonalization strategy, H-LLL is the first LLL-type algorithm that admits a natural vectorial description, which leads to a complexity upper bound that is proportional to the progress performed on the basis (for fixed dimensions). |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1576702.1576740 | ISSAC |
Keywords | Field | DocType |
floating-point arithmetic,householder transformation,complexity analysis,floating-point cholesky algorithm,l2 algorithm,new lll-type algorithm,lll-type algorithm,output basis,new orthogonalization strategy,correctness proof,lattice reduction,floating point arithmetic,floating point,upper bound | Discrete mathematics,Floating point,Upper and lower bounds,Algorithm,Householder's method,Householder transformation,Orthogonalization,Lattice reduction,Mathematics,Cholesky decomposition,Computation | Conference |
Citations | PageRank | References |
17 | 1.00 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ivan Morel | 1 | 17 | 1.00 |
| Damien Stehlé | 2 | 1269 | 73.95 |
| Gilles Villard | 3 | 565 | 48.04 |