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 4: Numerical methods for structured polynomial system solving
Time:
Friday, 12/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)

 

Low-degree approximation of real singularities

Antonio Lerario1, Paul Breiding2, Daouda Niang Diatta3, Hanieh Keneshlou2
1SISSA, 2MPI-MSI Leipzig, 3Université Assane SECK de Ziguinchor

In this talk I will discuss some recent results that allow to approximate a real singularity given by polynomial equations of degree d (e.g. the zero set of a polynomial, or the number of its critical points of a given Morse index) with a singularity which is diffeomorphic to the original one, but it is given by polynomials of degree O(d^{1/2} log d). The approximation procedure is constructive (in the sense that one can read the approximating polynomial from a linear projection of the given one) and quantitative (in the sense that the approximating procedure will hold for a subset of the space of polynomials with measure increasing very quickly to full measure as the degree goes to infinity).

I will also discuss the potential of this procedure for improving the average complexity of some algorithms.

This is based on a combination of joint works with P. Breiding, D. N. Diatta and H. Keneshlou.

 

Computing Verified Real Solutions of Polynomials Systems via Low-rank Moment Matrix Completion

Lihong Zhi, Yue Ma, Zhengfeng Yang
Academia Sinica

We propose a new algorithm for computing verified real solutions of polynomial systems with equalities and inequalities. We recast Lasserre's hierarchy of moment relaxations for computing real solutions of polynomial systems into finding symmetric positive semidefinite matrices of minimum nuclear norm subject to linear equality constraints, and then apply fixed point iterations together with Barzilai-Borwein technique for solving a sequence of moment matrix completion problems. Although the method based on function values and gradient evaluations cannot yield as high accuracy as interior point methods, much larger problems can be solved since no second-order information needs to be computed and stored. Finally, we apply interval arithmetic to verify the existence of real solutions of polynomial systems near to the computed approximate real solutions. The algorithm has been implemented in Matlab and is available at http://159.226.47.210:8080/verifyrealroots/tryOnline.jsp
It is a joint work with Zhengfeng Yang, Yue Ma, Yijun Zhu.

 

Computing the Canonical Polyadic Decomposition of Tensors with Damped Gauss-Newton Method

Felipe Diniz
Universidade Federal do Rio de Janeiro

Low rank approximation of tensors can be formulated as a structured nonlinear minimization problem. Exploiting this structure allows to improve the speed and accuracy of a damped Gauss-Newton method. A preliminary implementation of this method performed better than availble published software.

 

A most outrageous action

Gregorio Malajovich
Universidade Federal do Rio de Janeiro

The cost of homotopy algorithms for sparse polynomial systems can be bounded above by an integral of a condition length (Found Comput Math (2019) 19: 1. https://doi.org/10.1007/s10208-018-9375-2). This integral depends on a toric condition number and on a distortion invariant nu. In this talk, I will show how a certain renormalization operator induces a group action on the solution variety. This action will be used to produce a renormalized algorithm, where the distortion nu is constant. Then it becomes possible to integrate the square of the condition number for normal systems. This method provides upper bounds for the expected cost of sparse homotopy.