the Khovanskii Homotopy

joint work with Michael Burr and Frank Sottile

Abstract

We provide an efficient algorithm to compute all solutions to a system of equations using numerical methods.

Numerical homotopies provide a way to compute all solutions to a polynomial system of interest F by interpolating with known solutions to a similar system G. A homotopy is not efficient when it tracks excess paths. Generally the fewest number of paths to track is the normalized volume of the Newton-Okounkov body of the system. This can be a sharper bound than the mixed volume of the system.

When a system has a finite Khovanskii basis, we give a homotopy where the system G is a toric variety associated with the Newton-Okounkov body of F. This homotopy is optimal in the sense that it does not track excess paths in projective space. We give the Khovanskii homotopy, which is derived from an abstract toric degeneration of Anderson (2012).

Algorithm Implementation

We demonstrate our homotopy algorithms in Macaulay2 on various examples. Code for all of the examples in the paper can be found on my GitHub.

Publication

Preprint