An Algorithm to Compute the Nearest Point in the Lattice A_{n}^*

DOI10.1109/TIT.2008.928280zbMATH Open1322.94081arXiv0801.1364MaRDI QIDQ3604841FDOQ3604841

Barry Quinn, I. Vaughan L. Clarkson, Robby G. McKilliam

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: The lattice $A_n^{*}$ is an important lattice because of its covering properties in low dimensions. Clarkson cite{Clarkson1999:Anstar} described an algorithm to compute the nearest lattice point in $A_n^{*}$ that requires $O(nlogn)$ arithmetic operations. In this paper, we describe a new algorithm. While the complexity is still $O(nlogn)$, it is significantly simpler to describe and verify. In practice, we find that the new algorithm also runs faster.

Full work available at URL: https://arxiv.org/abs/0801.1364

Recommendations

• scientific article; zbMATH DE number 1504656
• Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
• Closest point search in lattices
• scientific article; zbMATH DE number 3908520
• Finding a closest point in a lattice of Voronoi's first kind

Mathematics Subject Classification ID

Source coding (94A29) Combinatorial aspects of matroids and geometric lattices (05B35) Lattices and convex bodies (number-theoretic aspects) (11H06) Channel models (including quantum) in information and communication theory (94A40)

Cited In (5)

• Title not available (Why is that?)
• Nearest lattice point algorithms on semi \(k\)-reduced basis
• An optimal algorithm for global optimization and adaptive covering
• The closest vector problem in tensored root lattices of type A and in their duals
• A fast algorithm for determining the distances of the points of a given set in an integral lattice from its complement

This page was built for publication: An Algorithm to Compute the Nearest Point in the Lattice $A_{n}^*$

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