Solving degenerate sparse polynomial systems faster (Q1808666): Difference between revisions

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\).