Open Collections

Complexity of Polynomial System Solving

Banff International Research Station for Mathematical Innovation and Discovery

Analysis of condition number for random matrices originated in the works of von Neumann and Turing on complexity of linear system solving. For the case of non-linear algebraic equations (i.e. polynomials), there are two decoupling facts: feasibility of a system of equations over the complex numbers is NP-Hard, and a generic system of polynomials always has the same number of roots (i.e. Bezout number or BKK bound). These facts led to the search for algorithms that solves a generic polynomial system fast, and a notion of condition number arose naturally. The analysis of condition number for random polynomial systems thus became the central ingredient for understanding complexity of polynomial system solving. We present a rather quick survey on condition number analysis over complex numbers (i.e., a survey on the solution of Smale's 17th problem), then pass to the field of real numbers. We hope to finish by presenting our results on condition number analysis of random real polynomial systems. This is joint work with J. Maurice Rojas and Grigoris Paouris.

Mathematics; Functional analysis; Convex and discrete geometry

video/mp4

Author affiliation: Technische Universitat Berlin

2018-09-25

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/67250

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/