application: tropical
This application concentrates on tropical hypersurfaces and tropical polytopes. It provides the functionality for the computation of basic properties. Visualization and various constructions are possible.
uses: fan, group, ideal, polytope, topaz
Objects
FIXME: Include typecheck?
Properties of Hypersurface
- COEFFICIENTS: common::Vector<Rational>
Coefficients of the (tropical) polynomial defining the hypersurface.
- DOME: polytope::Polytope<Rational>
The dome of a tropical polynomial \(F:\mathbb R^d\to\mathbb R\) (and the corresponding tropical hypersurface) is the set \[D(F)=\left\{(p,s)\in\mathbb R^{d+1}\mid p\in\mathbb R^d, s\in\mathbb R, s\leq F(p)\right\}.\] It is an unbounded convex polyhedron, c.f.
Michael Joswig, Essentials of Tropical Combinatorics, Chapter 1. - MAXIMAL_FACES: common::Array<Set<Int>>
Maximal faces of the hypersurface as a polyhedral complex. Each such face is encoded as a set of POINTS indices.
- MONOMIALS: common::Matrix<Int, NonSymmetric>
Monomials of the (tropical) polynomial defining the hypersurface. (Laurent polynomials are allowed.) The rows stands for the monomials, the columns for the variables. I.e., the entry in position (i,j) is the exponent of xj in the i-th monomial.
- NON_NEGATIVE: common::Bool
True if all MONOMIALS have non-negative exponents, this means that the hypersurface is defined by an ordinary polynomial (that is, not a Laurent polynomial).
- POINTS: common::Matrix<Rational, NonSymmetric>
Points and rays of the hypersurface, vertices of the complex. No canonicalization enforced. Note that a tropical hypersurface may be HOMOGENEOUS or not.
User Methods of Hypersurface
- opt_attained (x) → Pair<Rational,Set>
List the optimum value and the indices of the MONOMIALS for which the optimum at a given point is attained.
- privileged_subdivision () → fan::PolyhedralComplex<Rational>
Privileged subdivision dual to the tropical hypersurface. The vertices of this PolyhedralComplex are the non-redundant MONOMIALS.
These methods are for visualization.
- VISUAL () → Visual::Hypersurface
Visualizes the tropical hypersurface.
Options
option list: Visual::Polygons::decorations Returns
Visual::Hypersurface
Permutations of Hypersurface
- MonomPerm
UNDOCUMENTED
Properties of MonomPerm
- PointsPerm
UNDOCUMENTED
Properties of PointsPerm
FIXME: Include typecheck for Addition?/ Include addition!
Properties of TropicalPolytope
- AMBIENT_DIM: common::Int
Dimension of the tropical projective space which contains the tropical polytope.
- CONVEX_HULL_2D_CYCLIC: common::Array<Int>
Cyclic order of the PSEUDOVERTICES in the boundary (for dimension 2 only).
- ENVELOPE: polytope::Polytope
Tropical polytopes have a natural description as the complex of bounded faces of their envelopes. This envelope depends on the choice of the POINTS that generate the tropical polytope.
- HALF_SPACES: common::Array
Tropical halfspaces encoded as pairs of apices and sets of sectors. Maybe redundant (for now; subject to change in the future).
- POINTS: common::Matrix
Input points in homogeneous coordinates. This is the fixed system of generators with respect to which many combinatorial properties are expressed.
- PSEUDOVERTEX_COARSE_TYPES: common::Array<Array<Int>>
Coarse types of PSEUDOVERTICES relative to POINTS.
- PSEUDOVERTEX_GRAPH: graph::Graph<Undirected>
Tropical polytopes have a natural description as ordinary polytopal complexes. This is the 1-skeleton of such a complex.
- PSEUDOVERTEX_LABELS: common::Array<String>
Unique names assigned to the PSEUDOVERTICES. Can be used as "NodeLabels" in VISUAL_PLANAR.
- VERTEX_LABELS: common::Array<String>
Unique names assigned to the VERTICES. If specified, they are shown by visualization tools instead of vertex indices.
- VERTICES: common::Matrix
Vertices of the tropical convex hull in homogeneous coordinates: We normalize by setting the first homogeneous coordinate to zero.
User Methods of TropicalPolytope
These methods are for visualization.
- VISUAL () → Visual::TropicalPolytope
Visualize the tropical polytope.
Options
option list: Visual::Polygons::decorations Returns
Visual::TropicalPolytope - VISUAL_HYPERPLANE_ARRANGEMENT () → Visual::Hypersurface
Visualize the arrangement of hyperplanes with apices in the VERTICES of the tropical polytope.
Returns
Visual::Hypersurface - VISUAL_PLANAR () → Visual::TropicalPolytope
Visualize the tropical polytope projected onto the plane.
Options
Matrix Directions directions to project ontooption list: Visual::Graph::decorations Returns
Visual::TropicalPolytope - VISUAL_PSEUDOVERTEX_GRAPH () → Visual::TropicalPolytope
Visualize the PSEUDOVERTEX_GRAPH of a tropical polytope.
Options
Int seed random seed value for the string embedderoption list: Visual::Graph::decorations Returns
Visual::TropicalPolytope
Permutations of TropicalPolytope
- PseudoVertexPerm
UNDOCUMENTED
Properties of PseudoVertexPerm
User Functions
Special purpose functions.
- ch2d_3phases (n, Types, G) → Array<int>
List the pseudovertices of a 2-dimensional tropical polytope on the boundary in counter-clockwise cyclic order.
Parameters
Int n the number of generatorsArray<Array<Set>> Types the types of the generatorsGraph G Returns
Array<int> the pseudovertices on the boundary - check_minimality (T, I, n) → Set
Checks the three criteria of Gaubert and Katz to be the type T of an apex of a minimal tropical halfspace. It is assumed that the points that the type refers to are given by 0,...,n-1 and that the index set I is a subset of 0,...,d-1 where d is the AMBIENT_DIM of the tropical polytope. If the input fulfills all criteria, the output set is empty. If the input doesn't fulfill the first criterion the whole set 0,...,d-1 is given back. If the input doesn't fulfill the second and third criterion, then the violating indices are stored.
- coarse_types <Coord> (points, generators) → Array< Array<int>>
Compute the coarse types of the points set relative to a set of generators. The following are two typical cases:
(2) points = POINTS and generators = PSEUDOVERTICES - extract_pseudovertices (T, P)
Get the pseudovertices of a tropical polytope T from the bounded subcomplex of the corresponding unbounded polyhedron P.
Parameters
TropicalPolytope T polytope::Polytope P - get_corners (input) → Matrix
- lifted_pluecker (V) → Vector
- minimal_tropical_halfspaces <Coord> (T) → hash_set< Pair<Vector<Coord>,Set<Int> > >
Computes the minimal tropical halfspaces of a tropical polytope T.
- types <Coord> (points, generators) → Array<Array<Set>>
Compute the fine types of the points set relative to a set of generators. The following are two typical cases:
(2) points = POINTS and generators = PSEUDOVERTICES
These functions produce a tropical hypersurface from other objects.
- hyperplane <Addition> (coeffs) → Hypersurface<Addition>
Create a tropical hyperplane as object of type Hypersurface.
Type Parameters
Addition Parameters
Vector<Rational> coeffs coefficients of the tropical linear formReturns
Hypersurface<Addition> default Min - hypersurface_union (H1, H2, internal) → HypersurfaceUNDOCUMENTED
Parameters
Hypersurface H1 Hypersurface H2 Bool internal default 1: both input hyperplanes lie in the same spaceReturns
Hypersurface H1 cup H2 - points2hypersurface <Addition> (points) → Hypersurface
Constructs a tropical hypersurface defined by the linear hypersurfaces associated to the points. If the points are part of a min-tropical polytope then the output is a max-tropical hypersurface, and conversely.
These functions produce an object of type TropicalPolytope from other objects.
- cornered_hull (T) → TropicalPolytope
Compute the cornered hull of a tropical polytope. Cf.
M. Joswig, arXiv:0809.4694v2, Lemma 17. - cyclic (d, n) → TropicalPolytope
Produces a tropical cyclic d-polytope with n vertices. Cf.
Josephine Yu & Florian Block, arXiv: math.MG/0503279. - discard_non_vertices (points) → Matrix
- dualize <Coord> (points, generators) → Matrix
- hypersimplex (k, d) → TropicalPolytope
Produce the tropical hypersimplex Δ(k,d). Cf.
M. Joswig math/0312068v3, Ex. 2.10.The value of k defaults to 1, yielding a tropical standard simplex.
- minkowski_sum <Coord> (lambda, P, mu, Q) → TropicalPolytope
Produces the tropical polytope (lambda \( \otimes \) P) \( \oplus \) (mu \( \otimes \) Q), where \( \otimes \) and \( \oplus \) are tropical scalar multiplication and tropical addition, respectively.
Type Parameters
Coord Parameters
Scalar lambda TropicalPolytope P Scalar mu TropicalPolytope Q Returns
TropicalPolytope - poly2trop (P) → TropicalPolytope
Takes an ordinary convex polytope and interprets it in tropical projective space.
- tropical_matroid_polytope (m, v) → TropicalPolytope
Produce the tropical matroid polytope from a matroid m. Each vertex corresponds to a basis of the matroid, the non-bases coordinates get value 0, the bases coordinates get value v, default is -1.
These functions produce an object of another type not contained in application tropical.
- cornered_hull_poly (T) → polytope::Polytope
Compute the cornered hull of a tropical polytope. Cf.
M. Joswig, arXiv:0809.4694v2, Lemma 17. - pseudovertices2poly (T) → polytope::Polytope
Takes a tropical polytope T and interprets it in Euclidean space.
- trop2poly <Coord> (T) → polytope::Polytope
Given points in tropical projective space, compute an ordinary unbounded polyhedron such that the tropical convex hull of the input is the bounded subcomplex of the latter. Cf.
Develin & Sturmfels math.MG/0308254v2, Lemma 22.Warning: This client does not implement the reverse transformation to poly2trop.
- tropical_complex <Coord> (points) → fan::PolyhedralComplex
Computes the tropical complex of points.
- tropical_intersection <Coord> (pc1, pc2) → fan::PolyhedralComplex
Computes the intersection of two polyhedral complexes.
Type Parameters
Coord Parameters
fan::PolyhedralComplex pc1 fan::PolyhedralComplex pc2 Returns
fan::PolyhedralComplex
Functions for tropical arithmetic
- evaluate <Addition> (H, x) → Rational
Evaluate a tropical polynomial at a given point.
- evaluate <Addition> (H, X) → Vector<Rational>
Evaluate a tropical polynomial at a collection of points.
- nearest_point <Coord> (P, x) → Vector
Compute the projection of a point x in tropical projective space onto a tropical polytope P. Cf.
Develin & Sturmfels math.MG/0308254v2, Proposition 9. - norm <Scalar> (v) → Scalar
The tropical norm of a vector v in the tropical torus is the difference between the maximal and minimal coordinate in any coordinate representation of the vector.
- tdet <Addition, Scalar> (matrix) → Scalar
The tropical determinant of a matrix.