Tropical Homotopy Continuation

Abstract

Inspired by numerical homotopy methods we propose a combinatorial homotopy algorithm for finding all isolated solutions to a tropical polynomial systems of n tropical polynomials in n variables. In particular, a tropicalisation of the numerical "regeneration" technique leads to a new method for enumerating the mixed cells of a mixed subdivision. This tropical approach shares some ideas with the recent algorithm by Malajovich. However, our algorithm has several advantages. It is memoryless, parallelisable as a tree traversal, exact and relies on symbolic perturbations. Our computational experiments show that the method is competitive and especially fast on the Katsura class of examples.

References in corpus (1)

• Computing mixed volume and all mixed cells in quermassintegral time

Cited by in corpus (6)

• Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
• Computing mixed volume and all mixed cells in quermassintegral time
• Complexity of Sparse Polynomial Solving 2: Renormalization
• A Polyhedral Homotopy Algorithm For Real Zeros
• Beyond Polyhedral Homotopies
• The Nullstellensatz and Positivstellensatz for Sparse Tropical Polynomial Systems