An improved LLL algorithm

DOI10.1016/J.LAA.2007.02.029MaRDI QIDQ2465313zbMATH OpenOpenAlexFDO

Authors Franklin T. Luk, Daniel M. Tracy

Publication date 3 January 2008

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2007.02.029

zbMATH Keywords

integer least squaresoverdetermined systemspseudoinversesreduced basisunimodular transformation

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Review text

The paper is devoted to the presentation of a new way to look at the reduction algorithm of \textit{A. K. Lenstra, H. W. Lenstra jun.} and \textit{L. Lovasz} [(LLL); Math. Ann. 261, 515--534 (1982; Zbl 0488.12001)] which leads to a new implementation method that performs better than the original scheme of this algorithm. In the beginning of the paper, the idea of the reduced basis and the LLL algorithm are presented based on the description of the problem of integer lest squares. Next, the idea of a reduced basis is extend to that of a reduced triangular matrix, and a new algorithm is presented based on this extension. It is shown that the two methods (the LLL reduction algorithm and the proposed new one) are producing identical numerical results in exact arithmetic. The only difference lies in the used transformation. Some numerical examples are given to illustrate how the numerical results produced by the proposed new method can be significantly better than those produced by the original LLL scheme.

Recommendations

• A modification of the LLL reduction algorithm
• Fast LLL-type lattice reduction
• scientific article; zbMATH DE number 3958726
• An LLL algorithm with quadratic complexity
• A pivoted LLL algorithm

Cites work

• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications
• On the sphere-decoding algorithm I. Expected complexity

Cited in

(19)

• A modification of the LLL reduction algorithm
• Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems
• A pivoted LLL algorithm
• An Improvement of the Elliptic Net Algorithm
• Matrices and the LLL algorithm
• A comparative study of the LLL algorithm
• Efficient lattice reduction updating and downdating methods and analysis
• On LLL lattice basis reduction over imaginary quadratic fields by introducing reduction parameters
• An Efficient LLL Gram Using Buffered Transformations
• Solving ellipsoid-constrained integer least squares problems
• Loop-reduction LLL algorithm and architecture for lattice-reduction-aided MIMO detection
• Boosted KZ and LLL Algorithms
• Effect of the interval-symbol method with correct zero rewriting on the -LLL algorithm
• An efficient algorithm for clustered integer least squares problems.
• The history of the LLL-algorithm
• Recovering exact results from inexact numerical data in algebraic geometry
• A modified LLL algorithm for GPS integer ambiguity decorrelation
• A new method for lattice reduction using directional and hyperplanar shearing
• Parallel Cholesky-based reduction for the weighted integer least squares problem

This page was built for publication: An improved LLL algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465313)