Tropical geometry is an emerging field with strong connections in a wide array of areas both inside and outside mathematics. Efficient algorithms in tropical geometry take on a particular importance for developing these applications to other fields and for providing access to non-experts. The purpose of this dissertation is to provide novel and effective algorithms for the computation of various tropical objects of interest in pure mathematics and in phylogenetic data analysis.
We begin in the first chapter by describing some basic notions in tropical geometry which arise repeatedly throughout this thesis. We introduce tropical hypersurfaces, varieties, and prevarieties. We then discuss two classes of objects which are tropically convex, tropical linear spaces and tropical polytopes, and the ways in which they serve as tropical analogues to their classical equivalents. We also detail the connection between tropical geometry and the space of phylogenetic trees.
In the second chapter we discuss the computation of implicit tropicalizations of a very affine curve. We reduce the problem to the calculation of a basis for the group of units in the coordinate ring of the variety. We describe practical algorithms for computing such a basis for rational normal curves and elliptic curves. Our approach is rooted in divisor theory, based on interpolation in the case of rational curves and on methods from algebraic number theory in the case of elliptic curves.
In the third chapter we study the problem of computing the tropicalization of zero-dimensional varieties, which is a fundamental component of some algorithms for computing general tropical varieties. Our approach is via projections of the variety onto well-chosen lines, which are used to reconstruct the original variety. Our main algebraic tools for doing this are fast monomial transforms of triangular sets. Given a Groebner basis, we show that our algorithms require only a polynomial number of arithmetic operations, and for ideals in shape position we demonstrate that the algorithm performs well in practice against alternative approaches.
In the fourth chapter we describe the first time-bounded complexity algorithms for realizing the min-convex hull of a finite collection of points in the affine building of $SL_d$ as a tropical polytope lying inside a tropical linear space. These min-convex hulls describe the relations among a finite collection of invertible matrices over a field with valuation. As a consequence, we obtain a bound on the dimension of the tropical projective space needed to realize the min-convex hull as a tropical polytope.
In the fifth chapter we describe two tropical analogues of principal component analysis for the dimensionality reduction of ultrametric tree datasets. In one approach, we study the Stiefel tropical linear space of fixed dimension closest to the data points in the tropical projective torus; in the other, we consider the tropical polytope with a fixed number of vertices closest to the data points. We relate tropical best-fit hyperplanes to the tropical volume and prove that the polytropal decomposition of a tropical polytope spanned by ultrametrics refines the decomposition of the polytope into different tree topologies. We also give heuristic algorithms for both approaches and apply them to phylogenetics, testing the methods on simulated phylogenetic data and on an empirical dataset of Apicomplexa genomes.
