Computational approaches to lattice packing and covering problems (Q818684): Difference between revisions

Two classical problems in the geometry of numbers are computationally approached in this paper: the most economical lattice sphere packings and coverings of the Euclidean \(d\)-space. A historical presentation of the lattice covering problem is followed by a review of the known results and the history of the simultaneous lattice packing-covering problem, based on a rich and up-to-date bibliography. Finally, the reduction theory for positive definite quadratic forms by Voronoi is the main tool for deriving algorithms to solve these problems. Other basic tools come from the semidefinite programming and the determinant maximization, well known from the convex optimization theory. The duality theory together with the rational approximations are used for providing rigorous error bounds. Both problems have in common the necessity of minimizing a convex function on variables that satisfy some linear matrix inequalities. The algorithms, which are attained, theoretically solve the two problems under consideration. A detailed discussion on the efficiency of their implementation is based on examples, which both retrive known results and attain additional information on locally optimal solutions in dimensions \(d = 5, 6, 7\) and 8.