Toric Varieties and Numerical Algorithms for Solving Polynomial Systems
Abstract
This work utilizes toric varieties for solving systems of equations. In particular, it includes two numerical homotopy continuation algorithms for numerically solving systems of equations. The first algorithm, the Cox homotopy, solves a system of equations on a compact toric variety. The Cox homotopy tracks points in the total coordinate space of the toric variety and can be viewed as a homogeneous version of the polyhedral homotopy of Huber and Sturmfels. The second algorithm, the Khovanskii homotopy, solves a system of equations on a variety in the presence of a finite Khovanskii basis. This homotopy takes advantage of Anderson’s flat degeneration to a toric variety. The Khovanskii homotopy utilizes the Newton-Okounkov body of the system, whose normalized volume gives a bound on the number of solutions to the system. Both homotopy algorithms provide the computational advantage of tracking paths in a compact space while also minimizing the total number of paths tracked. The Khovanskii homotopy is optimal with respect to the number of paths tracked, and the Cox homotopy is optimal when the system is Bernstein-general.
Subject
Numerical algebraic geometrypolynomial systems
homotopy continuation
Cox homotopy
Khovanskii homotopy
Khovanskii bases
Newton-Okounkov bodies
nonlinear algebra
Citation
Walker, Elise Anne (2022). Toric Varieties and Numerical Algorithms for Solving Polynomial Systems. Doctoral dissertation, Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /197312.