H-LLL: Using Householder Inside LLL
Ivan Morel, Damien Stehlé and Gilles Villard
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).
Download: pdf.
Homepage