caa a22 4500 445331496 CHVBK 20180317142739.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s10208-010-9078-9 doi (NATIONALLICENCE)springer-10.1007/s10208-010-9078-9 Fast Linear Homotopy to Find Approximate Zeros ofPolynomial Systems [Elektronische Daten] [Carlos Beltrán, Luis Pardo] We prove a new complexity bound, polynomial on the average, for the problem of finding an approximate zero of systems of polynomial equations. The average number of Newton steps required by this method is almost linear in the size of the input (dense encoding). We show that the method can also be used to approximate several or all the solutions of non-degenerate systems, and prove that this last task can be done in running time which is linear in the Bézout number of the system and polynomial in the size of the input, on the average. SFoCM, 2010 Approximate zero nationallicence Homotopy method nationallicence Average complexity nationallicence Beltrán Carlos Depto. de Matemáticas, Estadística y Computación, Fac. de Ciencias, Avda. Los Castros s/n, 39005, Santander, Spain aut Pardo Luis Depto. de Matemáticas, Estadística y Computación, Fac. de Ciencias, Avda. Los Castros s/n, 39005, Santander, Spain aut Foundations of Computational Mathematics Springer-Verlag 11/1(2011-02-01), 95-129 1615-3375 11:1<95 2011 11 10208 https://doi.org/10.1007/s10208-010-9078-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10208-010-9078-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Beltrán Carlos Depto. de Matemáticas, Estadística y Computación, Fac. de Ciencias, Avda. Los Castros s/n, 39005, Santander, Spain aut NATIONALLICENCE 700 1- Pardo Luis Depto. de Matemáticas, Estadística y Computación, Fac. de Ciencias, Avda. Los Castros s/n, 39005, Santander, Spain aut NATIONALLICENCE 773 0- Foundations of Computational Mathematics Springer-Verlag 11/1(2011-02-01), 95-129 1615-3375 11:1<95 2011 11 10208 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer