Incremental Algorithms for Lattice Problems

A lattice of integers is the collection of all linear combinations of a set of vectors for which all entries of the vectors are integers and all coefficients in the linear combinations are also integers. Lattice reduction refers to the problem of finding a set of vectors in a given lattice such that the collection of all integer linear combinations of this subset is still the entire original lattice and so that the Euclidean norms of the subset are reduced. The present paper ...

As a typical application, the Lenstra-Lenstra-Lovasz lattice basis reduction algorithm (LLL) is used to compute a reduced basis of the orthogonal lattice for a given integer matrix, via reducing a special kind of lattice bases. With such bases in input, we propose a new technique for bounding from above the number of iterations required by the LLL algorithm. The main technical ingredient is a variant of the classical LLL potential, which could prove useful to understand the b...

A method of embedding partially ordered sets into linear spaces is presented. The problem of finding all orthocomplementations in a finite lattice is reduced to a linear programming problem.

In this paper, we show that for each lattice basis, there exists an equivalent basis which we describe as ``strongly reduced''. We show that bases reduced in this manner exhibit rather ``short'' basis vectors, that is, the length of the $i$th basis vector of a strongly reduced basis is upper bounded by a polynomial factor in $i$ multiplied by the $i$th successive minima of the lattice. The polynomial factor seems to be smaller than other known factors in literature, such as H...

The main objective of this thesis is a classification project for integral lattices. Using Kneser's neighbour method we have developed the computer program tn to classify complete genera of integral lattices. Main results are detailed classifications of modular lattices in dimensions up to 14 with levels 3,5,7, and 11. We present a fast meta algorithm for the computation of a basis of a lattice which is given by a large generating system. A theoretical worst case boundary and...

In this article, we present a new algorithm for computing a generating set of a lattice ideal. This algorithm is based on a project-and-lift approach and is implemented in 4ti2. We also include a computational comparison of several existing implementations to compute such generating sets.

A lattice reduction is an algorithm that transforms the given basis of the lattice to another lattice basis such that problems like finding a shortest vector and closest vector become easier to solve. Some of the famous lattice reduction algorithms are LLL and BKZ reductions. We define a class of bases called \emph{obtuse bases} and show that any lattice basis can be transformed to an obtuse basis in $\mathcal{O}(n^4)$ time. A shortest vector s can be written as $v_1b_1+\cdot...

In this paper we present a novel project-and-lift approach to compute the set of minimal generators of the semigroup $(\Lambda\cap\R^n_+,+)$ for lattices $\Lambda\subseteq\Z^n$. This problem class includes the computation of Hilbert bases of cones $\{z:Az=0,z\in\R^n_+\}$ for integer matrices $A$. A similar approach can be used to compute only the extreme rays of such cones. Finally, some combinatorial applications and computational experience are presented.

The Euclidean algorithm is one of the oldest algorithms known to mankind. Given two integral numbers $a_1$ and $a_2$, it computes the greatest common divisor (gcd) of $a_1$ and $a_2$ in a very elegant way. From a lattice perspective, it computes a basis of the sum of two one-dimensional lattices $a_1 \mathbb{Z}$ and $a_2 \mathbb{Z}$ as $\gcd(a_1,a_2) \mathbb{Z} = a_1 \mathbb{Z} + a_2 \mathbb{Z}$. In this paper, we show that the classical Euclidean algorithm can be adapted in ...

A lattice is a partially-ordered set in which every pair of elements has a unique meet (greatest lower bound) and join (least upper bound). We present new data structures for lattices that are simple, efficient, and nearly optimal in terms of space complexity. Our first data structure can answer partial order queries in constant time and find the meet or join of two elements in $O(n^{3/4})$ time, where $n$ is the number of elements in the lattice. It occupies $O(n^{3/2}\log...