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

DOI10.1109/TIT.2008.928280MaRDI QIDQ3604841zbMATH OpenFDO

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

Publication date 24 February 2009

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

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

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)

Abstract: The lattice $A_n^{\ast }$ 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^{\ast }$ 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.

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

Cited in

(5)

• scientific article; zbMATH DE number 1504656 (Why is no real title available?)
• 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)