BTP-I (ME-494)�OPTIMAL SPHERE PACKING IN HIGHER DIMENSIONS

Aditya Gupta

THE PROBLEM

• The Sphere Packing problem poses a seemingly understandable question – Given an arrangement of equal, non-overlapping spheres in R^N , find the densest packing of spheres

​

PRACTICAL USE-CASES

• NOISE IN COMMUNICATION CHANNEL -
• Send signal s in Rⁿ; receive r on other end. Noise means generally r is not equal to s.
• The channel has some noise level ε, and r is almost always within distance ε of s. For this, we choose a sphere of radius ε about each sent signal, showing how it could be received.
• If s1 and s2 get too close, received signals could get confused. However, we can keep all signals 2ε apart, do the spheres do not overlap
• Hence, we want the densest non-overlapping packing in n-dimensions !

PRACTICAL USE-CASES

• CRYPTOSYSTEM-
• Public key: high dimensional lattice
• Private key: secret nearly orthogonal basis, that makes it easy to find the nearest lattice point to any given point
• Encode messages as lattice points.
• To encrypt, add a small random perturbation. Can decrypt using the private key, but not without it

WHAT WE KNOW AS OF TODAY ?

• The results for lower dimensions (i.e 2 & 3) were proved to be the most optimal possible. However, higher dimensions are a mystery.
• The best packing structure for lower dimensions are mostly lattice packings for the following dimensions –
• n ≤ 4: Korkin and Zolotarev 1873
• n = 5: Korkin and Zolotarev 1877
• n ≤ 8: Blichfeldt 1935
• n = 24: Cohn and Kumar 2003

​

​

WHAT WE KNOW AS OF TODAY ?

• Established Lower & Upper Bounds –
• Simplistic Case – Lower Bound (2^-n)

​

​

No point in Rⁿ can be 2r units away from all sphere centers. I.e., radius 2r spheres cover space completely

Other Bounds –

​

DIFFICULTIES

• Scalability issues in higher dimensions -
• The exponential growth of volume causes ridiculous amount of space in higher dimensions
• Naïve searching in such high volumes is incredibly slow, like finding a needle in a haystack
• The solutions obtained from one dimension cannot be scaled well to other dimensions.
• We will see later how peculiarities emerge in some dimensions owing to their inherit nature (d=13,24)
• Similar packing may lead to optimal packing in lower dimensions but sub-optimal results later (Dn)
• Intuitive thinking and periodicity fails to provide optimal packing in higher dimensions, non-lattice packings may dominate which makes the problem difficult to solve.

CURRENT RESULTS

• The current results for lower dimensions (<6) are base on checkerboard packing (Dn)
• CHECKERBOARD PACKING
• Dn = {(x1, . . . , xn) ∈ Z n | x1 + · · · + xn is even}
• D3, D4, D5 are best known packings in those dimensions, and probably best lattice packings.
• The holes in this packing are of the size sqrt(n/4) with a radius of sqrt(1/2). Hence, at n>5, the holes grow greater and other packings are able to get better density.
• At n=8, these holes can accommodate another set of spheres, leading to the symmetric E8 Packing
• For n=24, we use Leech Packing, which is a complex packing, similar in spirit to E8

​

UNDERLYING COMMANLITY AMONG ALL METHODS

• As we expect symmetry to intuitively give us optimal solutions, we start-off using lattice packing (periodic)
• Lattice: integer span of n linearly independent vectors. I.e., for basis v1, . . . , vn, center spheres at � {a1v1 + a2v2 + · · · + anvn | a1, . . . , an ∈ Z}

SOLUTIONS EXPLORED

• I read papers exploring the densest packings through different approaches. The idea was to get an underlying idea about the effectiveness of algorithms in terms of time taken, success rate etc.
• Apart from that, the aim was to explore the mathematical formulations amongst different methods and to also find out the optimal packings observed across various dimensions and their differences.
• Both numerical and analytical solutions, some of them are –
• Torquato-Jio Algorithm
• Metrapolis Algorithm – implementation using simulated annealing
• PDC method – numerical method

​

*methods are explained later

LINEAR PROGRAMMING ALGORITHM TO GENERATE DENSEST LATTICE SPHERE PACKING

• Uses the Torquato-Jiao Algorithm (TJ) – capable upto 19 dimensions

Finding the densest sphere packing can be posed as an optimization problem with a large number of nonlinear constraints, which can be solved by solving a series of linear approximations of the original problem

Implementation is based on lattice packing, and we choose a fundamental cell, with the aim of maximizing its density.

The advantage of this algorithm is the simplicity in formulation and the time-efficiency, where the results are orders of magnitude better than previous algorithms

FORMULATION – TJ ALGORITHM

• A d- dimensional lattice is composed of all vectors that are integer linear combinations of a set of d basis vectors m1,...,md :
• P = n₁m₁ +··· n_dm_d

Now, we can write the lattice packing density φ as the ratio of the volume occupied by spheres of diameter D to the volume of the fundamental cell:

The aim is to maximize density by minimizing the determinant of the generating matrix

We randomly initialize the values in a generating matrix, and keep tweaking it until the convergence criteria is not satisfied. The constraint is for the size of the fundamental cell to be greater than the size of the sphere

The convergence criterion is achieved at e<10^-12

Initially, we choose a size of the fundamental cell > D�This value should be chosen meticulously for optimal results as both reducing this value or increasing it beyond a range affects the time efficiency.

RESULTS – TJ ALGORITHM

CONCLUSION – TJ ALGORITHM

• The TJ algorithm is found to be orders of magnitude faster than the previous state-of-the art lattice packing methods
• As the dimensionality increases, the densities tend to become concentrated around a specific value instead of being spread over a range of possible densities
• This concentration tendency is caused by the rapid increase in the number of such low-density inherent structures for large d, which eventually overwhelms the algorithmic bias toward high-density lattice

SOLUTIONS EXPLORED

• I read papers exploring the densest packings through different approaches. The idea was to get an underlying idea about the effectiveness of algorithms in terms of time taken, success rate etc.
• Apart from that, the aim was to explore the mathematical formulations amongst different methods and to also find out the optimal packings observed across various dimensions and their differences.
• Both numerical and analytical solutions, some of them are –
• Torquato-Jio Algorithm
• Metrapolis Algorithm – implementation using simulated annealing
• PDC method – numerical method

​

*methods are explained later

STATISTICAL MECHANICS OF THE LATTICE SPHERE PACKING PROBLEM

• Uses Monte-Carlo method for lattice sphere packing in dimensions 9 through 20
• Voronoi – Existence of finite perfect lattices – can enumerate all of them to get values, but becomes computationally infeasible after 8 dimensions

​

​

Reported using Monte-Carlo (MC) method, which is different from the paper before, however, similar results are obtained for a lot of dimensions

30% success rate is observed in each dimension <20 which falls drastically later, suggesting various possible scenarios for densest packings in higher dimensions

The presented MC method introduces an isobaric ensemble on the space of admissible lattices and utilizes a Metropolis algorithm to sample this ensemble. The Monte Carlo simulations include a simulated quasistatic compression, starting from a simple hypercubic lattice and gradually increasing the pressure.

FORMULATION

• A lattice can be specified by its generating matrix: the set of all sphere centers is given by M^T Z^d = {M^T n : n ∈ Z^d }, where M is a d × d matrix and its rows are generating vectors (primitive vectors) of the lattice

A lattice is a packing of radius-1/2 spheres (that is, its spheres do not overlap) if ||M^T n||² >1 for all n ∈ Z^d \ {0}. If this is the case, we say the lattice is admissible.

Any lattice, generated by M, can be rotated so that its generating matrix MU, where U is a rotation matrix, becomes lower-triangular

Admissible

Inadmissible

FORMULATION

• We then apply a tweaked version of the Metropolis algorithm, wherein a random element of the lower-triangular generating matrix is randomly changed by a small amount; the step is rejected or accepted depending on the type of lattice generated

​

We start the system in a simple hypercubic lattice Z_d and equilibrate at a constant pressure. We then start to increase the pressure by a constant factor after each proposed move. We vary the typical move size inversely with the pressure: e = e₀/p

A crucial step in this MC algorithm is checking whether a lattice is admissible. This is known to be an NP-complete problem, and in fact it takes up most of the computational time.

RESULTS

• The present method is much less efficient than the SLP (1^st method) in all lower dimensions. For the highest dimensions, d = 17,18, and 19, respectively, this average time is 3 × 10⁵ s, 8 × 10⁴ s, and 2 × 10⁶ s with the SLP method, compared to 2 × 105s, 3 × 105s, and 8 × 105s with the present method.

CONCLUSION

