Accelerated Solution of Multivariate Polynomial Systems of Equations

dual space matrix eigenproblem matrix sign iteration multivariate polynomials quadratic power iteration quasi-Hankel matrices quasi-Toeplitz matrices quotient algebra randomized algorithm root approximation system of polynomial equations

Mathematics Subject Classification ID

Real polynomials: location of zeros (26C10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical computation of solutions to systems of equations (65H10) Randomized algorithms (68W20)

Review text

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.

Recommendations

Cited in

(11)

Describes a project that uses

Uses Software

FGb

This page was built for publication: Accelerated Solution of Multivariate Polynomial Systems of Equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4706200)