Closed-Form Decomposition for Simplicial Cones and PDBarv Algorithm for Lattice Point Counting
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911020375605248 |
|---|---|
| author | Tao, Sihao Xin, Guoce Zhang, Zihao |
| author_facet | Tao, Sihao Xin, Guoce Zhang, Zihao |
| contents | Counting lattice points within a rational polytope is a foundational problem with applications across mathematics and computer science. A key approach is Barvinok's algorithm, which decomposes the lattice point generating function of cones to that of unimodular cones. However, standard implementations face difficulties: the original primal method struggles with points on cone boundaries, while the alternative dual method can be slow for certain cone types.
This paper introduces two main contributions. First, We derive a closed-form expression for these generating functions using arbitrary lattice point decompositions, enabling more effective primal space decomposition. Second, by decomposing both the cone and its dual cone starting from the side with a smaller index, we develop a novel algorithm called \textup{PDBarv}. This hybrid approach integrates the primal and dual Barvinok algorithms with a novel acceleration strategy, achieving an average computational performance improvement of over 20\% in dimension 5 and even better in higher dimensions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19322 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Closed-Form Decomposition for Simplicial Cones and PDBarv Algorithm for Lattice Point Counting Tao, Sihao Xin, Guoce Zhang, Zihao Combinatorics Primary 52B20, Secondary 05A15, 68Q25 Counting lattice points within a rational polytope is a foundational problem with applications across mathematics and computer science. A key approach is Barvinok's algorithm, which decomposes the lattice point generating function of cones to that of unimodular cones. However, standard implementations face difficulties: the original primal method struggles with points on cone boundaries, while the alternative dual method can be slow for certain cone types. This paper introduces two main contributions. First, We derive a closed-form expression for these generating functions using arbitrary lattice point decompositions, enabling more effective primal space decomposition. Second, by decomposing both the cone and its dual cone starting from the side with a smaller index, we develop a novel algorithm called \textup{PDBarv}. This hybrid approach integrates the primal and dual Barvinok algorithms with a novel acceleration strategy, achieving an average computational performance improvement of over 20\% in dimension 5 and even better in higher dimensions. |
| title | Closed-Form Decomposition for Simplicial Cones and PDBarv Algorithm for Lattice Point Counting |
| topic | Combinatorics Primary 52B20, Secondary 05A15, 68Q25 |
| url | https://arxiv.org/abs/2506.19322 |