Skip to main content

Efficient linear programming algorithm to generate the densest lattice sphere packings

Author(s): Marcotte, Étienne; Torquato, Salvatore

To refer to this page use:
Abstract: Finding the densest sphere packing in d-dimensional Euclidean space Rd is an outstanding fundamental problem with relevance in many fields, including the ground states of molecular systems, colloidal crystal structures, coding theory, discrete geometry, number theory, and biological systems. Numerically generating the densest sphere packings becomes very challenging in high dimensions due to an exponentially increasing number of possible sphere contacts and sphere configurations, even for the restricted problem of finding the densest lattice sphere packings. In this paper we apply the Torquato-Jiao packing algorithm, which is a method based on solving a sequence of linear programs, to robustly reproduce the densest known lattice sphere packings for dimensions 2 through 19. We show that the TJ algorithm is appreciably more efficient at solving these problems than previously published methods. Indeed, in some dimensions, the former procedure can be as much as three orders of magnitude faster at finding the optimal solutions than earlier ones. We also study the suboptimal local density-maxima solutions (inherent structures or “extreme” lattices) to gain insight about the nature of the topography of the “density” landscape.
Publication Date: Jun-2013
Electronic Publication Date: 7-Jun-2013
Citation: Marcotte, Étienne, Torquato, Salvatore. (2013). Efficient linear programming algorithm to generate the densest lattice sphere packings. Physical Review E, 87 (6), 10.1103/PhysRevE.87.063303
DOI: doi:10.1103/PhysRevE.87.063303
ISSN: 1539-3755
EISSN: 1550-2376
Pages: 063303-1 - 063303-9
Type of Material: Journal Article
Journal/Proceeding Title: Physical Review E
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.