Computing isolated roots of sparse polynomial systems in affine space (Q410703)

The subject of this paper concerns solving -- numerically and symbolically -- polynomial equation systems over \(\mathbb{C}^*\). Because actual efficient algorithms are based on the polyhedral deformations proposed by \textit{T. Gao, T. Y. Li} and \textit{X. Wang} [J. Symb. Comput. 28, No. 1--2, 187--211 (1999; Zbl 0944.65055)] (which preserve the monomial structure of the system), it results that the number of variants obtained by deformation equals the expected number of solutions. For sparse systems that means algorithms of lower complexity. The main result of the paper is focused in the theorem: Let \(f_1,\dots,f_n\) be polynomials in \(\mathbb{Q}[X_1,\dots,X_n]\). There exists a probabilistic algorithm which computes a finite set of points containing the isolated common zeros of \(f_1,\dots,f_n\) in \(\mathbb{C}^n\) within a complexity which is polynomial in the size of the combinatorial structure of the system supports. The algorithm -- detailed, analyzed by its complexity and exemplified -- is called \textit{AffineSolve} and it improves the algorithm proposed by \textit{G. Jeronimo, G. Matera, P. Solernó} and \textit{A. Waissbein} [Found. Comput. Math. 9, No. 1, 1--50 (2009; Zbl 1167.14039)]. Although it is not mentioned in the paper, this result can be used in several other domains which are based on solving polynomial equation systems, like coding theory or dynamical systems.