Numerical Methods in Algebraic Geometry


Main Conference: SIAM AG19 July 9-13, 2019 (Tue-Sat).

Location: University of Bern, Bern, Switzerland.

Our session (July 11-13): Thursday, Friday, Saturday
10am - 12pm in Unitobler, F012.

This minisymposium is meant to report on recent advances in using numerical methods in algebraic geometry: the foundation of algebraic geometry is the solving of systems of polynomial equations. When the equations to be considered are defined over a subfield of the complex numbers, numerical methods can be used to perform algebraic geometric computations forming the area of numerical algebraic geometry (NAG). Applications which have driven the development of this field include chemical and biological reaction networks, robotics and kinematics, algebraic statistics, and tropical geometry. The minisymposium will feature a diverse set of talks, ranging from the application of NAG to problems in either theory and practice, to discussions on how to implement new insights from numerical mathematics to improve existing methods.


Jose Israel Rodriguez, University of Wisconsin --- Madison.

Paul Breiding, Max-Planck-Institute for Mathematics in the Sciences Leipzig.


00:00 Elise Walker (Texas A&M) TBD.

00:00 Tingting Tang University of Notre Dame: TBD.

00:00 Anton Leykin (Georgia Tech) TBD.

00:00 Simon Telen (KU Leuven) TBD.

00:00 Emre Sertoz (Max-Planck-Institute MiS, Leipzig) TBD.

00:00 Tsung-Lin Lee (National Sun Yat-sen University) TBD.

00:00 Agnes Szanto (NCSU) TBD.

00:00 Margaret Regan (University of Notre Dame) TBD.

00:00 Sascha Timme (TU Berlin) TBD.

00:00 Justin Chen (Georgia Tech) TBD.


Justin Chen (Georgia Tech)
Numerical Implicitization

It is increasingly important nowadays to perform explicit computations on varieties, even in the realm where symbolic (e.g. Grobner basis) methods are too slow. We give an overview of the Macaulay2 package NumericalImplicitization, which aims to provide numerical information about images of varieties, such as dimension, degree, and Hilbert function. We also discuss some changes and additions to the package, such as improvements to point sampling, completions of partial pseudo-witness sets, and parallelization. This is joint work with Joe Kileel.

Tsung-Lin Lee (National Sun Yat-sen University)
Computing the real CANDECOMP/PARAFAC decomposition of real tensors

The real Candecomp/Parafac decomposition (CPD) has many applications in psychometrics, chemometrics, signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, neuroscience, graph analysis, and elsewhere. Several methods have been provided for computing the CPD such as alternating least squares (ALS), nonlinear least squares (NLS) and unconstrained nonlinear optimization. Those methods may take many iterations to converge and are not guar-anteed to converge to the solution. Recently, homotopy continuation techniques have been applied in computing tensor decomposition. In this talk, the real CPD of a real unbalanced tensor will be considered.

Anton Leykin (Georgia Tech)
Minimal problems in multiview 3D reconstruction via homotopy continuation

This will be a short survey of a class of problems in computer vision, for which it is plausible to construct efficient solvers based on polynomial homotopy continuation. For some of these problems alternative solvers do not exist at the moment.
The problems we consider concern relative camera pose recovery from points and lines in more than 2 views. In addition to classical point correspondences and line correspondences, we use incidence correspondences, which result from points lying on lines. We show how to build a solver based on a parameter homotopy coming from this framework.
(This survey is based on collaboration and discussions with many people involved in the Nonlinear Algebra semester at ICERM in Fall 2018.)

Margaret Regan (University of Notre Dame)
Numerical computation of monodromy action over R

The monodromy group (over the complex numbers) is a geometric invariant that encodes the structure of the solutions for a parameterized family of polynomial systems and can be computed using numerical algebraic geometry. Since a naive extension to the real numbers is very restrictive, this talk will explore a new approach over the real numbers which is computed piece-wise to obtain tiered characteristics of the real solution set. This talk will conclude with an application in kinematics to help highlight the computational method and impact on calibration.

Emre Sertoz (Max-Planck-Institute MiS, Leipzig)
Computing transcendental invariants of hypersurfaces via homotopy.

