Abstract: The classical problem of studying the topology of an algebraic curve is typically handled by the computation of braid monodromies. The existence of arithmetic Zariski pairs implies that purely algebraic methods cannot provide those braids, so we need numerical methods at some point. However numerical methods usually have the problem that floating point arithmetic introduces rounding errors that must be controlled to ensure certified results.
We present SIROCCO, a library for certified polynomial root continuation, specially suited for this task. It computes piecewise linear approximations of the paths followed by the roots. The library ensures that there exist disjoint tubular neighborhoods that contain both the actual path and the computed approximation. This fact proves that the braids corresponding to the approximation are equal to the ones corresponding to the actual curve. The validation is based on interval floating point arithmetic, the Interval Newton Criterion and auxiliary lemmas.
We also provide a SageMath interface and auxiliary routines that perform all the needed pre and post-processing tasks. Together this is an "out of the box" solution to compute, for instance, the fundamental group of the complement of an affine complex curve.
Abstract Singular is a comprehensive and steadily growing computer algebra system, with particular emphasis on applications in algebraic geometry, commutative algebra, and singularity theory.
Singular provides highly efficient core algorithms, a multitude of advanced algorithms in the above fields, an intuitive, C-like programming language,i easy ways to make it user-extendable through libraries, and a comprehensive online manual and help function.
Singular's core algorithms handle Gröbner resp. standard bases and free resolutions, polynomial factorization, resultants, characteristic sets, and numerical root finding.
Its advanced algorithms, contained in its libraries, address topics such as absolute factorization, algebraic D-modules, classification of singularities, deformation theory, Gauss-Manin systems, Hamburger-Noether (Puiseux) development, invariant theory, homological algebra, normalization, primary decomposition, resolution of singularities, and sheaf cohomology.
Symbolic-numeric solving in Singular starts with a decomposition to a triangular system or the primary decomposition of (the radical of) an ideal. New developments for primary decomposition will be presented in this talk: identifying sub problems allows an early split of the radical. A primary decomposition of these sub problems can be lifted to (not necessary primary) decomposition of the original problem: the following primary decomposition will be faster.
After the symbolic preprocessing numerical solving of these smaller and easier to solve systems can be achieved by Singular's implementation of Laguerre's algorithm or by integrating other systems. A easy way to extend Singular in this perspective will be shown.
Abstract In this talk we report on a C++ implementation of the tropical homotopy method for computing mixed volumes of lattice polytopes. The implemented algorithm was proposed at MEGA 2015 as a variant of Malajovich' approach but with the improvements that it is exact and memoryless. Prior to the presented implementation these new methods performed in practise much as more conventional methods (Li et al) although they have better theoretical asymptotic complexity bounds. In the presented implementation the focus has been on symbolically perturbing lifts, eliminating integer division, catching integer overflows, making cache-friendly memory layout and allowing vectorisation. The code is templated with the possibility of specialising computations to particular ring implementations. Such implementations include 32-bit machine integers, but can also be integers with arbitrary precision. While the mixed volume of a set of Newton polytopes bounds the number isolated solutions to square polynomial systems, the enumeration of mixed cells allows numerical polynomial system solving via polyhedral homotopy (Huber, Sturmfels). Therefore a future goal is to produce mixed cells for lifts numerically suitable for polyhedral homotopy rather than using symbolic lifts. With the software we successfully computed the mixed volume of cyclic-14 in 97 seconds in a single thread.
Abstract Algebraic methods for solving polynomial equations exploit the structure of quotient algebra. Border basis computation allows to construct efficiently a basis and the tensor of multiplication, which describes effectively the structure of an artinian quotient algebra. The solution of polynomial equations can be deduced by eigenvalues computation or by solving univariate polynomials. We describe dedicated tools for computing border bases and the solutions of polynomial equations, implemented in the software package borderbasix. We present the main ingredients of the border basis algorithm, the fast linear algebra solvers for dense and sparse matrices and the numerical solution from multiplication matrices. Border basis computation can be combined with moment relaxation techniques to find the minimizers of a polynomial optimization problem or the real radical of an ideal. We describe this approach, combining SDP solvers and border basis reduction on polynomials. The implementation of border basis tools is parametrized by the coefficient type and the choice function, providing a versatile family of solvers for computation with modular arithmetic, floating point arithmetic or rational arithmetic. Extensive benchmarks on typical polynomial systems and polynomial optimisation problems illustrate the excellent performance of the tool.
Abstract Numerical algebraic geometry frequently uses methods which compute over the complex numbers, using probability-one arguments as a mathematical foundation. Computation of the real part of a variety is challenging, but important since applications of coming from engineering and science are commonly interested only in real solutions.
This talk will discuss an algorithm for the computation of tropical curves using numerical algebraic geometry. The method uses path tracking and monodromy to directly compute Puiseux series coefficients for the branches of the curve. In turn, the valuation of the series gives rise to the tropical rays of the tropical curve itself. Furthermore, real curves are computable with minor changes to the complex algorithm.