Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleControlled Iterative Methods for Solving Polynomial Systems
Author(s) Didier Bondyfalat, Bernard Mourrain, Victor Y. Pan
TypeArticle in Conference Proceedings
AbstractFor a system of polynomial equations, we seek its specified root, maximizing or minimizing the absolute value of a fixed polynomial over all roots of the system. The latter requirement to a root, complicating the already difficult classical problem, is motivated by several practical applications. We first reduce the solution to the computation of the eigenvector of an associated matrix. Our novel treatment of this rather customary stage enables us to unify several known approaches and to simplify substantially the solution of an overconstrained polynomial system having only a simple root or a few roots. Likewise, when the reduction of a general polynomial system to an eigenproblem relies on the Gröbner basis techniques, we also obtain substantial simplification. Then we elaborate application of the power method and the (shifted) inverse power method to the solution of the resulting eigenproblem. Our elaboration is not straight-forward since we achieve the computation preserving the sparsity and the structure of the associated matrix involved. This enables the decrease of the arithmetic cost by roughly factor N , denoting the dimension of the associated resultant matrix.
Furthermore, our experiments show that our computations can be performed numerically, with single or double precision arithmetic, and the iteration converged to the specified root quite fast.
Translation No
Refereed No