Session S34 - Symbolic and Numerical Computation with Polynomials

Friday, July 16, 12:00 ~ 12:30 UTC-3

Rigid homotopy and structured polynomial systems

Felipe Cucker

City University of Hong Kong, Hong Kong   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

This talk deals with the average complexity of solving structured polynomial systems that are characterized by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity $L$. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with $n$ equations of degree at most $\delta$ in $n$ variables with only poly($n,\delta$)$L$ operations with high probability. This exceeds the expectations implicit in Smale’s 17th problem.

Joint work with Peter Bürgisser (Technische Universität Berlin) and Pierre Lairez (Inria).

View abstract PDF