Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Algorithm to Compute the Nearest Point in the Lattice $A_{n}^*$
382
0
0.0
(
0
)
Added by
Robert McKilliam
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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(nlog{n})$ arithmetic operations. In this paper, we describe a new algorithm. While the complexity is still $O(nlog{n})$, it is significantly simpler to describe and verify. In practice, we find that the new algorithm also runs faster.
rate research
Read More
We consider the closest lattice point problem in a distributed network setting and study the communication cost and the error probability for computing an approximate nearest lattice point, using the nearest-plane algorithm, due to Babai. Two distinct communication models, centralized and interactive, are considered. The importance of proper basis selection is addressed. Assuming a reduced basis for a two-dimensional lattice, we determine the approximation error of the nearest plane algorithm. The communication cost for determining the Babai point, or equivalently, for constructing the rectangular nearest-plane partition, is calculated in the interactive setting. For the centralized model, an algorithm is presented for reducing the communication cost of the nearest plane algorithm in an arbitrary number of dimensions.
The Coxeter lattices, which we denote $A_{n/m}$, are a family of lattices containing many of the important lattices in low dimensions. This includes $A_n$, $E_7$, $E_8$ and their duals $A_n^*$, $E_7^*$ and $E_8^*$. We consider the problem of finding a nearest point in a Coxeter lattice. We describe two new algorithms, one with worst case arithmetic complexity $O(nlog{n})$ and the other with worst case complexity O(n) where $n$ is the dimension of the lattice. We show that for the particular lattices $A_n$ and $A_n^*$ the algorithms reduce to simple nearest point algorithms that already exist in the literature.
We consider the problem of finding the closest lattice point to a vector in n-dimensional Euclidean space when each component of the vector is available at a distinct node in a network. Our objectives are (i) minimize the communication cost and (ii) obtain the error probability. The approximate closest lattice point considered here is the one obtained using the nearest-plane (Babai) algorithm. Assuming a triangular special basis for the lattice, we develop communication-efficient protocols for computing the approximate lattice point and determine the communication cost for lattices of dimension n>1. Based on available parameterizations of reduced bases, we determine the error probability of the nearest plane algorithm for two dimensional lattices analytically, and present a computational error estimation algorithm in three dimensions. For dimensions 2 and 3, our results show that the error probability increases with the packing density of the lattice.
Compute-and-Forward is an emerging technique to deal with interference. It allows the receiver to decode a suitably chosen integer linear combination of the transmitted messages. The integer coefficients should be adapted to the channel fading state. Optimizing these coefficients is a Shortest Lattice Vector (SLV) problem. In general, the SLV problem is known to be prohibitively complex. In this paper, we show that the particular SLV instance resulting from the Compute-and-Forward problem can be solved in low polynomial complexity and give an explicit deterministic algorithm that is guaranteed to find the optimal solution.
The compute-and-forward (CoF) is a relaying protocol, which uses algebraic structured codes to harness the interference and remove the noise in wireless networks. We propose the use of phase precoders at the transmitters of a network, where relays apply CoF strategy. We define the {em phase precoded computation rate} and show that it is greater than the original computation rate of CoF protocol. We further give a new low-complexity method for finding network equations. We finally show that the proposed precoding scheme increases the degrees-of-freedom (DoF) of CoF protocol. This overcomes the limitations on the DoF of the CoF protocol, recently presented by Niesen and Whiting. Using tools from Diophantine approximation and algebraic geometry, we prove the existence of a phase precoder that approaches the maximum DoF when the number of transmitters tends to infinity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
