Revision #1 Authors: Frank Vallentin, Boris Hemkemeier

Accepted on: 11th September 2006 00:00

Downloads: 973

Keywords:

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 Authors: Boris Hemkemeier, Frank Vallentin

Publication: 31st August 1998 16:52

Downloads: 1197

Keywords:

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.