Computational Approaches to Lattice Packing and Covering Problems |
| |
Authors: | Achill Schurmann Frank Vallentin |
| |
Institution: | (1) Department of Mathematics, University of Magdeburg, 39106 Magdeburg, Germany;(2) Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem 91904, Israel |
| |
Abstract: | We describe algorithms which address two classical problems in lattice
geometry: the lattice covering and the simultaneous lattice
packing-covering problem. Theoretically our algorithms solve the two
problems in any fixed dimension d in the sense that they approximate
optimal covering lattices and optimal packing-covering lattices within
any desired accuracy. Both algorithms involve semidefinite
programming and are based on Voronoi's reduction theory for positive
definite quadratic forms, which describes all possible Delone
triangulations of ℤd. In practice, our implementations reproduce known results in dimensions d ≤ 5 and in particular solve the two problems in
these dimensions. For d = 6 our computations produce new best known covering as well as packing-covering lattices, which are
closely related to the lattice E*6. For d = 7,8 our approach leads to new best known covering lattices. Although we use numerical methods, we made some effort
to transform numerical evidences into rigorous proofs. We provide rigorous error bounds and prove that some of the new lattices
are locally optimal. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|