H-LLL: Using Householder Inside LLL

Ivan Morel, Damien Stehle, Gilles Villard

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

20 Citations (Scopus)

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). Copyright 2009 ACM.
Original languageEnglish
Title of host publicationProceedings of the 2009 International Symposium on Symbolic and Algebraic Computation (ISSAC 2009)
EditorsJeremy Johnson, Erich Kaltofen, Hyungju Park
Place of PublicationNew York, United States
PublisherACM
Pages271-278
Number of pages8
ISBN (Print)9781605586090
DOIs
Publication statusPublished - 2009
EventThe 2009 International Symposium on Symbolic and Algebraic Computation (ISSAC 2009) - Seoul, Korea
Duration: 28 Jul 200931 Jul 2009

Conference

ConferenceThe 2009 International Symposium on Symbolic and Algebraic Computation (ISSAC 2009)
CitySeoul, Korea
Period28/07/0931/07/09

Fingerprint Dive into the research topics of 'H-LLL: Using Householder Inside LLL'. Together they form a unique fingerprint.

Cite this