A combinatorial simplicial cone decomposition
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929672011382784 |
|---|---|
| author | Xin, Guoce Xu, Xinyu Zhang, Zihao |
| author_facet | Xin, Guoce Xu, Xinyu Zhang, Zihao |
| contents | This paper introduces an algebraic combinatorial approach to simplicial cone decompositions, a key step in solving inhomogeneous linear Diophantine systems and counting lattice points in polytopes. We use constant term manipulation on the system \( Aα= \mathbf{b} \), where \( A \) is an \( r \times n \) integral matrix and \( \mathbf{b} \) is an integral vector. We establish a relationship between special constant terms and shifted simplicial cones. This leads to the \texttt{SimpCone[S]} algorithm, which efficiently decomposes polyhedra into simplicial cones. Unlike traditional geometric triangulation methods, this algorithm is versatile for many choices of the strategy \( \texttt{S} \) and can also be applied to parametric polyhedra. The algorithm is useful for efficient volume computation of polytopes and can be applied to address various new research projects. Additionally, we apply our framework to unimodular cone decompositions. This extends the effectiveness of the newly developed \texttt{DecDenu} algorithm from denumerant cones to general simplicial cones. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06691 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A combinatorial simplicial cone decomposition Xin, Guoce Xu, Xinyu Zhang, Zihao Combinatorics This paper introduces an algebraic combinatorial approach to simplicial cone decompositions, a key step in solving inhomogeneous linear Diophantine systems and counting lattice points in polytopes. We use constant term manipulation on the system \( Aα= \mathbf{b} \), where \( A \) is an \( r \times n \) integral matrix and \( \mathbf{b} \) is an integral vector. We establish a relationship between special constant terms and shifted simplicial cones. This leads to the \texttt{SimpCone[S]} algorithm, which efficiently decomposes polyhedra into simplicial cones. Unlike traditional geometric triangulation methods, this algorithm is versatile for many choices of the strategy \( \texttt{S} \) and can also be applied to parametric polyhedra. The algorithm is useful for efficient volume computation of polytopes and can be applied to address various new research projects. Additionally, we apply our framework to unimodular cone decompositions. This extends the effectiveness of the newly developed \texttt{DecDenu} algorithm from denumerant cones to general simplicial cones. |
| title | A combinatorial simplicial cone decomposition |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.06691 |