A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average timeReportar como inadecuado




A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Institut für Mathematik Berlin

Abstract : We describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum-Shub-Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale-s 17th problem. The main idea is to make use of the randomness contained in the input itself.

Keywords : Polynomial system homotopy continuation complexity Smale-s 17th problem derandomization





Autor: Pierre Lairez -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados