Numerical properties of the LLL algorithm

Franklin T LUK; Sanzheng Qiao

doi:10.1117/12.740194

Numerical properties of the LLL algorithm

Franklin T LUK, Sanzheng Qiao^*

^*Corresponding author for this work

Department of Mathematics

Research output: Chapter in book/report/conference proceeding › Conference contribution › peer-review

3 Citations (Scopus)

Abstract

The LLL algorithm is widely used to solve the integer least squares problems that arise in many engieering applications. As most practitioners did not understand how the LLL algorithm works, they avoided the issue by referring to the method as an integer Gram Schmidt approach (without explaining what they mean by this term). Luk and Tracy¹ were first to describe the behavior of the LLL algorithm, and they presented a new numerical implementation that should be more robust than the original LLL scheme. In this paper, we compare the numerical properties of the two different LLL implementations.

Original language	English
Title of host publication	Advanced Signal Processing Algorithms, Architectures, and Implementations XVII
DOIs	https://doi.org/10.1117/12.740194
Publication status	Published - 2007
Event	Advanced Signal Processing Algorithms, Architectures, and Implementations XVII - San Diego, CA, United States Duration: 26 Aug 2007 → 27 Aug 2007

Publication series

Name	Proceedings of SPIE - The International Society for Optical Engineering
Volume	6697
ISSN (Print)	0277-786X

Conference

Conference	Advanced Signal Processing Algorithms, Architectures, and Implementations XVII
Country/Territory	United States
City	San Diego, CA
Period	26/08/07 → 27/08/07

Scopus Subject Areas

Electronic, Optical and Magnetic Materials
Condensed Matter Physics
Computer Science Applications
Applied Mathematics
Electrical and Electronic Engineering

User-Defined Keywords

Gauss transformation
LLL algorithm
Numerical overflow and underflow
Plane reflection
QR decomposition
Reduced basis
Unimodular transformation

Access to Document

10.1117/12.740194

Cite this

@inproceedings{f08a3b524e1f4165b2e210cb1e5b80ca,

title = "Numerical properties of the LLL algorithm",

abstract = "The LLL algorithm is widely used to solve the integer least squares problems that arise in many engieering applications. As most practitioners did not understand how the LLL algorithm works, they avoided the issue by referring to the method as an integer Gram Schmidt approach (without explaining what they mean by this term). Luk and Tracy1 were first to describe the behavior of the LLL algorithm, and they presented a new numerical implementation that should be more robust than the original LLL scheme. In this paper, we compare the numerical properties of the two different LLL implementations.",

keywords = "Gauss transformation, LLL algorithm, Numerical overflow and underflow, Plane reflection, QR decomposition, Reduced basis, Unimodular transformation",

author = "LUK, {Franklin T} and Sanzheng Qiao",

year = "2007",

doi = "10.1117/12.740194",

language = "English",

isbn = "9780819468451",

series = "Proceedings of SPIE - The International Society for Optical Engineering",

booktitle = "Advanced Signal Processing Algorithms, Architectures, and Implementations XVII",

}

LUK, FT & Qiao, S 2007, Numerical properties of the LLL algorithm. in Advanced Signal Processing Algorithms, Architectures, and Implementations XVII., 669703, Proceedings of SPIE - The International Society for Optical Engineering, vol. 6697, Advanced Signal Processing Algorithms, Architectures, and Implementations XVII, San Diego, CA, United States, 26/08/07. https://doi.org/10.1117/12.740194

TY - GEN

T1 - Numerical properties of the LLL algorithm

AU - LUK, Franklin T

AU - Qiao, Sanzheng

PY - 2007

Y1 - 2007

N2 - The LLL algorithm is widely used to solve the integer least squares problems that arise in many engieering applications. As most practitioners did not understand how the LLL algorithm works, they avoided the issue by referring to the method as an integer Gram Schmidt approach (without explaining what they mean by this term). Luk and Tracy1 were first to describe the behavior of the LLL algorithm, and they presented a new numerical implementation that should be more robust than the original LLL scheme. In this paper, we compare the numerical properties of the two different LLL implementations.

AB - The LLL algorithm is widely used to solve the integer least squares problems that arise in many engieering applications. As most practitioners did not understand how the LLL algorithm works, they avoided the issue by referring to the method as an integer Gram Schmidt approach (without explaining what they mean by this term). Luk and Tracy1 were first to describe the behavior of the LLL algorithm, and they presented a new numerical implementation that should be more robust than the original LLL scheme. In this paper, we compare the numerical properties of the two different LLL implementations.

KW - Gauss transformation

KW - LLL algorithm

KW - Numerical overflow and underflow

KW - Plane reflection

KW - QR decomposition

KW - Reduced basis

KW - Unimodular transformation

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

U2 - 10.1117/12.740194

DO - 10.1117/12.740194

M3 - Conference contribution

AN - SCOPUS:42149083364

SN - 9780819468451

T3 - Proceedings of SPIE - The International Society for Optical Engineering

BT - Advanced Signal Processing Algorithms, Architectures, and Implementations XVII

T2 - Advanced Signal Processing Algorithms, Architectures, and Implementations XVII

Y2 - 26 August 2007 through 27 August 2007

ER -

Numerical properties of the LLL algorithm

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this