The computation of tropical varieties
From CRCG-Wiki
The computation of tropical varieties
Tropical hypersurfaces are tropical varieties defined by principal ideals. A finite generating set for an ideal is called a tropical basis if the intersection of the tropical hypersurfaces defined by the generators equals the tropical variety of the ideal. If one knows a tropical basis the tropical variety can be computed. However, for computational purposes, the characterization of a tropical variety in terms of initial ideals is helpful. This characterization which was given by David Speyer and Bernd Sturmfels (see here) allows the tropical variety to be seen as a subcomplex of the Gröbner fan of its defining ideal. The maximal cones in the Gröbner fan are indexed by the reduced Gröbner bases of the ideal while the tropical variety is a union of certain lower dimensional cones. The finiteness of the Gröbner fan implies the existence of a finite tropical basis. Stéphane Collart, Michael Kalkbrener and Daniel Mall gave as subroutine of their Gröbner walk a method to convert a Gröbner basis to that of an adjacent cone. Repeating this process one can enumerate all maximal cones of the Groebner fan and extract the desired subcomplex.
By a theorem of Robert Bieri and J. R. J. Groves the tropical variety of a prime ideal is a pure complex of the same dimension as the variety defined by the ideal. Moreover, it can be shown that this complex is connected in a way that allows for just the tropical variety part of the Gröbner fan to be traversed. An important ingredient in such a traversal is the computation of the mixed faces of a Minkowski sum. Interestingly this computation also shows up as a first step in the polyhedral homotopy method for numerically solving a polynomial system over the complex numbers. Indeed we may think of Bernstein's theorem for bounding the number of solutions to a polynomial system in terms of the mixed volume of the defining Newton polytopes to be a theorem in tropical geometry.
The above method for computing tropical varieties was described by Tristram Bogart, Anders Jensen, David Speyer, Bernd Sturmfels and Rekha Thomas (see here) and the algorithms have been implemented by Anders Jensen in the software Gfan. This software is useful for providing examples to people who work in tropical geometry.
In recent work Kerstin Hept and Thorsten Theobald used generic projections to show that any generating set for a prime ideal can be extended to a tropical basis by adding at most codimension plus one number of generators (see here). In other work by Theobald it is show that many decision problems concerning tropical varieties are NP-hard.
