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
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references