Lattices enumeration via linear programming
Abdellah Chkifa  1  
1 : Université Mohammed VI Polytechnique

Given a positive integer and a(1),...,a(mvectors in Rd{k1a(1) +···+kma(mk1,...,k∈ Z} ⊂ Ris the so-called lattice generated by the family of vectors, or by the matrix = (a(1) . . . |a(m∈ Rd×. In high dimensional integration, prescribed lattices are used for constructing reliable quadrature schemes. The quadrature points are the lattice points lying on the integration domain, typically the unit hypercube [01)or a shifted hypercube. It is crucial to be able to enumerate the lattice points in such domains inexpensively. Un- deniably, the lack of fast enumeration procedures hinders the applicability of lattice rules. Existing enumeration procedures exploit intrinsic properties of the lattice at hand, such as Z-periodicity, orthogonality, recurrences, etc, e.g. [1, 2, 3, 4]. We present a general-purpose lattice enumeration strategies based on linear programming, [5]. We demonstrate how to combine duality and parametric linear programming in order to accelerate these strategies, producing performances comparable to the enumeration strategies that are fine-tuned to special lat- tices. In addition, we discuss a variety of relaxation and reduction techniques that allow further acceleration of the introduced algorithms. Numerical experiments in high dimension are also presented.


Personnes connectées : 10 Vie privée
Chargement...