This article concerns the computational problem of counting the lattice points inside convex polytopes, when each point must be counted with a weight associated to it. We describe an efficient algorithm for computing the highest degree coefficients of the weighted Ehrhart quasi-polynomial for a rational simple polytope in varying dimension, when the weights of the lattice points are given by a polynomial function h. Our technique is based on a refinement of an algorithm of A. Barvinok in the unweighted case (i.e., h≡1). In contrast to Barvinok’s method, our method is local, obtains an approximation on the level of generating functions, handles the general weighted case, and provides the coefficients in closed form as step polynomials of the dilation. To demonstrate the practicality of our approach, we report on computational experiments which show that even our simple implementation can compete with state-of-the-art software

Baldoni, M., Berline, N., De Loera, J., Köppe, M., Vergne, M. (2012). Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra. FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 12, 435-469 [10.1007/s10208-011-9106-4].

Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra.

BALDONI, MARIA;
2012-01-01

Abstract

This article concerns the computational problem of counting the lattice points inside convex polytopes, when each point must be counted with a weight associated to it. We describe an efficient algorithm for computing the highest degree coefficients of the weighted Ehrhart quasi-polynomial for a rational simple polytope in varying dimension, when the weights of the lattice points are given by a polynomial function h. Our technique is based on a refinement of an algorithm of A. Barvinok in the unweighted case (i.e., h≡1). In contrast to Barvinok’s method, our method is local, obtains an approximation on the level of generating functions, handles the general weighted case, and provides the coefficients in closed form as step polynomials of the dilation. To demonstrate the practicality of our approach, we report on computational experiments which show that even our simple implementation can compete with state-of-the-art software
2012
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore MAT/03 - GEOMETRIA
English
Con Impact Factor ISI
Baldoni, M., Berline, N., De Loera, J., Köppe, M., Vergne, M. (2012). Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra. FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 12, 435-469 [10.1007/s10208-011-9106-4].
Baldoni, M; Berline, N; De Loera, J; Köppe, M; Vergne, M
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
Baldoni_et_al2012.pdf

solo utenti autorizzati

Descrizione: Articolo principale
Licenza: Copyright dell'editore
Dimensione 1.1 MB
Formato Adobe PDF
1.1 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/96831
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 13
social impact