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
MS160, part 3: Numerical methods for structured polynomial system solving
Time:
Thursday, 11/Jul/2019:
3:00pm - 5:00pm

Location: Unitobler, F012
30 seats, 57m^2

Presentations
3:00pm - 5:00pm

Numerical methods for structured polynomial system solving

Chair(s): Alperen Ergur (TU Berlin), Pierre Lairez (INRIA), Gregorio Malajovich (Universidade Federal do Rio de Janeiro, Brazil), Josue Tonelli-Cueto (TU Berlin)

Improvements in the understanding of numerical methods for dense polynomial system solving led to the complete solution of Smale's 17th problem. At this point, it remains an open challenge to achieve the same success in the solution of structured polynomial systems: explain the typical behavior of current algorithms and devise polynomial-time algorithms for computing roots of polynomial systems. In this minisymposium, researchers will present the current progress on applying numerical methods to structured polynomial systems.

 

(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)

 

Certifying solutions to a square system involving analytic functions

Michael Burr1, Kisun Lee2, Anton Leykin2
1Clemson University, 2Georgia Institute of Technology

In this talk, we introduce two different approaches for the certification of solutions to a square system built from univariate analytic functions. The first approach is based on alpha-theory, and the second is based on interval Newton's Method. The certification methods are based on the existence of oracles from input analytic functions. We show that these two oracles exist for D-finite functions. Finally, we compare these two approaches using our SageMath implementation for D-finite function cases.

 

Toric witness sets for sampling positive dimensional solution sets of polynomial systems

Tianran Chen
Auburn University at Montgomery

The linear slicing technique and the construction of "witness sets" proposed by Sommese and Wampler in 1996 form the foundation for numerical algebraic geometry. They are the indispensable tools for numerically finding and studying positive dimensional (non-isolated) solution sets defined by systems of polynomial equations. Combining the strength of the polyhedral homotopy method and the toric approach for studying algebraic sets, we propose a general framework for efficiently sampling positive dimensional solution sets that can potentially take advantage of the sparsity in the system. The practical usefulness of this approach is demonstrated through an application to the "power-flow equation" from electric engineering.

 

Farewell to Weyl: Condition-based analysis with a Banach norm in numerical algebraic geometry

Josue Tonelli-Cueto1, Felipe Cucker2, Alperen Ergür1
1TU Berlin, 2City University of Hong Kong

Condition-based complexity analyses of numerical algorithms in algebraic geometry seem to rely heavily on inner product norms, such as the Weyl norm. This contrasts with the situation in numerical linear algebra where it is common to use plenty of Banach norm that do not come from an inner product. We show that similar advantages can be obtained in numerical algebraic geometry by showing how such an analysis can be carried out with respect a Banach norm in various settings, obtaining substancial improvements over the known complexity estimates for linear homotopy continuation and grid based methods. This is on going work with Felipe Cucker and Alperen A. Ergür.

 

Singular polynomial eigenvalue problems are not ill-conditioned

Martin Lotz1, Vanni Noferini2
1Warwick University, 2Aalto University

Numerical methods are not supposed to work on ill-posed inputs, and even less so if the function to be computed is discontinuous. Yet, there are examples where arbitrary small perturbations in the input can lead to literally any function value, but where standard numerical algorithms that are oblivious to the special structure of the problem work perfectly fine. Neither the classical nor the stochastic theories of conditioning are adequate to predict the typical forward accuracy in such cases. Motivated by this limitation, and using singular polynomial eigenvalue problems as running example, we define and study weak worst-case and a weak stochastic condition numbers. This new theory can be a more powerful predictor of the accuracy of computations than existing tools, especially when the worst-case and the expected sensitivity of a problem to perturbations of the input are not finite. We illustrate how such condition number can be estimated and used in practice.