×

Accelerated solution of multivariate polynomial systems of equations. (English) Zbl 1030.65051

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.

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

Software:

FGb
PDFBibTeX XMLCite
Full Text: DOI