• The drop of densities with dimensions >20 via almost all methods raise the possibility of the optimal packing to be non-periodic non-lattice
• The current method might be useful for time efficient calculations in higher dimensions
• Convergence to the optimal packing is obtained for most simulations, but the path leading to it might be different

SOLUTIONS EXPLORED

• I read papers exploring the densest packings through different approaches. The idea was to get an underlying idea about the effectiveness of algorithms in terms of time taken, success rate etc.
• Apart from that, the aim was to explore the mathematical formulations amongst different methods and to also find out the optimal packings observed across various dimensions and their differences.
• Both numerical and analytical solutions, some of them are –
• Torquato-Jio Algorithm
• Metrapolis Algorithm – implementation using simulated annealing
• PDC method – numerical method

​

*methods are explained later

METHOD FOR DENSE PACKING DISCOVERY

• Uses Divide and Concur method to develop a general search method for the solution of periodic constraint problems, and we apply it to the discovery of dense periodic packings.

​

​

Analytic methods, successful for spheres, involve constructions based on groups, codes, and laminated lattices. However, for other shapes, computational investigations are necessary. The challenges include the difficulty of finding the densest packings, especially in high-dimensional spaces.

The proposed method is known to explore configurations that might have been overlooked by previous analytical investigations

The proposed solution to overcome challenges in numerical searches is the PDC method. This method combines the dynamics of the difference map (DM), a constraint-satisfaction iterative search algorithm, and the divide and concur constraint framework. The PDC method is designed to avoid getting stuck in local optima, particularly in highly nonconvex problems.

FORMULATION

• 2 constraints are required to be fulfilled primarily

​

Divide Constraint :

The defining constraint of packing problems is the constraint that no particles in the packing overlap, which we call the exclusion constraint.

​

FORMULATION

• 2 constraints are required to be fulfilled primarily

​

Concur Constraint :

The divide constraint is responsible for bifurcating spheres into pairs, the concur constraint enabes clubbing together, whilst maintaining the confinement constraint

​

The formulation is therefore, a 2-step process which ensures each of the constraints is satisfied. When done periodically over a space, it is called PDC algorithm

DIFFERENCE MAP�

Given a problem formulated as the task of finding a configuration, simultaneously satisfying the constraints, we wish to use the availability of efficient methods for computing the projections C and D to the constraints in order to set up an iterated map to search through the configuration space for a solution.

The given difference map formulation enables the algorithm to skip the local optima points and enable global search

1. Initialize the iterate x to a random configuration.
2. Compute the two estimates of the solution x_c and x_d
3. Compute the error ←x_c−x_d. If it is below a predefined threshold, the search terminates
4. Advance the iterate x←x+x_d −x_c . Start the next iteration at step 2.

RESULTS

• To implement the methods on lattices, the confinement constraint is replaced by density constraint -

CONCLUSION

• Unlike several other stochastic methods, the PDC algorithm uses deterministic steps for evaluating the densest packing.
• Introduction of the difference map has been observed to be important in overcoming dynamical stagnation.
• The method performs at par or rather better than the analytical methods published before

FUTURE WORK

• I have been able to understand the different techniques used to solve the sphere packing problem, both analytical and numerical. However, the mathematical rigor required to understand the algorithms will take some time.
• The paper implementing PDC algorithm also talked abut convex optimizations and having worked with semi-infinite optimization using a novel MSA algorithm, I would want to explore on that front.
• Another front where work needs to be done is using Semi-Definite approach, which will be looked at in the future
• There is a lot of impetus given on convex polygon packing as well, its structure is similar to the sphere packing problem, but the geometry difference forces some changes. I would like to continue work there.

REFERENCES

• The following slides and research articles were referred to –
• Yoav Kallus, Veit Elser, and Simon Gravel, Method for dense packing discovery, Phys. Rev. E 82, 056707 (2010)
• Etienne Marcotte and Salvatore Torquato, ´ Efficient linear programming algorithm to generate the densest lattice sphere packings, Phys. Rev. E 87, 063303 (2013)
• Yoav Kallus, Statistical mechanics of the lattice sphere packing problem, Phys. Rev. E 87, 063307 (2013)
• http://www.matroidunion.org/stefan/talks/20100604.pdf
• https://www.ime.usp.br/~spschool2016/wp-content/uploads/2016/07/Oliveira.pdf
• Sphere packing (mit.edu)

​

THANK YOU !