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.

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.