Unimodular equivalence of integral simplices
Mathematics of Computation · 29.05.2026
DOI: 10.1090/mcom/4214 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Computation, online erschienen am 29.05.2026. Verfasst von Feihu Liu und 2 weiteren Autor:innen. Die Arbeit nennt 22 Literaturangaben.
Abstract (Originalsprache)
Testing the unimodular equivalence of two full-dimensional integral simplices can be reduced to testing unimodular permutation (UP) equivalence of two nonsingular matrices. We conduct a systematic study of UP-equivalence, which leads to the first average-case quasi-polynomial time algorithm, called HEM , for deciding the unimodular equivalence of d d -dimensional integral simplices, as well as achieving a polynomial-time complexity with a failure probability less than 2.5 × 10 − 7 2.5 \times 10^{-7} . A key ingredient is the introduction of the permuted Hermite normal form and its associated pattern group , which streamlines the UP-equivalence test by comparing canonical forms derived from induced coset representatives. We also present an acceleration strategy based on Smith normal forms. As a theoretical by-product, we prove that two full-dimensional integral simplices are unimodularly equivalent if and only if their n n -dimensional pyramids are unimodularly equivalent. This resolves an open question posed by Abney-McPeek et al.
Zitieren
APA
Liu, F., Tao, S., & Xin, G. (2026). Unimodular equivalence of integral simplices. Mathematics of Computation. https://doi.org/10.1090/mcom/4214
Vancouver
Liu F, Tao S, Xin G. Unimodular equivalence of integral simplices. Mathematics of Computation. 2026. doi:10.1090/mcom/4214
BibTeX
@article{Liu2026,
author = {Liu, Feihu and Tao, Sihao and Xin, Guoce},
title = {Unimodular equivalence of integral simplices},
journal = {Mathematics of Computation},
year = {2026},
doi = {10.1090/mcom/4214}
}
EUVIMED