RECORD
Complexity of Resolution of Parametric Systems of Polynomial Equations and Inequations
Symbolic Computation · Submitted 7 Jun 2006
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Moreover, we prove that the degree of the computed minimal discriminant variety is bounded by $D:=(n+r)d^{(n+1)}$ and that the complexity of our method is $\sigma^{\mathcal{O}(1)} D^{\mathcal{O}(n+s)}$ bit-operations on a deterministic Turing machine.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Consider a system of n polynomial equations and r polynomial inequations in n indeterminates of degree bounded by d with coefficients in a polynomial ring of s parameters with rational coefficients of bit-size at most $\sigma$. From the real viewpoint, solving such a system often means describing some semi-algebraic sets in the parameter space over which the number of real solutions of the considered parametric system is constant. Following the works of Lazard and Rouillier, this can be done by the computation of a discriminant variety. In this report we focus on the case where for a generic specialization of the parameters the system of equations generates a radical zero-dimensional ideal, which is usual in the applications. In this case, we provide a deterministic method computing the minimal discriminant variety reducing the problem to a problem of elimination. Moreover, we prove that the degree of the computed minimal discriminant variety is bounded by $D:=(n+r)d^{(n+1)}$ and that the complexity of our method is $\sigma^{\mathcal{O}(1)} D^{\mathcal{O}(n+s)}$ bit-operations on a deterministic Turing machine.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Consider a system of n polynomial equations and r polynomial inequations in n indeterminates of degree bounded by d with coefficients in a polynomial ring of s parameters with rational coefficients of bit-size at most $\sigma$. | background 1.00 | 0.06 | 0.02 | unclear 0.51 |
| s1 | From the real viewpoint, solving such a system often means describing some semi-algebraic sets in the parameter space over which the number of real solutions of the considered parametric system is constant. | background 0.98 | 0.05 | 0.02 | hedged possibility 0.80 |
| s2 | Following the works of Lazard and Rouillier, this can be done by the computation of a discriminant variety. | background 1.00 | 0.04 | 0.03 | asserted 0.97 |
| s3 | In this report we focus on the case where for a generic specialization of the parameters the system of equations generates a radical zero-dimensional ideal, which is usual in the applications. | limitation 0.52 | 0.17 | 0.04 | asserted 0.90 |
| s4 | In this case, we provide a deterministic method computing the minimal discriminant variety reducing the problem to a problem of elimination. | contribution 0.79 | 0.94 | 0.36 | asserted 1.00 |
| s5 | Moreover, we prove that the degree of the computed minimal discriminant variety is bounded by $D:=(n+r)d^{(n+1)}$ and that the complexity of our method is $\sigma^{\mathcal{O}(1)} D^{\mathcal{O}(n+s)}$ bit-operations on a deterministic Turing machine. | result 0.96 | 0.94 | 0.83 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Consider a system of n polynomial equations and r polynomial inequations in n indeterminates of degree bounded by d with coefficients in a polynomial ring of s parameters with rational coefficients of bit-size at most $\sigma$. From the real viewpoint, solving such a system often means describing some semi-algebraic sets in the parameter space over which the number of real solutions of the considered parametric system is constant. Following the works of Lazard and Rouillier, this can be done by the computation of a discriminant variety. In this report we focus on the case where for a generic specialization of the parameters the system of equations generates a radical zero-dimensional ideal, which is usual in the applications. In this case, we provide a deterministic method computing the minimal discriminant variety reducing the problem to a problem of elimination. Moreover, we prove that the degree of the computed minimal discriminant variety is bounded by $D:=(n+r)d^{(n+1)}$ and that the complexity of our method is $\sigma^{\mathcal{O}(1)} D^{\mathcal{O}(n+s)}$ bit-operations on a deterministic Turing machine.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.