An improved LLL algorithm

Franklin T LUK; Daniel M. Tracy

doi:10.1016/j.laa.2007.02.029

An improved LLL algorithm

Franklin T LUK^*, Daniel M. Tracy

^*Corresponding author for this work

Research output: Contribution to journal › Journal article › peer-review

18 Citations (Scopus)

Abstract

The LLL algorithm has received a lot of attention as an effective numerical tool for preconditioning an integer least squares problem. However, the workings of the algorithm are not well understood. In this paper, we present a new way to look at the LLL reduction, which leads to a new implementation method that performs better than the original LLL scheme.

Original language	English
Pages (from-to)	441-452
Number of pages	12
Journal	Linear Algebra and Its Applications
Volume	428
Issue number	2-3
DOIs	https://doi.org/10.1016/j.laa.2007.02.029
Publication status	Published - 15 Jan 2008

User-Defined Keywords

Condition number
Gauss transformation
Integer least squares
LLL algorithm
Plane reflection
QR decomposition
Reduced basis
Unimodular transformation

Access to Document

10.1016/j.laa.2007.02.029

Cite this

@article{191efe26e3ab4a4798717e428330d884,

title = "An improved LLL algorithm",

abstract = "The LLL algorithm has received a lot of attention as an effective numerical tool for preconditioning an integer least squares problem. However, the workings of the algorithm are not well understood. In this paper, we present a new way to look at the LLL reduction, which leads to a new implementation method that performs better than the original LLL scheme.",

keywords = "Condition number, Gauss transformation, Integer least squares, LLL algorithm, Plane reflection, QR decomposition, Reduced basis, Unimodular transformation",

author = "LUK, {Franklin T} and Tracy, {Daniel M.}",

note = "Funding Information: ∗ Corresponding author. E-mail address: [email protected] (F.T. Luk). 1 This work was supported in part by DARPA/DSO under the Geo∗ program.",

year = "2008",

month = jan,

day = "15",

doi = "10.1016/j.laa.2007.02.029",

language = "English",

volume = "428",

pages = "441--452",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

number = "2-3",

}

TY - JOUR

T1 - An improved LLL algorithm

AU - LUK, Franklin T

AU - Tracy, Daniel M.

N1 - Funding Information: ∗ Corresponding author. E-mail address: [email protected] (F.T. Luk). 1 This work was supported in part by DARPA/DSO under the Geo∗ program.

PY - 2008/1/15

Y1 - 2008/1/15

N2 - The LLL algorithm has received a lot of attention as an effective numerical tool for preconditioning an integer least squares problem. However, the workings of the algorithm are not well understood. In this paper, we present a new way to look at the LLL reduction, which leads to a new implementation method that performs better than the original LLL scheme.

AB - The LLL algorithm has received a lot of attention as an effective numerical tool for preconditioning an integer least squares problem. However, the workings of the algorithm are not well understood. In this paper, we present a new way to look at the LLL reduction, which leads to a new implementation method that performs better than the original LLL scheme.

KW - Condition number

KW - Gauss transformation

KW - Integer least squares

KW - LLL algorithm

KW - Plane reflection

KW - QR decomposition

KW - Reduced basis

KW - Unimodular transformation

UR - http://www.scopus.com/inward/record.url?scp=36049050396&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2007.02.029

DO - 10.1016/j.laa.2007.02.029

M3 - Journal article

AN - SCOPUS:36049050396

SN - 0024-3795

VL - 428

SP - 441

EP - 452

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - 2-3

ER -

An improved LLL algorithm

Abstract

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this