Solving degenerate sparse polynomial systems faster

DOI10.1006/JSCO.1998.0271MaRDI QIDQ1808666zbMATH OpenOpenAlexFDO

Publication date 21 August 2000

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9809071

algorithm Chow form computational complexity degenerate polynomial system solving generalized characteristic polynomial resultant sparse system system of polynomial equations toric geometry twisted Chow form

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 solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20)

Abstract: Consider a system F of n polynomial equations in n unknowns, over an algebraically closed field of arbitrary characteristic. We present a fast method to find a point in every irreducible component of the zero set Z of F. Our techniques allow us to sharpen and lower prior complexity bounds for this problem by fully taking into account the monomial term structure. As a corollary of our development we also obtain new explicit formulae for the exact number of isolated roots of F and the intersection multiplicity of the positive-dimensional part of Z. Finally, we present a combinatorial construction of non-degenerate polynomial systems, with specified monomial term structure and maximally many isolated roots, which may be of independent interest.

Review text

Let \(F\) be a system of \(n\) polynomial equations in \(n\) unknowns over an algebraically closed field of arbitrary characteristic. Under these conditions, the author presents an algorithm for finding a point in every irreducible component of the zero set of \(F\) which is proven to be of computational complexity ``near-heptic in the number of roots of a system closely related to \(F\). The algorithm and its variations rely on two new constructs: the ``twisted Chow form (which is based on the classical \(\mu\)-resultant), and the ``toric perturbation, of which \textit{J. Canny}'s ``generalized characteristic polynomial [J. Symb. Comput. 9, No. 3, 241-250 (1990; Zbl 0704.12004)] is shown to be a special case. The author makes use of many facts and constructions from several of his previous papers, as well as toric geometry, and an extension of J. Canny's constructive version of the primitive element theorem. An example in the paper also requires the product formula for toric resultants developed by \textit{P. Pederson} and \textit{B. Sturmfels} [Math. 2, 214, No. 3, 377-396 (1993; Zbl 0792.13006)]. Both a deterministic and a ``Las Vegas version of the proof of the main theorem are given. Additionally, the author proves several corollaries which, among other things, provide an explicit method of computing field extensions involving the roots of \(F\), and an explicit formula for the exact (as opposed to generic) number of isolated roots of \(F\).

Recommendations

Cites work

Cited in

(36)

This page was built for publication: Solving degenerate sparse polynomial systems faster

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