Conference Agenda

Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

 
Session Overview
Session
MS179, part 1: Algebraic methods for polynomial system solving
Time:
Friday, 12/Jul/2019:
10:00am - 12:00pm

Location: Unitobler, F021
104 seats, 126m^2

Presentations
10:00am - 12:00pm

Algebraic methods for polynomial system solving solving

Chair(s): Mohab Safey El Din (Sorbonne Université, France), Éric Schost (University of Waterloo)

Polynomial system solving is at the heart of computational algebra and computational algebraic geometry. It arises in many applications ranging from computer security and coding theory (where computations must be done over finite fields) and engineering sciences such as chemistry, biology, signal theory or robotics among many others (here computations are done over inifinite domains such as complex or real numbers). The need of reliable algorithms for solving these problems is prominent because of the non-linear nature of the problems we have in hand.

Algebraic methods provide a nice framework for designing efficient and reliable algorithms solving polynoial systems. This mini-symposium will cover many aspects of this topic, including design of symbolic computation algorithms as well as the use of numerical methods in this framework with an emphasis on reliability.

 

(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)

 

Exploiting fast linear algebra in the computation of multivariate relations

Vincent Neiger
Univ. Limoges

We consider the problem of computing multivariate relations in a finite-dimensional setting: for a submodule M of K[x]^n such that Q = K[x]^n/M has finite dimension D as a K-vector space, and given elements f1,..,fm in Q, the problem is to compute relations between the fi's, that is, polynomials (p1,..,pm) in K[x]^m such that p1 f1 + ... + pm fm = 0 in Q.

Assume that the multiplication matrices of the r variables with respect to some basis of Q are known. Then, for any monomial order, we give an algorithm for computing the reduced Gröbner basis of the module of such relations using O(r D^w log(D)) operations in the base field K, where w is the exponent of matrix multiplication. We also show that, under some assumptions, the multiplication matrices can be computed from a Gröbner basis of M within the same complexity bound, leading in particular to a change of monomial order algorithm whose complexity bound is sub-cubic in D.

Contains joint work with Éric Schost and Hamid Rahkooy

 

Certification via squaring-up

Timothy Duff
Georgia Tech

We consider numerical certification of approximate solutions to N polynomial equations in n variables in the case where n < N via passing to a square subsystem. Typically the excess complex solutions of a general squaring-up are all isolated, and their number is given in terms of a birationally-invariant intersection index. This enables certification, via Smale and Shub's alpha-theory, for examples where the intersection index is known a priori, or in cases where it may be calculated algorithmically in terms of an associated Newton-Okounkov body.

joint w/ Frank Sottile (Texas A&M)

 

Efficient and complete certification of roots in solving polynomial systems

Michael Burr
Clemson Univ.

A certified algorithm is an algorithm that provides a proof or certificate of the correctness of its output. A complete algorithm is one that can be correctly implemented on a computer using a bit-based computation mode l. In this talk, I will present recent work on certification methods for solving polynomial systems. I will focus on two paradigms for certifying solutions to polynomial systems: A posteriori approaches take the output of (any) computation and check the correctness of the result. A priori approaches prove that an entire computation is correct, including the output. In particular, I will discuss how interval arithmetic-based methods can be used to make certification algorithms efficient in practice.

 

Reconstruction of an Algebraic Surface from a 2D Projection

Joseph Schicho
Johannes Kepler Univ.

An algebraic surface is given by its equation, the zero set of a polynomial in four homogeneous variables. Its picture under central projection is computed as the zero set of its discriminant: a plane algebraic curve. Can we recover the equation of an algebraic surface by its discriminant? If the surface is nonsingular, then the answer is yes, by a result of d'Almeida. If we allow also "generic" singularities, then the there is sometimes a finite list of possibles. This talk explains the resconstruction method and discusses the ambiguities in the singular case.