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


TitleComputing of a Specified Root of a Polynomial System of Equations Using Eigenvectors
Author(s) Didier Bondyfalat, Bernard Mourrain, Victor Y. Pan
TypeArticle in Journal
AbstractWe propose new techniques and algorithms for the solution of a polynomial system of equations by matrix methods. For such a system, we seek its specified root, at which a fixed polynomial takes its maximum or minimum absolute value on the set of roots. We first reduce the solution to the computation of the eigenvector of an associated matrix. Our novel treatment enables us to unify several known approaches and to simplify substantially the solution, in particular in the case of an overconstrained polynomial system having only a simple root or a few roots. We reduce the solution of a polynomial system to the eigenvector problem for a matrix that we dene implicitly, as a Schur complement in a sparse and structured matrix, and then we elaborate appropriate modification of the known efficient methods for the sparse eigenvector computation.

This enables us to accelerate the known algorithm for the solution of a polynomial system. Our acceleration is by roughly factor D, denoting the overall number of the roots. Furthermore, our experiments show that our computations can be performed numerically, without the usual increase of the computational precision, and the iteration converged to the specified root quite fast.
Keywordspolynomial systems of equations, resultants, matrix eigenproblem, sparse matrices, overconstrained polynomial systems, parameterized polynomial systems, Gröbner basis
URL dx.doi.org/10.1016/S0024-3795(00)00190-7
JournalLinear Algebra and its Applications
Translation No
Refereed No