Systems with parameters, or efficiently solving systems of polynomial equations: 33 years later. I
type: Item
instance of: scholarly article
title: Systems with parameters, or efficiently solving systems of polynomial equations: 33 years later. I
zbMATH Open document ID: 1405.13050
published in: Journal of Mathematical Sciences (New York)
publication date: 2018-08-16T00:00:00Z
review text: Consider a polynomial system in the variables \(X_0,\dots,X_n\) whose coefficients are unknown, unmeasurable, or otherwise unspecified. This situation is very frequent in applied algebra. To model it, one replaces the coefficients by indeterminate ``parameters'' \(a_1,\dots,a_\nu\) and studies the dependency of the solutions of the polynomial system on the parameter values. One can show that parameter space subdivides into strata (also defined by polynomial equations) where the formulas for the solutions of the original systems only depend on the stratum. The present paper discusses this theory and then focusses on the complexity of the resulting decompositions of parameter space. The main results are a sub-exponential bound on the degree of the strata (as quasi-projective varieties) and another sub-exponential bound on the number of strata. The paper is the first part of a series of papers by the same author on this fundamental problem, its history, and its solution.
reviewed by: Thomas Kahle
Mathematics Subject Classification ID: 13P15
Mathematics Subject Classification ID: 13-03
Mathematics Subject Classification ID: 01A60
Mathematics Subject Classification ID: 01A61
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 14Q20
zbMATH DE Number: 6919708
zbMATH Keywords: parametric polynomial system
zbMATH Keywords: resultant
zbMATH Keywords: discriminant
zbMATH Keywords: complexity
author: A. L. Chistov
MaRDI profile type: Publication
full work available at URL: s10958-018-3868-z
OpenAlex ID: W2803229928
cites work: Complexity of solving parametric polynomial systems
cites work: Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time
cites work: A bound for the degree of a system of equations determining the variety of reducible polynomials
cites work: Computations with parameters: a theoretical background
cites work: Efficient absolute factorization of polynomials with parametric coefficients
cites work: Q3775643
cites work: Vandermonde matrices, NP-completeness and transversal subspaces
cites work: Solving parametric polynomial systems
cites work: Résolution des systèmes d'équations algébriques
Wikidata QID: Q129753375
DOI: 10.1007/S10958-018-3868-Z
description: scientific article; zbMATH DE number 6919708