Mourrain, B.; Pan, V. Y.; Ruatta, O. Accelerated solution of multivariate polynomial systems of equations. (English) Zbl 1030.65051 SIAM J. Comput. 32, No. 2, 435-454 (2003). The authors propose new randomized algorithms of Las Vegas type, for solving a system of polynomial equations. Such problems have important applications in robotics,computer modeling, and graphics,molecular biology and computational algebraic geometry. The approach used in this paper is reduction of the solution of a multivariate polynomial system to a matrix eigenproblem. The authors exploit the structure of matrices associated to the system and related it to the associated linear operators, dual space of linear forms, and normal forms of polynomials in the quotient algebra of residue polynomials. Many results on quasi-Toeplitz and quasi-Hankel matrices and on linear forms are presented, in order to describe the iterative process for root approximation and for the number of the roots. The number of arithmetic operations are estimated. No numerical example. Reviewer: Iulian Coroian (Baia Mare) Cited in 3 Documents MSC: 65H10 Numerical computation of solutions to systems of equations 12Y05 Computational aspects of field theory and polynomials (MSC2010) 30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) 68W20 Randomized algorithms 26C10 Real polynomials: location of zeros 65F15 Numerical computation of eigenvalues and eigenvectors of matrices Keywords:multivariate polynomials; system of polynomial equations; quotient algebra; dual space; quasi-Toeplitz matrices; quasi-Hankel matrices; matrix sign iteration; quadratic power iteration; randomized algorithm; matrix eigenproblem; root approximation Software:FGb PDFBibTeX XMLCite \textit{B. Mourrain} et al., SIAM J. Comput. 32, No. 2, 435--454 (2003; Zbl 1030.65051) Full Text: DOI