Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR98-052 | 11th September 2006 00:00

Incremental Algorithms for Lattice Problems


Revision #1
Authors: Frank Vallentin, Boris Hemkemeier
Accepted on: 11th September 2006 00:00
Downloads: 952


In this short note we give incremental algorithms for the following lattice problems: finding a basis of a lattice, computing the successive minima, and determining the orthogonal decomposition. We prove an upper bound for the number of update steps for every insertion order. For the determination of the orthogonal decomposition we efficiently implement an argument due to Kneser.

This note is a concise version of report TR98-052 where we in particular emphasize the incremental algorithmic framework.


TR98-052 | 5th August 1998 00:00

On the decomposition of lattices

Authors: Boris Hemkemeier, Frank Vallentin
Publication: 31st August 1998 16:52
Downloads: 1088


A lattice in euclidean space which is an orthogonal sum of
nontrivial sublattices is called decomposable. We present an algorithm
to construct a lattice's decomposition into indecomposable sublattices.
Similar methods are used to prove a covering theorem for generating
systems of lattices and to speed up variations of the LLL algorithm
for the computation of lattice bases from large generating systems. We
prove an upper bound for this which is asymptotically better than the
known bound for a standard algorithm (variation of the LLL algorithm
due to Buchmann, Pohst). Experimental results show that our algorithm
is faster than Pohst's MLLL algorithm in particular if the number of
generators is large.

ISSN 1433-8092 | Imprint