Convex polyhedra and lattice polyhedra occur in linear and discrete optimization as the feasible regions of linear programs. In algebraic geometry and its applications piecewise-linear shapes occur in the guise of polyhedral fans. Examples include secondary fans and Gröbner fans, which play major roles, e.g., in tropical geometry. This session wants to bring together people working on algorithms and software dealing with the above structures.
|Monday||14:00 - 14:30 (CEST)|
|Jonathan Kliem, Janko Boehm, and Andreas Paffenholz|
|Monday||15:50 - 16:20 (CEST)|
|Leon Eifler, Winfried Bruns, and Rui-Juan Jing|
|Tuesday||14:00 - 14:30 (CEST)|
|Michael Joswig, Alheydis Geiger, and Marta Panizzut|
|Tuesday||15:50 - 16:20 (CEST)|
|Lars Kastner, Anders Jensen, and Cvetelina Hill|
|Wednesday||14:00 - 14:30 (CEST)|
|Xavier Allamigeon, Helen Naumann, and Oğuzhan Yürük|
|Wednesday||15:50 - 16:20 (CEST)|
|Antonio Macchia, Leon Zhang, and Rudy Yoshida|
|Thursday||14:00 - 14:30 (CEST)|
|Apostolos Chalkis and Maxim Demenkov|
A convex programming approach to solve posynomial systems
Xavier Allamigeon, École Polytechnique
We exhibit a class of classical or tropical posynomial systems which can be solved by reduction to linear or convex programming problems. This relies on a notion of colorful vectors with respect to a collection of Newton polytopes. This extends the convex programming approach of one player stochastic games. This is joint work with Marianne Akian, Marin Boyet and Stéphane Gaubert.
Massively parallel fan traversals and applications
Janko Böhm, Universität Kaiserslautern
In computational algebraic geometry, fan traversals frequently occur at the interplay of algebraic and combinatorial constructions. In this talk, we first focus on the design and implementation of a massively parallel approach to fan traversals. Our approach is based on the workflow management system GPI-Space, which uses Petri nets to model the algorithm in the coordination layer, while in the computation layer we rely on the computer algebra system Singular. We then discuss various applications of the fan traversal in algebraic geometry. We also comment on the parallel efficiency and scaling of the performance on large HPC clusters.
Recent developments in Normaliz
Winfried Bruns, Universität Osnabrück
Since the ICMS 2016 Normaliz has been extended in various directions (in addition to numerous minor improvements): project-and-lift for lattice points, descent algorithm for volumes, algebraic polyhedra, face lattice and f-vector, automorphism groups, python interface and integration into SageMath. I will discuss one or two of them in some detail.
Practical volume of estimation of zonotopes by a new annealing schedule for cooling convex bodies
Apostolos Chalkis, University of Athens
We study the problem of estimating the volume of convex polytopes, focusing on zonotopes. Although a lot of effort is devoted to practical algorithms for polytopes given as an intersection of halfspaces, there is no such method for zonotopes. Our algorithm is based on Multiphase Monte Carlo (MMC) and our main contributions include: (i) a new uniform sampler employing Billiard Walk for the first time in volume computation,showing it mixes much faster than the current main paradigm (i.e. Hit-and-Run), (ii) a new simulated annealing generalizing existing MMC by making use of adaptive convex bodies which fit to the input, thus drastically reducing the number of phases. Extensive experiments on zonotopes show our algorithm requires sub-linear in the dimension oracle calls while the best theoretical bound is cubic. Moreover our algorithm can be easily generalized for any convex body. We offer an open-source, optimized C++ implementation, and analyze its performance. Our code tackles problems intractable so far, offering the first efficient algorithm for zonotopes which scales with the dimension (e.g. one hundred dimensions in less than 1hr). We illustrate our C++ software in evaluating zonotope approximations. This is joint work with Ioannis Z. Emiris and Vissarion Fisikopoulos.
Polyhedral annexation revisited
Maxim Demenkov, Institute of Control Sciences (Moscow)
We describe a method for inner polyhedral approximation of convex sets and the preliminary results of its implementation in Julia programming language for the particular class of polytopic sets. The method builds a sequence of inner polytopic approximations of a convex set, which in the case of polytopic sets converges to the set itself in a finite number of steps. New vertices of such an approximation are obtained by optimizing linear functions (constructed from the facet-defining inequalities for the inner polytope) over the set. During several decades, it has been reinvented in many different contexts such as concave programming, beneath-beyond method for convex hull computation, reachable sets estimation in dynamical systems, polytope projection, computation of Newton polytopes in algebraic geometry, multi-objective optimization and computational molecular biology.
The SCIP Optimization Suite 7.0
Leon Eifler, Zuse Institute Berlin
The SCIP Optimization Suite is a collection of software packages for mathematical optimization, centered around the constraint integer programming framework SCIP. We give an overview of new and improved features introduced in the recent release and give a more in-depth discussion of tree-size estimation and PaPILO. Regarding tree-size estimation, SCIP is now able to guess the remaining tree-size, using different completion measures and performing either linear or random forest regression. SCIP will then perform restarts during the tree search, based on this estimation. Furthermore, we present PaPILO, a new matrix-based parallel presolving library for MIP and LP. This library is called as a presolving technique from SCIP, but can also be incorporated into any other MIP or LP solver.
Tropical algebraic geometry - A tropical count of binodal cubic surfaces
Alheydis Geiger, Eberhard Karls Universität Tübingen
In this talk I will give a short introduction to tropical algebraic geometry based on a tropical count of binodal cubic surfaces (joint work with Madeline Brandt). There are 280 binodal cubic surfaces through 17 points in general position. They can be counted using tropical geometry. After a brief introduction into tropical geometry we see how the dual subdivision of the Newton polytope allows us to count surfaces through points in Mikhalkin position via floor plans. We will see that we can recover 214 binodal surfaces with separated nodes in their tropicalizations and we will also have a short look at the complexes hiding the remaining 66 surfaces.
Tropical hypersurface intersections and cone classes in gfanlib
Anders Jensen, Aarhus Universitet
The intersection of a finite set of tropical hypersurfaces may be computed by exhaustively traversing an enumeration tree. The computation plays an important role in tropical geometry, although it is better replaced with algebraic methods when possible. We report on the implementation of a new polyhedral cone class in the coming version of gfanlib and its use in the enumeration. For better performance the templated pivoting has been implemented with machine integers in mind, while the use of halfopen cones plays an important role in several aspects of the computation. In particular, they allow discarding branches of the enumeration tree, dynamical decomposition of the tropical hypersurfaces, easier extraction of the face lattice of a fan and representing polyhedral complexes as fans.
The Z_Polyhedra library in Maple
Rui-Juan Jing, University of Western Ontario
Solving systems of linear equations is a well-studied and fundamental problem in mathematical sciences. When the input system includes equations as well as inequalities, the algebraic complexity of this problem increases from polynomial time to single exponential time with respect to the number of variables. When, in addition, the solution points with integer coordinates are the only ones of interest, the problem becomes even harder and is still actively investigated. We provide the Z_Polyhedra library, which is written in Maple and dedicated to solving problems dealing with the integer points of polyhedral sets. Those problems include decomposing the integer points of polyhedral sets, solving parametric integer programs, performing dependence analysis in for-loop nests and determining the validity of certain Presburger formulas. We report on the design of the Z_Polyhedra library and numerous illustrations of its usage. This is joint work with Marc Moreno Maza.
Real tropical hyperfaces by patchworking in polymake
Michael Joswig, TU Berlin and MPI-MIS
Hilbert's 16th problem asks what kind of topological constraints hold for real algebraic hypersurfaces in projective space. In the 1980s Viro developed patchworking as a method to construct real algebraic hypersurfaces with unsually large mod 2 Betti numbers. Interpreted within the larger framework of tropical geometry, patchworking leads to a combinatorial approach to real tropical hypersurfaces. We report on a recent implementation of this method in polymake, we compare with a previous implementation of de Wolff et al. in Sage, and we report on experiments with surfaces of degrees 4 and 5.
This is joint work with Paul Vater (MPI-MIS, Leipzig)
Hyperplane arrangements in polymake
Lars Kastner, Technische Universität Berlin
Hyperplane arrangements play an important in many areas of mathematics, such as algebraic geometry and combinatorics. Every hyperplane arrangement induces a subdivision of the whole space into a polyhedral fan. Often this fan is used for parametrizing certain objects, such as in GIT. Computing this fan structure becomes challenging, even for relatively small cases. In this talk we will discuss how hyperplane arrangements are encoded in polymake and how to compute the associated polyhedral fan structure, without taking the brute force approach.
A new face iterator for polyhedra
Jonathan Kliem, Freie Universität Berlin
I will briefly discuss a depth-first algorithm to iterate over the faces of polyhedra (joint work with Christian Stump). This algorithm is implemented in SageMath and has very little memory usage, such memory is no longer a limiting factor (e.g. when computing the f-vector). It can be parallelized easily and along with some improvements (yet to be peer-reviewed) is much faster than other available implementations. The algorithm can be applied to other situations such as finite polyhedral complexes, subdivisions of manifolds, extended tight spans and closed sets of matroids.
Computation of tropical convex hull of infinite sets
Cvetelina Hill, Georgia Tech
In this talk I will present some recent results on the interplay between tropical and classical convexity. In particular, I will focus on the tropical convex hull of convex sets and polyhedral complexes and their explicit computation. This will lead to a lower bound on the degree of tropical curves.
This is joint work with Sara Lamboglia and Faye Pasley Simon.
Computing slack ideals in Macaulay2
Antonio Macchia, Freie Universität Berlin
Recently Gouveia, Macchia, Thomas and Wiebe introduced the slack realization space, a new model for the realization space of a polytope. It represents each polytope by its slack matrix, the matrix obtained by evaluating its defining inequalities at each vertex. Unlike the classical model, the slack model naturally mods out projective transformations. It is inherently algebraic, arising as the positive part of a variety of a saturated determinantal ideal, and provides a new computational tool to study classical problems, such as realizability of combinatorial polytopes, rational realizability, and nonprescribability of faces. I will present a Macaulay2 package, developed with Amy Wiebe, to compute slack matrices and slack ideals of convex polytopes or matroids. Slack ideals are often difficult to compute. To improve the power of this model, we develop two strategies to simplify computations: we scale as many entries of the slack matrix as possible to one; we then obtain a reduced slack model combining the slack variety with the more compact Grassmannian model. This allows us to study slack ideals that were previously out of computational reach.As applications, we show that the well-known Perles polytope does not admit rational realizations and prove the non-realizability of some simplicial spheres.
A unified framework of SAGE and SONC polynomials and its duality theory
Helen Naumann, Goethe Universität Frankfurt
We introduce and study a cone which consists of a class of generalized polynomial functions and which provides a common framework for recent non-negativity certificates of polynomials in sparse settings. Specifically, this S-cone generalizes and unifies sums of arithmetic-geometric mean exponentials (SAGE) and sums of non-negative circuit polynomials (SONC). We provide a comprehensive characterization of the dual cone of the S-cone, which even for its specializations provides novel and projection-free descriptions.
In this talk, we give an exact characterization of the extreme rays of the S-cone and thus also of its specializations.
This is joint work with Lukas Katthän and Thorsten Theobald
polyDB: A Database for Polytopes and Related Objects
Andreas Paffenholz, Technische Universität Darmstadt
polyDB (polydb.org) is a new database for discrete geometric objects that aims to make datasets and classifications in this area easily accessible to researchers. Computational methods and the analysis of existing classifications of geometric objects are an increasingly useful way to support research and require a flexible tool to work with the data. polyDB tries to provide such a tool and already contains a growing set of data collections from the area of lattice polytopes, combinatorial polytopes, manifolds, matroids, and tropical geometry. The database is based on MongoDB and is currently accessible via its web interface and an interface from the software package polymake (polymake.org). However, it is designed so that its data can also easily be accessed from other software frameworks. In my talk I will first introduce the structure of the database, its interfaces, and options to obtain the data or contribute new datasets. In a second part I will show some explicit applications where polyDB has been used to study objects in discrete and tropical geometry. This will be done using the interface to the software polymake, which allows easy integration of the database access within the actual computations.
The Schläfli Fan
Marta Panizzut, Technische Universität Berlin
In 1849, Arthur Cayley and George Salmon proved one of the most famous results in algebraic geometry: every smooth cubic surface contains exactly 27 lines. In tropical geometry algebraic surfaces are replaced with polyhedral complexes of dimension two. Since the early development of this recent mathematical field, two natural problems were to understand whether the same statement holds for smooth tropical cubic surfaces and to classify combinatorial positions of their tropical lines. The answer to the first turned out to be false, as smooth tropical surfaces might contain families of tropical lines. Moreover, classifying positions of tropical lines reveals some computational challenges due to the massive number of combinatorial types of smooth tropical cubic surfaces. The latter are parametrized by 14 373 645 symmetry classes of maximal cones in the unimodular secondary fan of the triple tetrahedron. The Schläfli fan gives a further refinement of these cones, and it reveals all possible patterns of the 27 or more lines on tropical cubic surfaces, thus serving as a combinatorial base space for the universal Fano scheme. In this talk we will introduce the topic focusing in particular on the
algorithmic and computational aspects.
This is based on joint work with Michael Joswig and Bernd Sturmfels.
Tropical Support Vector Machines
Rudy Yoshida, Naval Postgraduate School
Most data in genome-wide phylogenetic analysis (phylogenomics) is essentially multidimensional, posing a major challenge to human comprehension and computational analysis. Also, we cannot directly apply statistical learning models in data science to a set of phylogenetic trees since the space of phylogenetic trees is not Euclidean. In fact, the space of phylogenetic trees is a tropical Grassmannian in terms of max-plus algebra. Therefore, to classify multi-locus data sets for phylogenetic analysis, we propose tropical Support Vector Machines (SVMs) over the space of phylogenetic trees. As classical SVMs, a tropical SVM is a discriminative classifier defined by the tropical hyperplane which maximizes the minimum tropical distance from data points to itself to separate these data points into tropical half spaces. We show that we can formulate hard margin tropical SVMs and soft margin tropical SVMs as linear programming problems. In addition, we show the necessary and sufficient conditions for each instance to be feasible and, in each case, there is an explicit formula for the optimal solution for the feasible linear programming problem. Based on our theorems, we develop novel methods to compute tropical SVMs and computational experiments show our methods work well.
This is joint work with Xiaoxian Tang and Houjie Wang.
Initial Steps in the Classification of Maximal Mediated Sets
Oğuzhan Yürük, Technische Universität Braunschweig
Maximal mediated sets (MMS), introduced by Bruce Reznick, are distinguished subsets of lattice points in integral polytopes with even vertices. MMS of Newton polytopes of nonnegative circuit polynomials determine whether these polynomials are sums of squares. In this talk, we present the initial theoretical and practical steps in classifying MMS. Theoretically, we show that MMS of simplices are isomorphic if and only if the simplices generate the same lattice up to coordinate permutations. On the practical side, we fully characterize MMS for all simplices of sufficiently small dimensions and maximal 1-norms via large scale computations carried out on Polymake. We will discuss some aspects of the distribution of the density of MMS discuss that that are inferred from our computations. In particular, we provide an experimental verification of a conjecture by Reznick for 2 dimensional simplices up to maximal 1-norm 150.
This is a joint work with Jacob Hartzer, Olivia Röhrig and Timo de Wolff.
Argmin of metric optimization problems in the affine building of SLk
Leon Zhang, University of California at Berkeley
Le showed that the tropicalization of certain canonical functions introduced by Fock and Goncharov can be reformulated as metric optimization problems over the affine building of SLk. We describe the arguments of the minimum for these optimization problems, which have a nice polyhedral description when restricted to single apartments.This is joint work with Melissa Sherman-Bennett.
© 2020. All rights reserved.