2025/06/24 by Guoce Xin, Tao, Sihao, Zihao Zhang +2
Computer Science · Medicine · #68Q25 #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Medical Imaging Techniques and Applications #Primary 52B20 #Secondary 05A15 #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2506.19322
openalex publication_date 2025/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \textupPDBarv. 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.