TU Berlin

Fachgebiet Algorithmische AlgebraPublications

Page Content

to Navigation

There is no English translation for this web page.

Search for Publication

Search for publications

All Publications

Condition length and complexity for the solution of polynomial systems
Citation key ABBCS-Condition-Length-And-Complexity-For-The-Solution-Of-Polynomial-Systems
Author Diego Armentano and Carlos Beltrán and Peter Bürgisser and Felipe Cucker and Michael Shub
Pages 1401–1422
Year 2016
ISSN 1615-3383
DOI 10.1007/s10208-016-9309-9
Journal Found. Comput. Math.
Volume 16
Number 6
Month 03
Abstract Smale's 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale 2000). The main progress on Smale's problem is Beltrán-Pardo (2011) and Bürgisser-Cucker (2010). In this paper we will improve on both approaches and we prove an important intermediate result. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltrán-Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Bürgisser-Cucker (2010), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last Theorem is the main result of Bürgisser-Cucker (2010). We give a proof of it relying only on homotopy methods, thus removing the need for the elimination theory methods used in Bürgisser-Cucker (2010). We build on methods developed in Armentano et al. (2015).
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe