Abstract:
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.
Key words and phrases: Lattices, LLL algorithm, Large generating systems, Successive Minima
1991 Mathematics Subject Classification: Primary 11H55; Secondary 11Y40,11H06.
Available as
To appear in: submitted
Contact: Boris.Hemkemeier@Mathematik.Uni-Dortmund.DE