3C in G Workshop on Computational Algebra

Normaliz is a versatile package for computations in discrete convex geometry: it computes lattice points in polyhedra, or, from a different perspective, solves linear diophantine systems of inequalities, equations and congruences.

Recently it has been included in benchmarks of convex hull computation (or vertex enumeration), and has often outperformed dedicated systems, especially on large problems. We will present Normaliz' approach to convex hulls. The main tool is pyramid decomposition whose development was sparked off by the more difficult task of computing triangulations. Pyramid decomposition allows "localization" and helps to break the often forbidding complexity of pure Fourier-Motzkin elimination. Furthermore it is parallelization friendly.

Based on: W. Bruns, B. Ichim and C. Söger, The power of pyramid decomposition in Normaliz. J. Symb. Comp. 74 (2016), 513--536.

Determinantal singularities form a class of singularities which seem at first glance more complicated than complete intersection singularities. However, this larger class also contains singularities which are from a certain point of view simpler than the simplest complete intersections - just think of the three coordinate axes in C³.

Up to now the study of determinantal singularities has been impeded by the failure of many standard techniques, as soon as one left the realm of complete intersections. In this talk I shall give a brief overview on similarities and differences to the complete intersection case, on open questions and on tools to study the topology and deformation properties for some important subclasses of such singularities in detail.

Most research would be impossible without software, and this reliance is forcing a rethink of the skills needed in a traditional research group. A survey of 15 Russell Group universities found that 92% of researchers used research software, 67% reported that it was fundamental to their research, and 56% said they developed their own software. With the emergence of software as the pre-eminent research tool used across all disciplines, comes the realisation that a significant majority of results are based, ultimately, on the skill of the experts who design and build it.

The work of software experts in academia is rarely recognised, and they suffer poor conditions of employment relative to other research roles. Since 2012, a community of these experts has grown around a campaign to raise awareness of the people who build the software used in research. These people have worked under many titles, but many now identify as Research Software Engineers.

By providing the expertise needed by modern research groups, we will promote the development of well-engineered software that will increase the scope, productivity and reliability of research.

Deciding if a polynomial ideal contains monomials is a problem which can be solved by usual Groebner basis techniques. Deciding if a polynomial ideal contains binomials is more complicated. We show how the general case can be reduced to the case of zero-dimensional ideals using projections and stable intersections in tropical geometry. In the case of rational coefficients the zero-dimensional problem can then be solved via Ge's algorithm using methods by Babai, Beals, Cai, Ivanyos and Luks. In case binomials exist, one can be computed.

This is joint work with Thomas Kahle and Lukas Katthän.

Polyhedral adjunction theory allows to study questions of classical adjunction theory for polarised toric varieties from a convex-geometric viewpoint using the associated polyhedral fans and lattice polytopes. Important algebraic invariants like the (unnormalised) spectral value or the nef-value can be defined and studied purely in terms of these polytopes.

Using this approach we obtain structural results for lattice polytopes and their toric varieties. In particular we can show that a lattice polytope with sufficiently large spectral value has a Cayley structure, i.e. it allows a non-trivial lattice projection onto a lattice simplex. We can also affirmatively answer a conjecture of Fujita on the spectrum of the spectral value in the toric case.

This is partially based on joint work with Benjamin Nill, Christian Haase, and Sandra Di Rocco.

The computation of the roots of a univariate polynomial is one of the best studied problems in the areas of computer algebra and numerical analysis. Nevertheless, until recently, there has still been a large discrepancy between methods that are considered to be efficient in practice and those that achieve good theoretical bounds. In the first part of this talk, I will review some recently developed algorithms for real and complex root finding, which are simple and practical on the one hand and whose worst-case bit complexity matches that of the best methods in theory on the other hand. Combining our techniques with a classical approach that considers so-called fractional derivatives, we can further derive a polynomial-time algorithm to compute approximations of all real roots of a sparse polynomial with arbitrary real coefficients. For very sparse polynomials with integer coefficients, the method performs near-optimal.

In the second part of my talk, I will focus on the more general problem of computing the solutions of a given zero-dimensional polynomial system in d variables. A common approach for computing the set S of solutions is to first project S into one dimension (e.g. using resultant computation and univariate root finding) and then to recover the solutions from the projections. The latter step turns out to be difficult if the projection direction is not known to be separating for the solutions. I will review a simple and efficient algorithm for the certified computation of S, which only needs to compute projections of the solutions but no further algebraic manipulations. It computes a separating direction of small bit-size as well as isolating boxes for all solutions for the cost of O(d) projections of the solutions. Finally, I will sketch a symbolic-numeric algorithm to count the number of solutions within a local region, which is based on a "local variant" of the rather global method from above. Assuming the existence of an oracle that provides arbitrary good approximations of the solutions of the system, our method can be used to verify correctness of these approximations. In contrast to global approaches, the complexity of our method mainly depends on local parameters such as the number of roots within the given region or the size of this region.

Calabi-Yau 3-folds play a large role in string theory. Cohomology of sheaves on such varieties has many uses in string theory, including counting the number of particles or fields in a theory, as well as to help identify terms in the superpotential that determines the equations of motion of the corresponding string theory, and many other uses as well. As a computational algebraic geometer, string theory provide a rich source of new computational problems to solve.

In this talk, we focus on the search for rigid divisors on these Calabi-Yau hypersurfaces of toric varieties. We have had methods to compute sheaf cohomology on these varieties for many years now (Eisenbud-Mustata-Stillman, around 2000), but these methods fail for many of the examples of interest, in that they take a very long time, or the software (wisely) refuses to try!

We provide techniques and formulas for the sheaf cohomology of certain divisors of interest in string theory, that other current methods cannot handle. Along the way, we describe a Macaulay2 package for computing with these objects, and show its use on examples.

This is joint work with Andreas Braun, Cody Long, Liam McAllister, and Benjamin Sung.