Algebraic Volume for Polytope Arise from Ehrhart Theory
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916082748489728 |
|---|---|
| author | Xin, Guoce Xu, Xinyu Zhang, Yingrui Zhang, Zihao |
| author_facet | Xin, Guoce Xu, Xinyu Zhang, Yingrui Zhang, Zihao |
| contents | Volume computation for $d$-polytopes $\mathcal{P}$ is fundamental in mathematics. There are known volume computation algorithms, mostly based on triangulation or signed-decomposition of $\mathcal{P}$. We consider $ \mathrm{cone}(\mathcal{P})$ as a lift of $\mathcal{P}$ in view of Ehrhart theory. By using technique from algebraic combinatorics, we obtain a volume algorithm using only signed simplicial cone decompositions of $ \mathrm{cone}(¶)$. Each cone is associated with a simple algebraic volume formula. Summing them gives the volume of the polytope. Our volume formula applies to various kind of cases. In particular, we use it to explain the traditional triangulation method and Lawrence's signed decomposition method. Moreover, we give a completely new primal-dual method for volume computation. This solves the traditional problem in this area: All existing methods are hopelessly impractical for either the class of simple polytopes or the class of simplicial polytopes. Our method has a good performance in computer experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_12080 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Algebraic Volume for Polytope Arise from Ehrhart Theory Xin, Guoce Xu, Xinyu Zhang, Yingrui Zhang, Zihao Combinatorics 05A15, 52B05, 68U05, 52B11 Volume computation for $d$-polytopes $\mathcal{P}$ is fundamental in mathematics. There are known volume computation algorithms, mostly based on triangulation or signed-decomposition of $\mathcal{P}$. We consider $ \mathrm{cone}(\mathcal{P})$ as a lift of $\mathcal{P}$ in view of Ehrhart theory. By using technique from algebraic combinatorics, we obtain a volume algorithm using only signed simplicial cone decompositions of $ \mathrm{cone}(¶)$. Each cone is associated with a simple algebraic volume formula. Summing them gives the volume of the polytope. Our volume formula applies to various kind of cases. In particular, we use it to explain the traditional triangulation method and Lawrence's signed decomposition method. Moreover, we give a completely new primal-dual method for volume computation. This solves the traditional problem in this area: All existing methods are hopelessly impractical for either the class of simple polytopes or the class of simplicial polytopes. Our method has a good performance in computer experiments. |
| title | Algebraic Volume for Polytope Arise from Ehrhart Theory |
| topic | Combinatorics 05A15, 52B05, 68U05, 52B11 |
| url | https://arxiv.org/abs/2306.12080 |