Computing zero-dimensional tropical varieties via projections

Görlach, Paul; Ren, Yue; Zhang, Leon

Abstract

We present an algorithm for computing zero-dimensional tropical varieties using projections. Our main tools are fast monomial transforms of triangular sets. Given a Gröbner basis, we prove that our algorithm requires only a polynomial number of arithmetic operations, and, for ideals in shape position, we show that its timings compare well against univariate factorization and backsubstitution. We conclude that the complexity of computing positive-dimensional tropical varieties via a traversal of the Gröbner complex is dominated by the complexity of the Gröbner walk.

Citation

Görlach, P., Ren, Y., & Zhang, L. (2022). Computing zero-dimensional tropical varieties via projections. Computational Complexity, 31(1), Article 5. https://doi.org/10.1007/s00037-022-00222-9

• Journal Article Type: Article
• Online Publication Date: May 20, 2022
• Publication Date: 2022-06
• Deposit Date: Jul 14, 2022
• Publicly Available Date: Jul 14, 2022
• Journal: computational complexity
• Print ISSN: 1016-3328
• Electronic ISSN: 1420-8954
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 31
• Issue: 1
• Article Number: 5
• DOI: https://doi.org/10.1007/s00037-022-00222-9
• Public URL: https://durham-repository.worktribe.com/output/1200379