Deep geometric properties of each projective variety is encoded in a matrix of complex numbers, called its periods. Knowing the periods of a variety, one can often say quite a lot about the type of subvarieties it contains using LLL methods, without resorting to symbolic elimination. However, numerical computation of periods have been previously confined to curves in the plane and to varieties enjoying many symmetries. We will demonstrate how periods of hypersurfaces can be computed using a form of homotopy and how they can be studied to reveal the geometry of the hypersurface.

Agnes Szanto (NCSU)
Certification of approximate roots of exact ill-posed polynomial systems

In this talk, I will survey some of our recent work on certifying approximate roots of exact polynomial systems and will describe some applications. In particular, we will concentrate on systems with root multiplicity, and show ways to certify approximations to singular roots, as well as their multiplicity structure. The difficulty lies in the fact that having singular roots is not a continuous property, so traditional numerical certification techniques do not work. Our certification methods are based on hybrid symbolic-numeric techniques. This is joint work with Jonathan Hauenstein and Bernard Mourrain.

Tingting Tang University of Notre Dame
On the nonlinearity interval in parametric semidefinite optimization

We consider the parametric analysis of semidefinite optimization problems with respect to the perturbation of the objective vector along a fixed direction. We characterize the so-called transition point of the optimal partition where the ranks of a maximally complementary optimal solution suddenly change, and the nonlinearity interval of the optimal partition where the ranks of maximally complementary optimal solutions stay constant. The continuity of the optimal set mapping on the basis of Painleve-Kuratowski set convergence in a nonlinearity interval is investigated. We show that not only the continuity might fail, even the sequence of maximally complementary optimal solutions might jump in the interior of a nonlinearity interval. Finally, we present a procedure stemming from numerical algebraic geometry to efficiently compute nonlinearity intervals.

Simon Telen (KU Leuven)
Numerical Root Finding via Cox Rings

In this talk, we consider the problem of solving a system of (sparse) Laurent polynomial equations defining finitely many nonsingular points on a compact toric variety. The Cox ring of this toric variety is a generalization of the homogeneous coordinate ring of projective space. We work with multiplication maps in graded pieces of this ring to generalize the eigenvalue, eigenvector theorem for root finding in affine space. We present a numerical linear algebra algorithm for computing the corresponding matrices, and from these matrices a set of homogeneous coordinates of the roots of the system. Several numerical experiments show the effectiveness of the resulting method, especially for solving (nearly) degenerate, high degree systems in small numbers of variables..

Sascha Timme (TU Berlin)
Adaptive step size control for homotopy continuation methods

At the heart of homotopy continuation methods lies the numerical tracking of implicitly defined paths by a predictor-corrector scheme. For efficient path tracking the predictor step size must be chosen appropriately. We present a new adaptive step size control which changes the step size based on computational estimates of local geometric information as well as the order of the used predictor method. We also give an update on the Julia package HomotopyContinuation.jl.

Elise Walker (Texas A&M)
Numerical homotopies from Khovanskii bases

Homotopies are useful numerical methods for solving systems of polynomial equations. I will present such a homotopy method using Khovanskii bases. Finite Khovanskii bases provide a flat degeneration to a toric variety, which consequentially gives a homotopy. The polyhedral homotopy, which is implemented in PHCPack, can be used to solve for points on a general linear slice of this toric variety. These points can then be traced via the Khovanskii homotopy to points on a general linear slice of the original variety. This is joint work with Michael Burr and Frank Sottile.

Important information for speakers

1. The rules of SIAM do not allow a speaker to present multiple talks at this conference. Here is a list of other proposed sessions special sessions.

2. Talks will be 19-21 minutes plus 4 minutes for questions. (At 17 minutes, a signal will be given if desired).

3. Titles and abstracts should be emailed to Jose Israel Rodriguez by February 21.

4. The minisymposium ID number is 173.

5. Housing information: You are encouraged to make your accomodations by April 31. The local organizers have provided a list of possible options. A facebook page has been set up where people wanting to share hotel rooms can find a room mate:

6. Students/Early-career participants can apply for travel support here.

7. Early registraton is open and expires June 1. Please consult this website.

Extra Links

SIAM AG Activity Group.