Solving degenerate sparse polynomial systems faster (Q1808666)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Solving degenerate sparse polynomial systems faster |
scientific article |
Statements
Solving degenerate sparse polynomial systems faster (English)
0 references
21 August 2000
0 references
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\).
0 references
degenerate polynomial system solving
0 references
resultant
0 references
Chow form
0 references
toric geometry
0 references
sparse system
0 references
system of polynomial equations
0 references
algorithm
0 references
computational complexity
0 references
twisted Chow form
0 references
generalized characteristic polynomial
0 references
0 references
0 references
0 references