ECCC-Report TR98-052https://eccc.weizmann.ac.il/report/1998/052Comments and Revisions published for TR98-052en-usMon, 11 Sep 2006 00:00:00 +0300
Revision 1
| Incremental Algorithms for Lattice Problems |
Frank Vallentin,
Boris Hemkemeier
https://eccc.weizmann.ac.il/report/1998/052#revision1In 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.
Mon, 11 Sep 2006 00:00:00 +0300https://eccc.weizmann.ac.il/report/1998/052#revision1
Paper TR98-052
| On the decomposition of lattices |
Boris Hemkemeier,
Frank Vallentin
https://eccc.weizmann.ac.il/report/1998/052A 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.
Mon, 31 Aug 1998 16:52:52 +0300https://eccc.weizmann.ac.il/report/1998/052