| Abstract Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations (2009) | |||||||||||||||
Abstract | |||||||||||||||
| We propose new Las Vegas randomized algorithms for the solution of a multivariate generic or sparse polynomial system of equations. The algorithms use ¢¡¤£¦¥¤§©¨������������� � arithmetic operations to approximate all real roots of the system as well as all roots lying in a � fixed-dimensional box or disc. Here � is an upper bound on the number of all the roots of the system, ¥ is the number of real roots or the roots lying in the box �������� � or disc, is the required upper bound on the output errors, and �¡�£��© � stands for ¢£������©�����© � , be- � ing a constant independent of �. We also yield the bounds for the complexity of counting the numbers of all roots in a fixed box (disc) and all real roots. For a large class of inputs and typically in practical computations, the factor ¥ is much smaller than ���� ¥ £¦���, and most ��� frequently ¥ grows proportionally to ���©���. By ignoring this factor, we yield the � complexity bounds and, respectively. This improves by order of magni-tude the known complexity estimates of order at least �������©��� or � � , which so far are the record ones even for approximating a single root of a system and for each of the cited counting problems, respectively. Our progress relies on proposing several novel techniques. In particular, we exploit the structure of matrices associated to a given polynomial system and relate it to the associated linear operators, dual space of linear forms, and algebraic residues; furthermore, our techniques support the new nontrivial extension of the matrix sign and quadratic inverse power iterations to the case of multivariate polynomial systems, where we emulate the recursive splitting of a univariate polynomial into factors of smaller degree. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||