Louis Gaillard

Mohab Safey

El Din

Solving parameter-dependent semi-algebraic systems

Keywords: CCS CONCEPTS, Computing methodologies → Algebraic algorithms, • Theory Polynomial system solving, Real algebraic geometry, Gröbner bases

We consider systems of polynomial equations and inequalities in [𝒙] where 𝒙 = (𝑥 1 , . . . , 𝑥 𝑛 ) and 𝒚 = (𝑦 1 , . . . , 𝑦 𝑡 ). The 𝒚 indeterminates are considered as parameters and we assume that when specialising them generically, the set of common complex solutions, to the obtained equations, is finite.

We consider the problem of real root classification for such parameter-dependent problems, i.e. identifying the possible number of real solutions depending on the values of the parameters and computing a description of the regions of the space of parameters over which the number of real roots remains invariant.

We design an algorithm for solving this problem. The formulas it outputs enjoy a determinantal structure. Under genericity assumptions, we show that its arithmetic complexity is polynomial in both the maximum degree 𝑑 and the number 𝑠 of the input inequalities and exponential in 𝑛𝑡 + 𝑡 2 . The output formulas consist of polynomials of degree bounded by (2𝑠 + 𝑛)𝑑 𝑛+1 . This is the first algorithm with such a singly exponential complexity. We report on practical experiments showing that a first implementation of this algorithm can tackle examples which were previously out of reach.

Assumption A. There exists a nonempty Zariski open subset O ⊆ C 𝑡 such that for all 𝜂 ∈ O, 𝜋 -1 (𝜂) ∩ V is nonempty and finite.

In other words, for a generic specialization point 𝜂, the specialized system 𝒇 (𝜂, •) = 0 is zero-dimensional. Besides, can assume that the cardinality of 𝜋 -1 (𝜂) ∩ V remains invariant when 𝜂 ranges over O. This is not the case for the set of real solutions.

We consider the (basic) semi-algebraic set S ⊆ R 𝑡 +𝑛 defined by

𝑓 1 = • • • = 𝑓 𝑝 = 0, 𝑔 1 > 0, . . . , 𝑔 𝑠 > 0. ( 1
)
The goal of this paper is to provide an efficient algorithm for solving the real root classification problem over S as stated below.

Problem 1 (Real solution classification). On input (𝒇, 𝒈) with 𝒇 satisfying Assumption A, compute (Φ 𝑖 , 𝜂 𝑖 , 𝑟 𝑖 ) 1≤𝑖 ≤ℓ such that, for 1 ≤ 𝑖 ≤ ℓ, Φ 𝑖 is a semi-algebraic formula in Q[𝒚] defining the semi-algebraic set T 𝑖 ⊆ R 𝑡 , with 𝜂 𝑖 ∈ T 𝑖 and 𝑟 𝑖 ≥ 0 such that • for all 𝜂 ∈ T 𝑖 , the number of points in S ∩ 𝜋 -1 (𝜂) is 𝑟 𝑖 ,

• ℓ 𝑖=1 T 𝑖 is dense in R 𝑡 . Such a sequence (Φ 𝑖 , 𝜂 𝑖 , 𝑟 𝑖 ) 1≤𝑖 ≤ℓ is said to be a solution to Problem 1 which arises in many applications (see e.g. [START_REF] Bonnard | Determinantal sets, singularities and application to optimal control in medical imagery[END_REF][START_REF] Corvez | Using computer algebra tools to classify serial manipulators[END_REF][START_REF] Faugère | Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities[END_REF][START_REF] Le | Computing totally real hyperplane sections and linear series on algebraic curves[END_REF][START_REF] Puente | Absolute concentration robustness: Algebra and geometry[END_REF][START_REF] Yang | Equi-cevaline points on triangles[END_REF]).

Prior works. First, as noticed in [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF], the cylindrical algebraic decomposition (CAD) algorithm due to Collins [START_REF] Collins | Quantifier elimination for real closed fields by cylindrical algebraic decomposition[END_REF] could be used to solve Problem 1. However, its doubly exponential complexity [START_REF] Brown | The complexity of quantifier elimination and cylindrical algebraic decomposition[END_REF][START_REF] Davenport | Real quantifier elimination is doubly exponential[END_REF] in the total number of variables makes it difficult to use.

More efficient approaches have been devised by using polynomial elimination methods combined with real algebraic geometry. They consist in computing some nonzero polynomials, say ℎ 1 , . . . , ℎ 𝑘 in Q[𝒚], such that the number of points in S ∩ 𝜋 -1 (𝜂) remains invariant when 𝜂 ranges over some connected component of the semi-algebraic set defined by ℎ 1 ≠ 0, . . . , ℎ 𝑘 ≠ 0. Such polynomials are called border polynomials, in the context of methods using the theory of regular chains (see e.g. [START_REF] Liang | The complete root classification of a parametric polynomial on an interval[END_REF][START_REF] Yang | A complete algorithm for automated discovering of a class of inequality-type theorems[END_REF][START_REF] Yang | Real solution classification for parametric semi-algebraic systems[END_REF]), or discriminant polynomials in the context of methods using algebraic elimination algorithms based on Gröbner bases (see e.g. [START_REF] Lazard | Solving parametric polynomial systems[END_REF][START_REF] Moroz | Complexity of the resolution of parametric systems of polynomial equations and inequations[END_REF]) when the ideal generated by 𝒇 is assumed to be radical and equidimensional. When 𝑑 is the maximum degree of the input polynomials in 𝒇 and 𝒈, these ℎ 𝑖 's can be proven to have degree bounded by 𝑛(𝑑 -1)𝑑 𝑛 .

Once these polynomials are computed one then needs to describe the connected components of the set where none of them vanish. When this is done through the CAD algorithm, the cost of this is doubly exponential in 𝑡, the number of parameters. Using more advanced algorithms for computing semi-algebraic descriptions of connected components of semi-algebraic sets (see [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Chap. 16]) through parametric roadmaps, one can obtain a complexity using (𝑛(𝑑 -1)𝑑 𝑛 ) 𝑂 (𝑡 4 ) arithmetic operations in Q and which would output polynomials of degree lying in (𝑛(𝑑 -1)𝑑 𝑛 ) 𝑂 (𝑡 3 ) .

All in all, just a few is known about the complexity of these methods and it has been an open problem to obtain better complexity estimates or degree bounds on the polynomials of the output formulas required to solve Problem 1.

A first step towards this goal comes from the analysis of the algorithm in [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]. This algorithm is restricted to the case where the ideal generated by 𝒇 is radical and the sequence 𝒈 is empty. Under genericity assumptions on the input 𝒇 , this algorithm runs in time quasi-linear in 𝑛 𝑂 (𝑡 ) 𝑑 3𝑛𝑡 +𝑂 (𝑛+𝑡 ) and the degrees of the polynomials in the output formulas lie in 𝑛(𝑑 -1)𝑑 𝑛 . This is achieved using classical real root counting methods (through Hermite's quadratic forms) but combined in an innovative way with the theory of Gröbner bases. Additionally, the output formulas enjoy a nice determinantal encoding which allows one to evaluate them easily. This is at the foundations of new efficient algorithms for one-block quantifier elimination [START_REF] Le | Faster one block quantifier elimination for regular polynomial systems of equations[END_REF]. We also note that these techniques can lead to a new geometric approach for Cylindrical Algebraic Decomposition [START_REF] Chen | Geometric fiber classification of morphisms and a geometric approach to cylindrical algebraic decomposition[END_REF].

Still, several open problems remain. One is to obtain similar complexity bounds which do not depend on the aforementioned genericity assumptions. Another open problem is to extend such an approach to real root classification problems involving inequalities, hence extending significantly the range of applications which could be reached. In this paper, we tackle this second open problem.

Contributions. We present an algorithm solving Problem 1 revisiting the ideas in [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF] to handle the case of systems of equations and inequalities. It uses a real root counting machinery based on Hermite's quadratic form [START_REF] Hermite | Extrait d'une lettre de Mr. Ch. Hermite de Paris à Mr. Borchardt de Berlin sur le nombre des racines d'une équation algébrique comprises entre des limites données[END_REF] in some appropriate basis. In order to take the polynomial inequalities defined by 𝒈 into account, this algorithm relies on a method originated in [START_REF] Ben-Or | The complexity of elementary algebra and geometry[END_REF] using the so-called Tarskiquery [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Sec. 10.3] for determining the sign conditions realized by a family of polynomials on a finite set of points. These methods are devised to count the number of real solutions to some system of polynomial equations (with coefficients in R), with finitely many complex roots, which do satisfy some extra polynomial inequalities.

Our contribution combines these methods with Gröbner bases computations in our context where the coefficients of our input polynomials depend on the parameters 𝒚. A second key ingredient, used to control the number of calls to Tarski queries, in a way that is similar to the one used in [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Chap. 10], is the use of efficient routines for computing sample points per connected components in semi-algebraic sets lying in the space of parameters [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]Sec. 3]. Hence, the semi-algebraic constraints depending on 𝒚 actually encode some constraints on the signature of parameter-dependent Hermite matrices and thus, enjoy a nice determinantal structure.

Note that, by contrast with [START_REF] Lazard | Solving parametric polynomial systems[END_REF], this algorithm does not assume that the ideal generated by 𝒇 is radical and equidimensional.

Since this algorithm makes use of Gröbner bases computations, extra genericity assumptions are needed to control its complexity. Hence, we assume that the homogeneous component of the 𝑓 𝑖 's of highest degree forms a regular sequence, which we abbreviate by the saying that 𝒇 is a regular sequence. In addition, letting G be a reduced Gröbner basis for the ideal generated by 𝒇 and the graded reverse lexicographical ordering, we assume the following. Assumption B. For any 𝑝 ∈ G , we have deg 𝑝 = deg 𝒙 𝑝.

These assumptions are known to be satisfied generically (see [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]Prop. 20]) and to enable nicer complexity bounds on Gröbner bases. Our main complexity result is the following one. We use the notation 𝑔 = O (𝑓 ) meaning that 𝑔 = O (𝑓 log 𝜅 (𝑓 )) for some 𝜅 > 0.

O 𝑡 + 𝔇 𝑡 𝑠 𝑡 𝑡 +1 2 3𝑡 2 +𝑛𝑡 +8𝑡 +𝑛 𝑠 𝑡 +2 (2𝑠 + 𝑛) 2𝑡 +1 𝑑 𝑡 2 +4𝑛𝑡 +3(𝑛+𝑡 )+1
arithmetic operations in Q and outputs at most (4𝑑 𝑛 𝑠𝑟𝔇) 𝑡 formulas that consists of O (𝑑 𝑛 𝑠𝑟 ) polynomials of degree at most 𝔇.

We report on practical experiments performed with a first implementation of this algorithm. That implementation makes no use of the genericity assumptions made to enable a complexity analysis, it only uses Assumption A. Benchmark tests include random dense polynomial systems (hence, these are presumably generic). Practical performances which are achieved show that this algorithm outperforms the state-of-the-art software for solving Problem 1. We also fully solve an application related to the Perspective-Three-Point problem for which computing semi-algebraic formulas for the real root classification was an open problem.

Plan of the paper. Section 2 recalls the basics on Hermite's quadratic forms, using materials mostly from [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Chap. 4]. Section 3 generalizes constructions and results on parametric Hermite matrices from [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF] to the case where inequalities are involved. Section 4 describes the algorithm on which Theorem 1.1 relies and proves the complexity statements. Section 5 reports on practical experiments.

HERMITE'S QUADRATIC FORM

We recall some basic definitions and properties on Hermite's quadratic forms. For more details, we refer to [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Chap. 4].

Definition

Let K be a field of characteristic 0 and 𝒇 = (𝑓 1 , . . . , 𝑓 𝑝 ) ⊂ K[𝒙] be generating a zero-dimensional ideal, denoted by ⟨𝒇 ⟩ K . The quotient ring A K K[𝒙]/⟨𝒇 ⟩ K is a finite dimensional K-vector space [2, Theorem 4.85] of dimension 𝛿. A monomial basis 𝐵 = (𝑏 1 , . . . , 𝑏 𝛿 ) of A K can be derived from a Gröbner basis 𝐺 of ⟨𝒇 ⟩ K with respect to (w.r.t.) an admissible monomial ordering ≻ over K[𝒙]: it is the set of monomials that are not divisible by any leading monomial of elements in 𝐺. For 𝑞 ∈ K[𝒙], we denote by 𝑞 the class of 𝑞 in A K and by 𝐿 𝑞 :

𝑝 ∈ A K ↦ → 𝑝 • 𝑞 ∈ A K the multiplication by 𝑞 in A K .
Definition 2.1 (Hermite's qadratic form). For 𝑔 ∈ A K , Hermite's bilinear form herm(𝒇, 𝑔) is defined by

herm(𝒇, 𝑔) : A K × A K → K (𝑝, 𝑞) ↦ → Tr(𝐿 𝑔𝑝𝑞 ),
where Tr denotes the trace. The corresponding quadratic form 𝑝 ↦ → Tr(𝐿 𝑔𝑝 2 ) is called Hermite's quadratic form Herm(𝒇, 𝑔). The Hermite matrix associated to (𝒇, 𝑔) w.r.t. the basis 𝐵 is the matrix H = (ℎ 𝑖,𝑗 ) 1≤𝑖,𝑗 ≤𝛿 ∈ K 𝛿 ×𝛿 of Herm(𝒇, 𝑔) w.r.t. 𝐵, i.e. ℎ 𝑖,𝑗 = Tr(𝐿 𝑔𝑏 𝑖 𝑏 𝑗 ).

For a matrix H , H 𝑖,𝑗 is its element at the 𝑖-th row and 𝑗-th column.

sign(𝑔(𝑥)) = ♯{𝑥 ∈ 𝑍 | 𝑔(𝑥) > 0} -♯{𝑥 ∈ 𝑍 | 𝑔(𝑥) < 0}.
When 𝑍 is the finite set of real roots of a zero-dimensional system 𝒇 = 0, we denote it by TaQ(𝑔, 𝒇 ).

We denote the signature of a real quadratic form 𝑞 by Sign(𝑞). Hence, Tarski-queries are given by signatures of Hermite matrices. From TaQ(1, 𝒇 ) TaQ(𝑔, 𝒇 ) and TaQ(𝑔 2 , 𝒇 ), one can compute the number of real roots of 𝒇 that satisfy a given sign condition for 𝑔. We define 𝑐 (𝑔 ♦ 0) for ♦ ∈ {<, =, >} as ♯{𝑥 | 𝒇 (𝑥) = 0 ∧𝑔(𝑥) ♦ 0}. We have the following invertible system

      1 1 1 0 1 -1 0 1 1       •       𝑐 (𝑔 = 0) 𝑐 (𝑔 > 0) 𝑐 (𝑔 < 0)       =       TaQ(1, 𝒇 ) TaQ(𝑔, 𝒇 ) TaQ(𝑔 2 , 𝒇 )       . ( 2
)
Theorem 2.5 ([15, Thm. 1.9]). Let 𝑀 be a symmetric matrix in R 𝑚×𝑚 and for 0 ≤ 𝑖 ≤ 𝑚 let 𝑀 𝑖 denote its 𝑖-th leading principal minor. We assume that 𝑀 𝑖 ≠ 0 for all 0 ≤ 𝑖 ≤ 𝑚. Then we have

Sign(𝑀) = 𝑚 -2 Var(𝑀 0 , 𝑀 1 , . . . , 𝑀 𝑚 ),
where Var stands for the number of sign variations in the sequence.

PARAMETRIC HERMITE MATRICES 3.1 Basic construction and properties

Let 𝒇 = (𝑓 1 , . . . , 𝑓 𝑝 ) ⊂ Q[𝒚] [𝒙] such that 𝒇 satisfies Assumption A and 𝑔 ∈ Q[𝒚] [𝒙].
We take as a base field K the rational function field 𝐵 of A K is fixed). We start by making explicit how these can be computed and next prove some nice specialization properties of these matrices. We follow and extend the approach in [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF].

Q(𝒚).
Gröbner basis and monomial basis. We denote grevlex(𝒙) for the graded reverse lexicographical ordering (grevlex) among the variables 𝒙 (with 𝑥 1 ≻ • • • ≻ 𝑥 𝑛 ) and grevlex(𝒙) ≻ grevlex(𝒚) (with 𝑦 1 ≻ • • • ≻ 𝑦 𝑡 ) for the elimination ordering. For 𝑝 ∈ C(𝒚) [𝒙], lc 𝒙 (𝑝) (resp. lm 𝒙 (𝑝)) denotes the leading coefficient (resp. monomial) of 𝑝 for the ordering grevlex(𝒙). We let G be the reduced Gröbner basis of ⟨𝒇 ⟩ ⊂ Q[𝒚] [𝒙] w.r.t. this elimination ordering. By [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]Lem. 6], G is also a Gröbner basis of ⟨𝒇 ⟩ K w.r.t. grevlex(𝒙). Hence the set B of all monomials in 𝒙 that are not reducible by the leading monomials of G (w.r.t. grevlex(𝒙)) is finite since ⟨𝒇 ⟩ K is zero-dimensional. It forms a basis of A K . We define H 𝑔 as the parametric Hermite matrix associated to (𝒇, 𝑔) w.r.t. the basis B.

Algorithm for computing Hermite matrices. In [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF], an algorithm is described to compute the parametric Hermite matrix H 1 . Actually this does not only compute the matrix H 1 but also the family of matrices (𝑀 𝑏 ) 𝑏 ∈B such that 𝑀 𝑏 is the matrix of the multiplication map 𝐿 𝑏 w.r.t. the basis B. We explain now how we can compute H 𝑔 from H 1 . We first compute 𝑔 the normal form of 𝑔 by the Gröbner basis G (w.r.t. grevlex(𝒙) and K as a base field), namely

𝑔 = 𝑏 ∈B 𝑐 𝑏 𝑏, with 𝑐 𝑏 ∈ Q(𝒚). Then we have 𝑀 𝑔 = 𝑏 ∈B 𝑐 𝑏 𝑀 𝑏 ,
where 𝑀 𝑔 denotes the matrix of the multiplication by 𝑔 in the basis B. By Proposition 2.2, we obtain

H 𝑔 = H 1 • 𝑀 𝑔 .
Specialization properties. We prove now specialization properties of these parametric Hermite matrices. The Gröbner basis G is a subset of Moreover, the specialization property for the Gröbner basis G implies that when dividing some polynomial w.r.t. G , none of the denominators which appear vanish at 𝜂 ∈ C 𝑡 . Hence, given ℎ ∈

Q[𝒚] [𝒙], thus for all 𝑝 ∈ G , lc 𝒙 (𝑝) ∈ Q[𝒚]. We denote by 𝑉 (lc 𝒙 (𝑝)) its vanishing set in C 𝑡 . We consider the following algebraic set W ∞ ⊆ C 𝑡 : W ∞ 𝑝 ∈G 𝑉 (lc 𝒙 (𝑝)). (3)

Q[𝒚]

[𝒙] and its normal form ℎ w.r.t. G (computed with K as a base field and w.r.t. grevlex(𝒙)), for any

𝜂 ∈ C 𝑡 \ W ∞ , ℎ(𝜂, •) coincides with the normal form of ℎ(𝜂, •) w.r.t. G (𝜂, •). This implies that H 𝑔 (𝜂) = H 𝜂 𝑔 . □ Corollary 3.2. For all 𝜂 ∈ C 𝑡 \ W ∞ , the signature of H 𝑔 (𝜂) is the Tarski-query of 𝑔(𝜂, •) for the zero-dimensional system 𝒇 (𝜂, •).
Proof. By Proposition 3.1, H 𝑔 (𝜂) is a Hermite matrix associated to (𝒇 (𝜂, •), 𝑔(𝜂, •)). The result follows from Theorem 2.4 . □

Note that W ∞ does not depend on 𝑔. One can compute the number of real roots of the specialized system 𝒇 (𝜂, •) satisfying some sign condition for 𝑔 by computing the signatures of three parametric Hermite matrices evaluated in 𝜂 and inverting the system (2).

Degree bounds

We bound the degrees of the entries of the parametric Hermite matrix H 𝑔 under some assumptions that we make explicit below. We start by recalling the definition of a regular sequence.

Definition 3.3 (Regular seqence). Let (𝑓 1 , . . . , 𝑓 𝑝 ) ⊂ K[𝒙]
with 𝑝 ≤ 𝑛 be a homogeneous polynomial sequence. We say that (𝑓 1 , . . . , 𝑓 𝑝 ) is a homogeneous regular sequence if for all 1 ≤ 𝑖 ≤ 𝑝, 𝑓 𝑖 is not a zero-divisor in K[𝒙]/⟨𝑓 1 , . . . , 𝑓 𝑖 -1 ⟩.

A polynomial sequence (𝑓 1 , . . . , 𝑓 𝑝 ) ⊂ K[𝒙] is called an affine regular sequence if (𝑓 𝐻 1 , . . . , 𝑓 𝐻 𝑝 ) is a homogeneous regular sequence, where for a polynomial 𝑞 ∈ K[𝒙], 𝑞 𝐻 denotes the homogeneous component of largest degree of 𝑞.

First we bound the degrees of the entries of the matrix H 𝑔 . For 𝑝 ∈ Q[𝒚] [𝒙] we denote by deg(𝑝) the total degree of 𝑝 and deg 𝒙 (𝑝) (resp. deg 𝒚 (𝑝)) the degree of 𝑝 w.r.t. 𝒙 (resp. 𝒚). Let 𝑑 max 1≤𝑖 ≤𝑝 deg(𝑓 𝑖 ). We consider the reduced Gröbner basis G as above and the associated monomial basis B of monomials in 𝒙 of the finite dimensional vector space A K . The quotient ring A K has dimension 𝛿. Note that by the regularity assumption, the codimension of the ideal generated by 𝑓 1 , . . . , 𝑓 𝑝 is 𝑝 if this ideal is not ⟨1⟩. Hence, combined with Assumption A, this forces 𝑝 = 𝑛 and by Bézout's inequality, we have 𝛿 ≤ 𝑑 𝑛 . We recall below Assumption B. As a direct consequence, the degree of a minor of H 𝑔 defined by the rows (𝑟 1 , . . . , 𝑟 𝑘 ) and the columns (𝑐 sign(𝑄 𝑖 (𝑥)) = 𝜎 (𝑖)}.

∈ Q[𝒚] [𝒙], 𝐶 ∈ Q[𝒚] 𝛿 ×𝛿 . So, ℎ 𝑖,𝑗 = Tr(𝐶) = 𝛿 𝑘=1 𝑐 𝑘,𝑘 ∈ Q[𝒚
We consider the set SIGN(Q, Z) ⊆ {0, 1, -1} 𝑠 of realizable sign conditions for Q over Z.

Let 𝒇 and 𝒈 be an instance of Problem 1. We are interested in the set of sign conditions SIGN(𝒈, V R ). We describe an algorithm for the determination of the realizable sign conditions for 𝒈 over the real solutions of 𝒇 = 0 when 𝒇 satisfies Assumption A. This algorithm does not recover the whole set SIGN(𝒈, V R ), but only the set of realizable conditions for 𝒈 over V R ∩ W where W is a nonempty Zariski open subset of C 𝑡 +𝑛 . It means that we potentially miss some elements of SIGN(𝒈, V R ) but they can only occur for (𝒚, 𝒙) lying in a Zariski closed set. Also, as a by-product our algorithm enables us to compute a valid solution to Problem 1 for (𝒇, 𝒈).

This algorithm is a variant of [2, Chap. 10] for determining the sign conditions realized by a family of polynomials on a finite set of points in R 𝑘 using Tarski-queries. Tarski-queries are expressed as signatures of parametric Hermite matrices as in Corollary 3.2. We also use sample points algorithms as in [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF][START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth algebraic set[END_REF]. In the case where 𝒈 is empty, this algorithm coincides with the one in [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF].

Sign determination on a finite set of points

We are given a family of polynomials Q = (𝑄 1 (𝑿 ), . . . , 𝑄 𝑠 (𝑿 )) ⊂ Q[𝑿 ] with 𝑿 = (𝑋 1 , . . . , 𝑋 𝑘 ) and an implicit finite set of points 𝑍 in R 𝑘 of size 𝑟 . By implicit we mean that we have no explicit description for the points in 𝑍 . Typically, the set 𝑍 designates the roots of the system 𝒇 (𝜂, •) = 0 with 𝜂 in the space of parameters and Q is the family 𝒈(𝜂, •). For now we assume that we have access to a black-box for computing the Tarski-queries TaQ(𝑄, 𝑍 ) for any

𝑄 ∈ Q[𝑿 ]. We aim at computing SIGN(Q, 𝑍 ).
For a sign condition 𝜎 ∈ {0, 1, -1} 𝑠 for Q, define 𝑐 (𝜎, 𝑍 )

♯ Reali(𝜎, 𝑍 ) and, for 𝛼 ∈ {0, 1, 2} 𝑠 , denote Q 𝛼 𝑠 𝑖=1 𝑄 𝛼 (𝑖 ) 𝑖
, and 𝑖 ) . One can notice that on Reali(𝜎, 𝑍 ), the sign of Q 𝛼 is fixed and equal to 𝜎 𝛼 .

𝜎 𝛼 𝑠 𝑖=1 𝜎 (𝑖) 𝛼 (
We also order {0, 1, -1} 𝑠 with the lexicographic order induced by 0 < 1 < -1 and {0, 1, 2} 𝑠 with the lexicographic order induced by 0

< 1 < 2. Let Σ = {𝜎 1 , . . . , 𝜎 𝑝 } ⊂ {0, 1, -1} 𝑠 with 𝜎 1 < lex • • • < lex 𝜎 𝑝 , we denote by 𝑐 (Σ, 𝑍 ) the column vector (𝑐 (𝜎 1 , 𝑍 ), . . . , 𝑐 (𝜎 𝑝 , 𝑍 )) 𝑡 . Similarly, let 𝐴 = {𝛼 1 , . . . , 𝛼 𝑚 } ⊂ {0, 1, 2} 𝑠 with 𝛼 1 < lex • • • < lex 𝛼 𝑚 , we denote by TaQ(Q 𝐴 , 𝑍 ) the column vector (TaQ(Q 𝛼 1 , 𝑍 ), . . . , TaQ(Q 𝛼 𝑚 , 𝑍 )) 𝑡 .
We define the matrix of signs of 𝐴 on Σ as the 𝑚 × 𝑝 matrix Mat(𝐴, Σ) whose entry

(𝑖, 𝑗) is 𝜎 𝛼 𝑖 𝑗 . Proposition 4.1 ([2, Prop. 10.59]). If SIGN(Q, 𝑍 ) ⊆ Σ, then it holds that Mat(𝐴, Σ) • 𝑐 (Σ, 𝑍 ) = TaQ(Q 𝐴 , 𝑍 ).
Hence, when Mat(𝐴, Σ) is invertible, one can determine 𝑐 (Σ, 𝑍 ) and thus SIGN(Q, 𝑍 ) = {𝜎 ∈ Σ | 𝑐 (𝜎, 𝑍 ) > 0} from TaQ(Q 𝐴 , 𝑍 ) by linear system solving. In this case, we say that the set 𝐴 is adapted to Σ for sign determination. If one chooses Σ = {0, 1, -1} 𝑠 to be the whole set of possible sign conditions for Q, the only adapted set to Σ is 𝐴 = {0, 1, 2} 𝑠 as we need Mat(𝐴, Σ) to be square. In this case Mat(𝐴, Σ) is invertible [2, Prop. 10.60]. However, we need to compute 3 𝑠 Tarski-queries to perform sign determination. Yet the number of realizable sign conditions is bounded by the number 𝑟 of elements in 𝑍 and often 𝑟 ≪ 3 𝑠 . So when Σ = {0, 1, -1} 𝑠 , many entries in 𝑐 (Σ, 𝑍 ) are equal to 0. To avoid to compute an exponential number of Tarski-queries, we want to avoid unrealizable sign conditions. To do so, we use the incremental approach of [2, Sec. 10.3]. Let Q 𝑖 (𝑄 𝑠 -𝑖+1 , . . . , 𝑄 𝑠 ) be the last 𝑖 polynomials in Q. At step 𝑖, we compute SIGN(Q 𝑖 , 𝑍 ) the realizable sign conditions for Q 𝑖 , for 𝑖 from 1 to 𝑠, so that we get rid of the empty sign conditions at each step of the computation.

First for any Σ ⊆ {0, 1, -1} 𝑠 , we explain how to construct a set 𝐴 ⊆ {0, 1, 2} 𝑠 that is adapted to Σ. For 𝜎 = (𝜎 (1), . . . , 𝜎 (𝑠)) ∈ {0, 1, -1} 𝑠 , we denote by 𝜎 ′ the vector obtained by removing the first coordinate of 𝜎, i.e. 𝜎 ′ (𝜎 (2), . . . , 𝜎 (𝑠

)) ∈ {0, 1, -1} 𝑠 -1 . Definition 4.2. For Σ ⊆ {0, 1, -1} 𝑠 , we define Σ ′ 1 {𝜎 ′ | 𝜎 ∈ Σ}, and the subsets Σ ′ 2 , Σ ′ 3 ⊆ Σ ′ 1 such that Σ ′ 2 (resp. Σ ′ 3 ) contains the elements of Σ ′
1 that can be extended to an element of Σ in at least two different ways (resp. exactly three different ways). if 𝑠 = 1, let ℎ ∈ {1, 2, 3} be the size of Σ, and set Ada(Σ) = {0, . . . , ℎ -1}; Now suppose that for 1 ≤ 𝑖 < 𝑠, we have built SIGN(Q 𝑖 , 𝑍 ) and Ada(SIGN(Q 𝑖 , 𝑍 )), we explain how we can compute SIGN(Q 𝑖+1 , 𝑍 ) and Ada(SIGN(Q 𝑖+1 , 𝑍 )). It is based on the two following lemmas. Lemma 4.5. Let 𝑠 1 , 𝑠 2 ≥ 0, and

-if 𝑠 > 1, Ada(Σ) = 0 × Ada(Σ ′ 1 ) ∪ 1 × Ada(Σ ′ 2 ) ∪ 2 × Ada(Σ ′ 3 ).
𝐴 1 ⊆ {0, 1, 2} 𝑠 1 , 𝐴 2 ⊆ {0, 1, 2} 𝑠 2 , Σ 1 ⊆ {0, 1, -1} 𝑠 1 , Σ 2 ⊆ {0, 1, -1} 𝑠 2 . The matrix of signs of 𝐴 1 × 𝐴 2 on Σ 1 × Σ 2 is Mat(𝐴 1 × 𝐴 2 , Σ 1 × Σ 2 ) = Mat(𝐴 1 , Σ 1 ) ⊗ Mat(𝐴 2 , Σ 2 ). As a consequence, if 𝐴 1 is adapted to Σ 1 and 𝐴 2 is adapted to Σ 2 then 𝐴 1 × 𝐴 2 is adapted to Σ 1 × Σ 2 . Proof. Let 𝛼 = (𝛼 1 , 𝛼 2 ) ∈ 𝐴 1 × 𝐴 2 and 𝜎 = (𝜎 1 , 𝜎 2 ) ∈ Σ 1 × Σ 2 .
By definition, we have

𝜎 𝛼 = 𝜎 𝛼 1 1 • 𝜎 𝛼 2 2 .
Since rows and columns of matrices of signs are ordered with the lexicographic orderings induced by 0 < 1 < 2 for the rows and 0 < 1 < -1 for the columns, the result holds. □ The computation of SIGN(Q 𝑖+1 , 𝑍 ) and Ada(SIGN(Q 𝑖+1 , 𝑍 )) is described in Algorithm 1. After 𝑠 iterations of this algorithm we get SIGN(Q, 𝑍 ). This is [2, Alg. 10.11].

General sign determination

We design an algorithm based on Algorithm 1 to solve Problem 1.

Let 𝒇 = (𝑓 1 , . . . , 𝑓 𝑝 ) ⊂ Q[𝒚] [𝒙] such that 𝒇 satisfies Assumption A and let 𝒈 = (𝑔 1 , . . . , 𝑔 𝑠 ) ⊂ Q[𝒚] [𝒙] define the inequalities of our input system. As before, let G be the reduced Gröbner basis of ⟨𝒇 ⟩ w.r.t. the ordering grevlex(𝒙) ≻ grevlex(𝒚). We also denote by K the field Q(𝒚) and

B ⊂ Q[𝒙] is the basis of A K K[𝒙]/⟨𝒇 ⟩ K derived from G of dimension 𝛿. Let 𝑔 ∈ Q[𝒚] [𝒙], H 𝑔 ∈ K 𝛿
H 𝑄 𝑔 (𝜂) = 𝑄 𝑡 H 𝑔 (𝜂)𝑄 = Δ 0 0 0 ,
where Δ is a diagonal matrix of size 𝑟 with nonzero real entries on its diagonal. Hence the evaluation of 𝔲 at the entries of 𝑄 gives 𝑀 𝑗 (𝔲) a nonzero value. So we conclude that 𝑀 𝑗 (𝔲) is not identically zero.

Finally, let U 𝑗 be the nonempty Zariski open subset of GL 𝛿 (C) defined as the non-vanishing set of 𝑀 𝑗 (𝔲). We define U 𝑔 as the intersection of U 𝑗 for 1 ≤ 𝑗 ≤ 𝑟 , and for 𝑈 ∈ U 𝑔 , none of the first 𝑟 leading principal minors of H 𝑈 𝑔 (𝜂) is zero. Thus, none of the first 𝑟 leading principal minors of H 𝑈 𝑔 is identically zero. □ Lemma 4.8. Let 𝑆 be a symmetric matrix in R 𝛿 ×𝛿 of rank 𝑟 and let 𝑆 𝑖 be its 𝑖-th leading principal minor for 0 ≤ 𝑖 ≤ 𝛿. We assume that 𝑆 𝑖 ≠ 0 for 𝑖 ≤ 𝑟 . Then, the signature of 𝑆 equals 𝑟 -2𝑣 where 𝑣 is the number of sign variations in 𝑆 0 , . . . , 𝑆 𝑟 .

Proof. We have

𝑆 = 𝑆 𝑉 𝑡 𝑉 𝑊 = 𝐼 𝑟 0 𝑉 𝑆 -1 𝐼 𝛿 -𝑟 𝑆 0 0 𝑊 -𝑉 𝑆 -1 𝑉 𝑡 𝑅 𝐼 𝑟 𝑆 -1 𝑉 𝑡 0 𝐼 𝛿 -𝑟 .
.

Thus 𝑆 and 𝑅 have the same signature. Since det( 𝑆) = 𝑆 𝑟 ≠ 0, we have rk( 𝑆) = 𝑟 = rk(𝑆) = rk(𝑅). Therefore, 𝑊 -𝑉 𝑆 -1 𝑉 𝑡 = 0 and Sign(𝑅) = Sign( 𝑆). By Theorem 2.5, Sign( 𝑆) = 𝑟 -2𝑣. □

We use the previous lemmas as follows. Assume that after picking randomly a matrix 𝑈 ∈ GL 𝛿 (C), the first 𝑟 leading principal minors of H 𝑈 𝑔 𝑈 𝑡 • H 𝑔 • 𝑈 are not identically zero, with 𝑟 the rank of H 𝑔 . Then over a connected component of the semi-algebraic set defined by the complementary of W ∞ and the non-vanishing set of these minors, the sign of each leading principal minor is invariant. Consequently the Tarski-query TaQ(𝒇 (𝜂, •), 𝑔(𝜂, •)) is invariant when 𝜂 ranges over this connected component. Then by sampling at least one point in each connected component using the algorithm in [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF] originating from [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth algebraic set[END_REF], we are able to recover all the sign conditions satisfied by a family of polynomials 𝒈 on a dense subset of V R the real algebraic set defined by 𝒇 = 0.

Algorithm 2 for solving Problem 1 uses the subroutines: • FirstHermiteMatrix follows from Algorithm 1 in [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]. It takes as input a polynomial sequence 𝒇 that satisfies Assumption A and outputs a Gröbner basis G of ⟨𝒇 ⟩ for the ordering grevlex(𝒙) ≻ grevlex(𝒚), a monomial basis B of A K derived from G , the family of multiplication matrices

(𝑀 𝑏 ) 𝑏 ∈B in B, a polynomial 𝑤 ∞ ∈ Q[𝒚]
whose vanishing set is W ∞ defined in (3), and the Hermite matrix H 1 associated to (𝒇, 1) in B.

• LeadPrincMinors returns the list of the numerators of the nonzero leading principal minors of a matrix with entries in Q(𝒚).

• SamplePoints that takes as input a sequence of polynomials (ℎ 1 , . . . , ℎ ℓ ) ⊂ Q[𝒚] and sample a finite set of points that meets every connected component of the semi-algebraic set defined by

ℎ 1 ≠ 0, . . . , ℎ ℓ ≠ 0.
For a family of polynomials (𝑄 1 , . . . , 𝑄 ℓ ) ⊂ Q[𝒚] and 𝜂 ∈ R 𝑡 the sign pattern of (𝑄 𝑖 (𝜂)) 1≤𝑖 ≤ℓ is the semi-algebraic formula Φ below

Φ ℓ 𝑖=1 sign(𝑄 𝑖 ) = sign(𝑄 𝑖 (𝜂)). ( 4
)
Theorem 4.9 (Correction). Assume that 𝒇 satisfies Assumption A. Let 𝒈 = (𝑔 1 , . . . , 𝑔 𝑠 ) be a polynomial sequence. There exists a Zariski dense subset

U of GL 𝛿 (C) such that if 𝑈 is sam- pled in U ∩ Q 𝛿 ×𝛿 , Algorithm 2 outputs a set Σ that is equal to SIGN(𝒈, V R ∩ 𝜋 -1 (W))
where V R is the real algebraic set defined by 𝒇 and W is a nonempty Zariski open subset of C 𝑡 ; and a solution to Problem 1 for (𝒇, 𝒈).

Proof. For 1 ≤ 𝑖 ≤ 𝑠, let Σ 𝑖 be the value of Σ and Ada 𝑖 the value of Ada after the 𝑖-th iteration of the loop in line 5. We also define Σ 0 ∅ and 𝒈 0 ∅. We prove the following loop invariant: for all 0 ≤ 𝑖 ≤ 𝑠, there exists a Zariski dense subset U 𝑖 of GL 𝛿 (C) s.t. if 𝑈 was sampled in

U 𝑖 ∩ Q 𝛿 ×𝛿 , then Σ 𝑖 = SIGN(𝒈 𝑖 , V R ∩ 𝜋 -1 (W 𝑖 ))
where W 𝑖 is the nonempty Zariski open subset in C 𝑡 defined as the non-vanishing locus of 𝑤 ∞ and the polynomials in the set Minors obtained after performing the for loop starting at line 9. This is true when entering the loop as Σ 0 = ∅ = SIGN(∅, V R ). Now suppose that the result holds for 0 ≤ 𝑖 -1 < 𝑠. Let Σ * {0, 1, -1}×Σ 𝑖 -1 and Ada * {0, 1, 2}×Ada 𝑖 -1 . By Lemma 4.7, for each 𝛼 ∈ Ada * there exists a Zariski dense subset U 𝛼 of GL 𝛿 (C) such that if 𝑈 ∈ U 𝛼 , the first rk 𝛼 (see line 10) leading principal minors of

𝑈 𝑡 • H 𝒈 𝛼 𝑖 • 𝑈 are not identically 0. Let U 𝑖 U 𝑖 -1 ∩ 𝛼 ∈Ada * U 𝛼 .
It is a Zariski dense subset of GL 𝛿 (C) and we further suppose that 𝑈 was sampled in U 𝑖 ∩ Q 𝛿 ×𝛿 . In particular 𝑈 ∈ U 𝑖 -1 , so by the induction hypothesis, Σ 𝑖 -1 = SIGN(𝒈 𝑖 -1 , V R ∩ 𝜋 -1 (W 𝑖 -1 )). Note that W 𝑖 is nonempty since all its defining polynomials are not identically 0 and W 𝑖 ⊆ W 𝑖 -1 as the set Minors can only increase along the iterations. We now show that Σ 𝑖 = SIGN(𝒈 𝑖 , V R ∩ 𝜋 -1 (W 𝑖 )). Let R be the semialgebraic set defined as the real trace of W 𝑖 . Then the signs of the first rk 𝛼 leading principal minors of 𝑈

) ⊂ Q[𝒚] [𝒙] such that 𝒇 satisfies Assumption A -A polynomial sequence 𝒈 = (𝑔 1 , . . . , 𝑔 𝑠 ) ⊂ Q[𝒚] [𝒙] Output :
-A set Σ ⊆ {0, 1, -1} 𝑠 of sign conditions satisfied by 𝒈 on the real algebraic set defined by 𝒇 -The description of a collection of semi-algebraic sets T 𝑖 solving Problem 1

1 H 1 , 𝑤 ∞ , G , B, (𝑀 𝑏 ) 𝑏 ∈B ← FirstHermiteMatrix(𝒇 ) 2 Choose randomly a matrix 𝑈 ∈ Q 𝛿 ×𝛿 3 Σ ← ∅, Ada ← ∅, 𝑀 ← Mat(Ada, Σ) 4 Minors ← ∅ 5 for 𝑖 from 1 to 𝑠 do 6 𝒈 𝑖 ← (𝑔 𝑠 -𝑖+1 , . . . , 𝑔 𝑠 ) 7 Σ ← {0, 1, -1} × Σ, Ada ← {0, 1, 2} × Ada, 8 𝑀 ← Mat(Ada, Σ) = Mat({0, 1, 2}, {0, 1, -1}) ⊗ 𝑀 9 for 𝛼 ∈ Ada do 10
Compute H 𝒈 𝛼 𝑖 using the algorithm of Section 3.1 and let rk 𝛼 be its rank

11 (ℎ 𝛼 1 , . . . , ℎ 𝛼 rk 𝛼 ) ← LeadPrincMinors(𝑈 𝑡 • H 𝒈 𝛼 𝑖 • 𝑈 ) 12 Minors ← Minors ∪ {ℎ 𝛼 1 , . . . , ℎ 𝛼 rk 𝛼 } 13 end 14 𝐿 ← SamplePoints(𝑤 ∞ ≠ 0 ∧ Minors ≠ 0)
𝑟 𝜂 ← entry of 𝑐 𝜂 corresponding to (1, 1, . . . , 1) ∈ {0, 1, -1} 𝑠 27 end 28 return Σ, (Φ 𝜂 ∧ 𝑤 ∞ ≠ 0 ∧ Minors ≠ 0, 𝜂, 𝑟 𝜂 ) 𝜂 ∈𝐿 at least one point in each connected component of R. So we have {𝑇 𝜂 | 𝜂 ∈ R} = {𝑇 𝜂 | 𝜂 ∈ 𝐿}. Moreover, by the induction hypothe- sis, for all 𝜂 ∈ R, we have SIGN(𝒈 𝑖 -1 , V R ∩ 𝜋 -1 (𝜂)) ⊆ Σ 𝑖 -1 since 𝜂 ∈ W 𝑖 -1 .
Thus for all 𝜂 ∈ R, we have

Σ 𝜂 SIGN(𝒈 𝑖 , V R ∩ 𝜋 -1 (𝜂)) ⊆ {0, 1, -1} × Σ 𝑖 -1 Σ * .
As a consequence of Proposition 4.1, Σ 𝜂 corresponds to the nonzero entries of

𝑐 𝜂 Mat(Σ * , Ada * ) -1 • 𝑇 𝜂 = 𝑀 -1 • 𝑇 𝜂 . Since 𝑀 does not depend on 𝜂, it holds that Σ 𝜂 is invariant over a connected component of R. Finally, SIGN(𝒈 𝑖 , V R ∩ 𝜋 -1 (W 𝑖 )) = SIGN(𝒈 𝑖 , V R ∩ 𝜋 -1 (R)) = 𝜂 ∈ R Σ 𝜂 = 𝜂 ∈𝐿 Σ 𝜂 = Σ 𝑖 .
Hence Algorithm 2 outputs a set Σ describing all the sign conditions realised by 𝒈 on V R ∩ 𝜋 -1 (W) for W a nonempty Zariski open subset of C 𝑡 . Finally, we show that the output of Algorithm 2:

(Φ 𝜂 ∧ 𝑤 ∞ ≠ 0 ∧ Minors ≠ 0, 𝜂, 𝑟 𝜂 ) 𝜂 ∈𝐿 is a solution for Problem 1.
For 𝜂 ∈ 𝐿, let T 𝜂 be the semi-algebraic set defined by Φ 𝜂 ∧ 𝑤 ∞ ≠ 0 ∧ Minors ≠ 0. By construction, 𝑐 𝜂 ′ is invariant when 𝜂 ′ varies over T 𝜂 and its first entry equals 𝑟 𝜂 that is exactly ♯V R ∩ 𝜋 -1 (𝜂 ′ ). The union of the sets T 𝜂 is R 𝑡 \ W; it is dense in R 𝑡 . □

Complexity analysis

Further, we use the following notation for integers 𝑎, 𝑏, 𝑐:

T 𝑎,
= (𝑔 1 , . . . , 𝑔 𝑠 ) ⊆ Q[𝒚] [𝒙] a polynomial sequence.
Let 𝑑 be a bound on the degree of the polynomials in 𝒇 and 𝒈. We further assume that 𝑛, 𝑡 and 𝑑 are at least 2 as we are dealing with asymptotics. Let 2 < 𝜔 ≤ 3 be an admissible exponent for matrix multiplication. We also denote 𝜆 𝑛(𝑑 -1).

We prove that the arithmetic cost of each loop iteration in Algorithm 2 is dominated by the computation of the sample points at line 14. By [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]Prop. 26], the cost in terms of arithmetic operations in Q of the call to FirstHermitematrix at line 1 is at most O M 𝑡,2𝜆 𝑛T 𝑑,𝑡,𝑛 + 𝑛 𝜔+1 𝑑 𝜔𝑛+1 + 𝑑 (𝜔+1)𝑛 .

(

Note that at loop iteration 𝑖 the newly computed Hermite matrices are of the form H • 𝐿 𝑔 𝑖 , H • 𝐿 2 𝑔 𝑖 , where H is a Hermite matrix that has already been computed at the previous iteration and 𝐿 𝑔 𝑖 is the matrix of the multiplication by 𝑔 𝑖 w.r.t. the basis B in A K . So, each Hermite matrix is computed by multiplying a known Hermite matrix by one matrix of multiplication 𝐿 𝑔 𝑖 for 1 ≤ 𝑖 ≤ 𝑠. Proof. Let 𝛿 be the size of the Hermite matrix 𝐿 𝑔 . We already observed that 𝛿 ≤ 𝑑 𝑛 . We compute 𝐿 𝑔 by evaluation and interpolation using the multivariate interpolation algorithm of [START_REF] Canny | Solving systems of nonlinear polynomial equations faster[END_REF]. Because 𝒇 satisfies Assumption B and is regular, by Lemma 3.6 and [21, Lem. 23], the matrix 𝐿 𝑔 has polynomial entries in 𝒚 of degree at most 𝑑 + 𝜆. Thus we need T 𝑡,𝑑,𝜆 interpolation points 𝜂 ∈ Q 𝑡 .

First we bound the cost of computing 𝐿 𝑔 (𝜂) for 𝜂 ∈ Q 𝑡 . We start by computing all the matrices 𝐿 𝑥 𝑖 (𝜂). This is done in time O (𝑑𝑛 𝜔+1 𝛿 𝜔 ) = O (𝑛 𝜔+1 𝑑 𝜔𝑛+1 ) using [START_REF] Faugère | Sub-cubic change of ordering for gröbner basis: a probabilistic approach[END_REF]Algo. 4]. Then we evaluate 𝑔 at 𝜂 in time O T 𝑑,𝑡,𝑛 . We write 𝑔(𝜂, 𝒙) = 𝑚 𝑐 𝑚 𝑚 where 𝑐 𝑚 ∈ Q and 𝑚 ranges over the set of monomials in 𝒙 of degree at most 𝑑. There are M 𝑛,𝑑 such monomials. We compute all the matrices 𝐿 𝑚 (𝜂) using 𝑂 (M 𝑛,𝑑 𝑑 𝜔𝑛 ) arithmetic operations by multiplying appropriately the matrices 𝐿 𝑥 𝑖 (𝜂). Then, we compute 𝐿 𝑔 (𝜂) = 𝑚 𝑐 𝑚 𝐿 𝑚 (𝜂) in time O (𝑑 2𝑛 M 𝑛,𝑑 ). All in all, computing 𝐿 𝑔 (𝜂) uses O T 𝑑,𝑡,𝑛 + M 𝑛,𝑑 𝑑 𝜔𝑛 + 𝑛 𝜔+1 𝑑 𝜔𝑛+1 arithmetic operations in Q. Hence, the whole evaluation step has an arithmetic cost lying in O T 𝑡,𝑑,𝜆 T 𝑑,𝑡,𝑛 + M 𝑛,𝑑 𝑑 𝜔𝑛 + 𝑛 𝜔+1 𝑑 𝜔𝑛+1 .

Finally, we interpolate 𝛿 2 entries which are polynomials in Q[𝒚] of degree at most 𝑑 + 𝜆. So using multivariate interpolation [START_REF] Canny | Solving systems of nonlinear polynomial equations faster[END_REF]

arithmetic operations in Q.

Proof. Again let 𝛿 ≤ 𝑑 𝑛 be the size of the Hermite matrix H 𝑔 . We write 𝑔 = 𝑔 ′ 𝑔 𝑖 so that H 𝑔 = H 𝑔 ′ • 𝐿 𝑔 𝑖 for some 1 ≤ 𝑖 ≤ 𝑠 and H 𝑔 ′ a parametric Hermite matrix that is already known. By Lemma 3.6 and Proposition 3.7, the matrices H 𝑔 , H 𝑔 ′ and 𝐿 𝑔 𝑖 have entries in [START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]Lem. 23] the largest degree among the entries of H 𝑔 and H 𝑔 ′ is bounded by Λ 𝑑 𝑔 + 2𝜆 and 𝐿 𝑔 𝑖 has all its entries of degree at most 𝑑 + 𝜆. We compute the evaluations H 𝑔 (𝜂) = H 𝑔 ′ (𝜂) • 𝐿 𝑔 𝑖 (𝜂) for M 𝑡,Λ distinct points 𝜂 ∈ Q 𝑡 , and then we interpolate the matrix H 𝑔 using the algorithm of [START_REF] Canny | Solving systems of nonlinear polynomial equations faster[END_REF].

Q[𝒚]. Moreover, by
Let 𝜂 ∈ Q 𝑡 . We first estimate the cost of computing 𝐿 𝑔 𝑖 (𝜂). It is the evaluation of 𝛿 2 polynomials in Q[𝒚] of degree at most 𝑑 + 𝜆. So its cost is in O T 𝑡,𝑑,𝜆 𝛿 2 arithmetic operations in Q.

Similarly, we estimate the cost for computing H 𝑔 ′ (𝜂). We obtain O M 𝑡,Λ 𝛿 2 arithmetic operations in Q.

Finally, we need to compute the matrix product H 𝑔 ′ (𝜂)𝐿 𝑔 𝑖 (𝜂) and this is done in time O (𝛿 𝜔 ). Notice that 𝜆 -𝑑 = 𝑛(𝑑 -1) -𝑑 = 𝑛𝑑 -𝑛 -𝑑 ≥ 0, as 𝑛 ≥ 2 and 𝑑 ≥ 2. So 𝑑 + 𝜆 ≤ Λ. Summing up every step together we obtain that the evaluation H 𝑔 (𝜂) can be computed within O 𝛿 2 M 𝑡,Λ + 𝛿 𝜔 arithmetic operations in Q. Since there are M 𝑡,Λ evaluation points, the whole evaluation step uses O M 𝑡,Λ 𝑑 2𝑛 M 𝑡,Λ + 𝑑 𝜔𝑛 arithmetic operations in Q at most. Finally, we interpolate 𝛿 2 entries which are polynomials in Q[𝒚] of degree at most Λ. Using [START_REF] Canny | Solving systems of nonlinear polynomial equations faster[END_REF], the complexity of this step lies in O 𝛿 2 M 𝑡,Λ log 2 M 𝑡,Λ log log M 𝑡,Λ . Summing up these costs, we obtain the claimed complexity for H 𝑔 .

To compute the minors, we again use an evaluation-interpolation scheme. Any minor of H 𝑔 has degree at most (𝑑 𝑔 + 𝜆)𝑑 𝑛 by Corollary 3.8, so we need M 𝑡,(𝑑 𝑔 +𝜆)𝑑 𝑛 interpolation points. Each evaluation of the matrix costs O 𝛿 2 M 𝑡,Λ and the computation of the minors lies in O (𝛿 𝜔 ). We deduce the bound as before.

□

One shows that the cost for computing the minors of H 𝑔 dominates the cost for computing the matrix H 𝑔 . First note that M 𝑛,𝑑 = (𝑑 + 𝑛) . . . (𝑑 + 1)

𝑛! = 𝑑 𝑛 𝑛 𝑘=1 1 𝑑 + 1 𝑘 ≤ 2𝑑 𝑛 , since 1 𝑑 +1 ≤ 2 and 1 𝑑 + 1 𝑘 ≤ 1 for 𝑘 ≥ 2.
Then, the cost in Lemma 4.10 is bounded by the cost (5) of FirstHermiteMatrix. In [21, Sec. 6.2], it is shown that ( 5) is bounded by O M 𝑡,𝜆𝑑 𝑛 M 𝑡,2𝜆 𝑑 2𝑛 . Thus the cost for computing 𝐿 𝑔 𝑖 is bounded by [START_REF] Chen | Geometric fiber classification of morphisms and a geometric approach to cylindrical algebraic decomposition[END_REF]. In addition, it holds that ( 6) is bounded by [START_REF] Chen | Geometric fiber classification of morphisms and a geometric approach to cylindrical algebraic decomposition[END_REF]. Hence we can conclude that computing the minors dominates the cost of computing the matrices. Now let us bound the cost of computing the set of sample points at Line 14. In Algorithm

arithmetic operations in Q. We can now prove Theorem 1.1.

Proof of Theorem 1.1. The sequence 𝒇 is regular and satisfies both Assumptions A and B. At each iteration of Algorithm 2, the call to SamplePoints has a cost bounded by [START_REF] Collins | Quantifier elimination for real closed fields by cylindrical algebraic decomposition[END_REF]. We also compute at most 2𝑟 new Hermite matrices and their 𝛿 ≤ 𝑑 𝑛 leading principal minors. By Proposition 4.11, this can be done using O 𝑑 𝑛 𝑟 M 𝑡,𝔇 𝑑 2𝑛 T 𝑡,2𝑠𝑑,2𝜆 + 𝑑 𝜔𝑛 arithmetic operations. Since T 𝑡,2𝑠𝑑,2𝜆 ∈ O 𝔇 𝑡 , the above estimate is bounded by [START_REF] Collins | Quantifier elimination for real closed fields by cylindrical algebraic decomposition[END_REF]. Next, we have to evaluate the signatures of at most 3𝑟 Hermite matrices for every points 𝜂 ∈ 𝐿. This is done by evaluating the sign patterns of the minors. There are at most 3𝛿𝑟 minors of degree at most 𝔇 to evaluate at at most (4𝑑 𝑛 𝑠𝑟𝔇) 𝑡 points. This is done within O 𝑑 𝑛 𝑟 (4𝑑 𝑛 𝑠𝑟𝔇) 𝑡 M 𝑡,𝔇 arithmetic operations in Q and this is bounded by [START_REF] Collins | Quantifier elimination for real closed fields by cylindrical algebraic decomposition[END_REF]. The linear algebra to solve the linear systems 𝑀 • 𝑐 𝜂 = 𝑇 𝜂 or to compute the rank row profile of 𝑀 has a negligible cost in front of the evaluations of the minors. Finally we sum the costs for each of the 𝑠 iterations and substitute the values of 𝜆, 𝑟, 𝔇 to get the complexity estimate. The algorithm outputs ♯𝐿 ≤ (4𝑑 𝑛 𝑠𝑟𝔇) 𝑡 formulas. Each formula contains O (𝑑 𝑛 𝑠𝑟 ) minors of degree at most 𝔇. This completes the proof. □

PRACTICAL EXPERIMENTS

We report here on the practical behaviour of our algorithm and compare it with existing Maple packages based on other methods for solving parametric semi-algebraic systems. In Algorithm 2, we need to compute sample points per connected components of the non-vanishing set of leading principal minors of several Hermite matrices. Once we have computed these sample points, the semi-algebraic conditions for the classification are derived from the sign patterns of the minors on these points. However when facing practical problems, calling the SamplePoints routine with this number of minors is often the bottleneck of Algorithm 2. If we assume that for each inequality 𝑔 𝑖 with 1 ≤ 𝑖 ≤ 𝑠, the Hermite matrix H 𝑔 𝑖 is nonsingular, one can get better timings in practice with the following approach:

• Compute a set {𝜂 1 , . . . , 𝜂 ℓ } of sample points in the nonvanishing set of the determinants of (H 1 , H 𝑔 1 , . . . , H 𝑔 𝑠 ). For 1 ≤ 𝑖 ≤ ℓ, perform sign determination to obtain 𝑟 𝑖 the number of solutions of the specialized system (𝒇 (𝜂 𝑖 , •), 𝒈(𝜂 𝑖 , •)).

One can show that we obtain all the possible number of solutions that the input system can admit. • Next in order to get semi-algebraic conditions, compute the 3 𝑠 Hermite matrices H 𝒈 𝛼 for all 𝛼 ∈ {0, 1, 2} 𝑠 and all their leading principal minors. From each sign pattern 𝜏 on this family of minors, the signatures of the Hermite matrices are determined and one can associate 0 ≤ 𝑟 𝜏 ≤ 𝛿 the number of solutions of the input system. Finally we derive a classification from the sign patterns 𝜏 such that 𝑟 𝜏 ∈ {𝑟 1 , . . . , 𝑟 ℓ }.

Notice that we get a classification with semi-algebraic formulas that contain clauses that may be infeasible. Yet we only need one call to the SamplePoints routine with 𝑠 + 1 polynomials in input.

The timings are given in hours (h.), minutes (m.) and seconds (s.) and the computations have been performed on a PC Intel (R) Xeon (R) Gold 6244 CPU 3.6GHz with 1.5Tb of RAM. In our implementation, we compute Hermite matrices using FGb package [START_REF] Faugère | Fgb: a library for computing gröbner bases[END_REF] for Gröbner basis computation. For the sample points routine, we use RAGlib [START_REF] Din | Real algebraic geometry library, raglib (version 3.4)[END_REF]. In Table 1, we analyse the costs on dense generic inputs, i.e. the input polynomials (𝑓 1 , . . . , 𝑓 𝑛 ) and (𝑔 1 , . . . , 𝑔 𝑠 ) ⊂ Q[𝒚] [𝒙] are dense and randomly chosen among polynomials of degree 𝑑. We collect results for various values of (𝑛, 𝑡, 𝑠, 𝑑). We focus on the timings for computing all the Hermite matrices (hm), all their leading principal minors (min). We also report in column det the timings for computing only the (𝑠 + 1) matrices (H 1 , H 𝑔 1 , . . . , H 𝑔 𝑠 ) and their determinants; and for computing sample points (column sp) in the non-vanishing locus of these determinants. We compare our algorithm with the Maple packages RootFinding[Parametric] [START_REF] Gerhard | A package for solving parametric polynomial systems[END_REF] (the column RF) and RegularChains[ParametricSystemTools] [START_REF] Yang | A complete algorithm for automated discovering of a class of inequality-type theorems[END_REF].

In the column RF, we give the timings for the command Discrim-inantVariety (dv) that computes a set of polynomials defining a discriminant variety D of the input system. For generic systems, the output of DiscriminantVariety coincides with the irreducible factors of the determinants of (H 1 , . . . , H 𝑔 𝑠 ) and the border polynomials returned by the command BorderPolynomial (bp) contains these polynomials. We also collect the results for the command CellDecomposition (cad) that outputs semi-algebraic formulas by computing an open CAD for R 𝑡 \ D. The column det has to be compared with the two columns dv and bp as they are three different approaches to compute polynomials that defines the boundary of semi-algebraic sets over which the number of solutions of the input system is invariant.

We observe that our method outperforms DiscrimantVariety and BorderPolynomial. With our approach based on the minors of the Hermite matrices, we are not only able to solve the classification problem for systems faster by several orders of magnitude than what can be achieved with CellDecomposition (cad) and the command Re-alRootClassification of the RegularChains[ParametricSystemTools] library. We can also tackle problems that were previously out of reach.

Perspective-Three-Point Problem (P3P). We now consider a system coming from the P3P problem and apply our algorithm to find a classification. The problem consists in determining the position of a camera given the relative spatial location of 3 control points. As in [START_REF] Faugère | Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities[END_REF], we want to compute a classification of the real solutions of the following system:

         1 = 𝐴 2 + 𝐵 2 -𝐴𝐵𝑢 𝑡 = 𝐵 2 + 𝐶 2 -𝐵𝐶𝑣 𝑥 = 𝐴 2 + 𝐶 2 -𝐴𝐶𝑤
with 𝐴 > 0, 𝐵 > 0, 𝐶 > 0, (P3P) subject to the following constraints: 𝑥, 𝑡 > 0, -2 < 𝑢, 𝑣, 𝑤 < 2, where 𝐴, 𝐵, 𝐶 are the variables and 𝑥, 𝑡, 𝑢, 𝑣, 𝑤 are parameters.

In [START_REF] Faugère | Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities[END_REF], a special case of (P3P) is studied where 𝑡 = 1. This restriction corresponds to the case where the three controls points form an isosceles triangle. In this case, a discriminant variety D for the system is computed in [START_REF] Faugère | Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities[END_REF]. Sample points in the semi-algebraic set R 4 \ D in order to deduce all the possible number of solutions of (P3P) in the isosceles case are computed using RAGlib but this is not sufficient to obtain semi-algebraic conditions that prescribe the number of real solutions to the input parametric system.

With our method, we are able to derive these semi-algebraic descriptions for each possible number of solutions from the signs of the leading principal minors of parametric Hermite matrices. In less than one hour, we compute all the minors and sample points in R 4 \ D whence we obtain a complete classification in the isosceles case.

We also studied the general case. The system (P3P) has 3 variables and 5 parameters. We compute the first Hermite matrix H 1 and the ones corresponding to each inequality H 𝐴 , H 𝐵 , H 𝐶 and their determinants in a few seconds. This gives polynomials defining a discriminant variety of the system (P3P). Already this first step was out of reach using the Maple commands DiscriminantVariety or BorderPolynomial. Next we are able to compute the leading principal minors of all Hermite matrices of the form H 𝐴 𝛼 1 𝐵 𝛼 2 𝐶 𝛼 3 with (𝛼 1 , 𝛼 2 , 𝛼 3 ) ∈ {0, 1, 2} 3 and get semi-algebraic conditions for a classification. One further step would be to sample points outside the discriminant variety to get all the possible number of solutions of the system (P3P).

Theorem 2 . 4 (

 24 [START_REF] Basu | Algorithms in real algebraic geometry[END_REF] Thm. 4.100]). Let 𝒇 = (𝑓 1 , . . . , 𝑓 𝑝 ) ⊂ K[𝒙] be as above and 𝑔 ∈ K[𝒙]. Then, Sign(Herm(𝒇, 𝑔)) = TaQ(𝑔, 𝒇 ).

Proposition 3 . 1 .

 31 For all 𝜂 ∈ C 𝑡 \ W ∞ , the specialization H 𝑔 (𝜂) coincides with the Hermite matrix H 𝜂 𝑔 associated to (𝒇 (𝜂, •), 𝑔(𝜂, •)) w.r.t. the basis B. Proof. Let 𝜂 ∈ C 𝑡 \W ∞ . By [21, Lem. 9] which is a consequence of [17, Thm. 3.1], the specialization G (𝜂, •) {𝑝 (𝜂, •) | 𝑝 ∈ G } is a Gröbner basis of the ideal ⟨𝒇 (𝜂, •)⟩ ⊆ C[𝒙] w.r.t. the ordering grevlex(𝒙). Since 𝜂 ∈ C 𝑡 \W ∞ , the leading coefficient lc 𝒙 (𝑝) does not vanish at 𝜂 for all 𝑝 ∈ G . Thus, the set of leading monomials of G in the variables 𝒙 w.r.t. grevlex(𝒙) is exactly the set of leading monomials of G (𝜂, •) w.r.t. grevlex(𝒙). Therefore, the finite set B is also the set of monomials in 𝒙 that are not reducible by G (𝜂, •). Hence B is a basis of the quotient ring C[𝒙]/⟨𝒇 (𝜂, •)⟩. So, ⟨𝒇 (𝜂, •)⟩ is zero-dimensional and one can define H 𝜂 𝑔 as the Hermite matrix associated to (𝒇 (𝜂, •), 𝑔(𝜂, •)) w.r.t. the basis B.

  For any 𝑝 ∈ G , we have deg 𝑝 = deg 𝒙 𝑝. By [21, Prop. 20], Assumption B holds for generic sequences 𝒇 . Lemma 3.4. Under Assumption B, deg 𝒚 (lc 𝒙 (𝑝)) = 0 for all 𝑝 ∈ G . Proof. Let 𝑝 ∈ G , by definition of the ordering grevlex(𝒙) ≻ grevlex(𝒚), lc 𝒙 (𝑝) is obtained from a term 𝜏 in 𝑝 s.t. deg 𝒙 (𝜏) = deg 𝒙 (𝑝). By Assumption B, deg 𝒙 (𝑝) = deg(𝑝), so deg 𝒚 (𝜏) = 0. □ Lemma 3.5. If Assumption B holds, then for any 𝑞 ∈ Q[𝒚] [𝒙], the normal form 𝑞 of 𝑞 w.r.t. G lies in Q[𝒚] [𝒙] and deg(𝑞) ≤ deg(𝑞). Proof. Let 𝑞 ∈ Q[𝒚] [𝒙], 𝑞 is the remainder of successive divisions of 𝑞 by polynomials in G . As Assumption B holds, by Lemma 3.4, those divisions do not introduce any denominator. So, every term appearing during these reductions are polynomials in Q[𝒚] [𝒙]. By Assumption B, for any 𝑝 ∈ G , the total degree of every term of 𝑝 is bounded by deg 𝒙 (𝑝) = deg(lm 𝒙 (𝑝)) by Lemma 3.4. Thus, a division of 𝑞 by 𝑝 involves only terms of total degree deg(𝑞). Therefore, during the normal form reduction of 𝑞 by G , only terms of degree at most deg(𝑞) will appear. Hence deg(𝑞) ≤ deg(𝑞). □ We prove now degree bounds on the entries of 𝐿 𝑔 and H 𝑔 . Lemma 3.6. Under Assumption B, let 𝑔 ∈ Q[𝒚] [𝒙] and let us denote by (𝑔 𝑖,𝑗 ) 1≤𝑖,𝑗 ≤𝛿 the matrix of 𝐿 𝑔 in the basis B. Then, for all 1 ≤ 𝑖, 𝑗 ≤ 𝛿, 𝑔 𝑖,𝑗 ∈ Q[𝒚] and deg(𝑔 𝑖,𝑗 ) ≤ deg(𝑔) +deg(𝑏 𝑗 ) -deg(𝑏 𝑖 ). Proof. We have for all 1 ≤ 𝑗 ≤ 𝛿, 𝑔𝑏 𝑗 = 𝛿 𝑖=1 𝑔 𝑖,𝑗 𝑏 𝑖 and 𝑔 𝑖,𝑗 ∈ Q[𝒚] by Lemma 3.5. Also, deg(𝑔𝑏 𝑗 ) = max deg(𝑔 𝑖,𝑗 𝑏 𝑖 ) because 𝑔 𝑖,𝑗 ∈ Q[𝒚] and the 𝑏 𝑖 's are distinct monomials in 𝒙. In particular, for all 1 ≤ 𝑖 ≤ 𝛿, deg(𝑔 𝑖,𝑗 𝑏 𝑖 ) = deg(𝑔 𝑖,𝑗 ) + deg(𝑏 𝑖 ) ≤ deg(𝑔𝑏 𝑗 ) ≤ deg(𝑔𝑏 𝑗 ) ≤ deg(𝑔) + deg(𝑏 𝑗 ) by Lemma 3.5. The result follows. □ Proposition 3.7. Under Assumption B, let 𝑔 ∈ Q[𝒚] [𝒙] and let us denote by (ℎ 𝑖,𝑗 ) 1≤𝑖,𝑗 ≤𝛿 the Hermite matrix H 𝑔 associated to (𝒇, 𝑔) in the basis B. Then, for all 1 ≤ 𝑖, 𝑗 ≤ 𝛿, ℎ 𝑖,𝑗 ∈ Q[𝒚] and deg(ℎ 𝑖,𝑗 ) ≤ deg(𝑔) + deg(𝑏 𝑖 ) + deg(𝑏 𝑗 ).

Definition 4 . 3 .

 43 Let Σ ⊆ {0, 1, -1} 𝑠 , we define Ada(Σ) ∈ {0, 1, 2} 𝑠 by induction on 𝑠 ≥ 1 as follows:

Algorithm 1 : 3 3

 13 One step of sign determinationInput : Q = {𝑄 } ∪ Q ′ , the sets Σ SIGN(Q ′ , 𝑍 ) and Ada(Σ), the associated matrix of signs Mat(Ada(Σ), Σ) Output : The sets SIGN(Q, 𝑍 ), Ada(SIGN(Q, 𝑍 )) and the associated matrix of signs1 Compute 𝑆 SIGN(𝑄, 𝑍 ) from the Tarski-queries TaQ(1, 𝑍 ), TaQ(𝑄, 𝑍 ), TaQ(𝑄 2 , 𝑍 ) by solving[START_REF] Basu | Algorithms in real algebraic geometry[END_REF]. 𝑆 corresponds to the nonzero entry of the solution 2 Deduce 𝐴 Ada(𝑆) from Definition 4.Compute the vector 𝑇 TaQ(Q 𝐴×Ada(Σ) , 𝑍 )4 𝑀 ← Mat(𝐴 × Ada(Σ), 𝑆 × Σ) = Mat(𝐴, 𝑆) ⊗ Mat(Ada(Σ), Σ)5 Compute 𝑐 𝑐 (𝑆 × Σ, 𝑍 ) by solving 𝑀 • 𝑐 = 𝑇 6 Deduce SIGN(Q, 𝑍 ) # given by the nonzero entries in 𝑐 7 Delete in 𝑀 the columns whose index is not in SIGN(Q, 𝑍 ) 8 Deduce Ada(SIGN(Q, 𝑍 )) from the row rank profile of 𝑀 and delete the other rows. Proposition 4.4. [2, Prop. 10.65] The set Ada(Σ) is adapted to Σ for sign determination.

Lemma 4 . 6 (

 46 See[START_REF] Basu | Algorithms in real algebraic geometry[END_REF] Lem. 10.66]). Let Σ ⊆ Γ ⊆ {0, 1, -1} 𝑠 and 𝑝 = ♯Σ. The matrix Mat(Ada(Σ), Σ) is the matrix obtained by extracting the first 𝑝 linearly independent rows of Mat(Ada(Γ), Σ).

Lemma 4 . 10 .

 410 Under the above assumptions, let 𝑔 be one of the 𝑔 𝑖 's, one can compute the matrix of multiplication 𝐿 𝑔 w.r.t. basis B within O T 𝑡,𝑑,𝜆 T 𝑑,𝑡,𝑛 + M 𝑛,𝑑 𝑑 𝜔𝑛 + 𝑛 𝜔+1 𝑑 𝜔𝑛+1 arithmetic operations in Q.

  Theorem 1.1. Let 𝒇 ⊂ Q[𝒚] [𝒙] be a regular sequence such that 𝒇 satisfies both Assumptions A and B. Let 𝔇 (2𝑠𝑑 + 𝑛(𝑑 -1))𝑑 𝑛 . There exists an algorithm which computes a solution to Problem 1 using

  Proposition 2.2. Let 𝐵 = (𝑏 1 , . . . , 𝑏 𝛿 ) be a basis of A K , 𝑔 ∈ A K , H and H 𝑔 be the matrices of Herm(𝒇, 1) and Herm(𝒇, 𝑔) w.r.t. 𝐵. Let 𝑀 = (𝑚 𝑖,𝑗 ) be the matrix of 𝐿 𝑔 w.r.t. 𝐵. Then, H 𝑔 = H𝑀.Proof. For 𝑝, 𝑞 ∈ A K , we have herm(𝒇, 𝑔)(𝑝, 𝑞) = Tr(𝐿 𝑔𝑝𝑞 ) = herm(𝒇, 1) (𝑝, 𝑔𝑞). Thus, it holds that (H 𝑔 ) 𝑖,𝑗 = herm(𝒇, 1)(𝑏 𝑖 , 𝑔𝑏 𝑗 ) = herm(𝒇, 1) 𝑏 𝑖 ,

			𝛿
			∑	𝑚 𝑘,𝑗 𝑏 𝑘
			𝑘=1
		𝛿
	=	∑	𝑚 𝑘,𝑗 H 𝑖,𝑘 = (H𝑀) 𝑖,𝑗 .	□
		𝑘=1
	2.2 Real root counting
	For now, we assume K = R or Q (or any ordered field). For 𝑟 ∈ K,
	sign(𝑟 ) is -1, 0 or 1 if 𝑟 < 0, 𝑟 = 0 or 𝑟 > 0 respectively.
	Definition 2.3 (Tarski-qery). Let 𝑍 be a finite set in K 𝑛 and
	𝑔 ∈ K[𝒙]. We define the Tarksi-query, TaQ(𝑔, 𝑍 ) of 𝑔 for 𝑍 by
	∑
	𝑥 ∈𝑍

  By[START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF] Lem. 4], as 𝒇 satisfies Assumption A, the ideal ⟨𝒇 ⟩ K generated by 𝒇 in K[𝒙] is zero-dimensional. Hence one can define Hermite's quadratic form Herm(𝒇, 𝑔) and compute a parametric Hermite matrix H 𝑔 ∈ K 𝛿 ×𝛿 representing Herm(𝒇, 𝑔) (once a basis

  1 , . . . , 𝑐 𝑘 ) is bounded by 𝑏 𝑟 𝑖 ) + deg(𝑏 𝑐 𝑖 )). Hence, the determinant of H 𝑔 has degree bounded by 𝛿 deg(𝑔) + 2 𝛿 𝑖=1 deg(𝑏 𝑖 ) and 𝛿 ≤ 𝑑 𝑛 . Proof. We have ℎ 𝑖,𝑗 = Tr(𝐿 𝑔𝑏 𝑖 𝑏 𝑗 ). Let 𝐶 = (𝑐 𝑘,ℓ ) 1≤𝑘,ℓ ≤𝛿 denote the entries of the matrix of 𝐿 𝑔𝑏 𝑖 𝑏 𝑗 w.r.t. B. By Lemma 3.6, as 𝑔𝑏 𝑖 𝑏 𝑗

		𝑘
	𝑘 deg(𝑔) +	∑	(deg(
		𝑖=1

  ]. By Lemma 3.6, deg(ℎ 𝑖,𝑗 ) ≤ max 𝑘 deg(𝑐 𝑘,𝑘 ) ≤ max 𝑘 deg(𝑔𝑏 𝑖 𝑏 𝑗 ). Therefore, deg(ℎ 𝑖,𝑗 ) ≤ deg(𝑔) + deg(𝑏 𝑖 ) + deg(𝑏 𝑗 ). The degree bound for the minors of H 𝑔 is clear by expanding the expression for determinants. □ Corollary 3.8. Assume that 𝒇 is an affine regular sequence satisfying B. For 𝑔 ∈ Q[𝒚] [𝒙], the degree of any minor of H 𝑔 is bounded by (deg(𝑔) + 𝑛(𝑑 -1))𝑑 𝑛 .Proof. Since 𝒇 is an affine regular sequence, one can apply[START_REF] Le | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF] Lem. 23]. Hence, the highest degree among the elements of B is bounded by 𝑛(𝑑 -1) and it holds that 2 𝛿 𝑖=1 deg(𝑏 𝑖 ) ≤ 𝑛(𝑑 -1)𝑑 𝑛 . Substituting these degree bounds on the 𝑏 𝑖 's in the ones of Proposition 3.7 ends the proof.

□

4 ALGORITHM

Let Q = (𝑄 1 , . . . , 𝑄 𝑠 ) ⊂ Q[𝑿 ] for 𝑿 = (𝑋 1 , . . . , 𝑋 𝑘 ). Let Z be a subset of R 𝑘 . We say that an element 𝜎 ∈ {0, 1, -1} 𝑠 is a sign condition for Q. A sign condition 𝜎 for Q is said to be realizable over Z if the following set is nonempty Reali(𝜎, Z) {𝑥 ∈ Z | 𝑠 𝑖=1

  ×𝛿 denotes the Hermite matrix associated to (𝒇, 𝑔) in B. We consider as in[START_REF] Ben-Or | The complexity of elementary algebra and geometry[END_REF], the algebraic setW ∞ = ∪ 𝑝 ∈G 𝑉 (lc 𝒙 (𝑝)) ⊂ C 𝑡 .Lemma 4.7. Let 𝑟 denotes the rank of H 𝑔 . There exists a Zariski dense subset U 𝑔 of GL 𝛿 (C) such that for 𝑈 ∈ U 𝑔 , the first 𝑟 leading principal minors of H 𝑈 𝑔 𝑈 𝑡 H 𝑔 𝑈 are not identically zero. Proof. The matrix H 𝑔 has rank 𝑟 so there exists 𝜂 ∈ R 𝑡 \ W ∞ such that the evaluation H 𝑔 (𝜂) is a matrix of rank 𝑟 . Moreover, for all 𝑈 ∈ GL 𝛿 (C), H 𝑈 𝑔 (𝜂) = 𝑈 𝑡 H 𝑔 (𝜂)𝑈 . We show that there exists a Zariski dense subset U 𝑔 such that for all 𝑈 ∈ U 𝑔 , the first 𝑟 leading principal minors of H 𝑈 𝑔 (𝜂) are nonzero. This would imply that the first 𝑟 leading principal minors of H 𝑈 𝑔 are not identically zero. For 1 ≤ 𝑗 ≤ 𝑟 , let us denote by M 𝑗 the set of all 𝑗 × 𝑗 minors of H 𝑔 (𝜂). We consider the matrix 𝑈 (𝔲 𝑖,𝑗 ) 1≤𝑖,𝑗 ≤𝛿 where 𝔲 = (𝔲 𝑖,𝑗 ) are new indeterminates. Then, the 𝑗-th leading principal minor 𝑀 𝑗 (𝔲) of the matrix H 𝑈 𝑔 (𝜂) can be written as 𝑀 𝑗 (𝔲) = ∑

𝑚∈ M 𝑗 𝑢 𝑚 • 𝑚, where the 𝑢 𝑚 's are elements of Q[𝔲]. As H 𝑔 (𝜂) is a real symmetric matrix of rank 𝑟 there exists a matrix 𝑄 ∈ GL 𝛿 (R) such that

  However, the set 𝐿 defined at line 14 contains Algorithm 2: Classification Input :-A polynomial sequence 𝒇 = (𝑓 1 , . . . , 𝑓 𝑝

𝑡 • H 𝒈 𝛼 𝑖 (𝜂) • 𝑈 are invariant when 𝜂 ranges over a connected component C of R. By Lemma 4.8, the vector 𝑇 𝜂 (Sign(H 𝒈 𝛼 𝑖 (𝜂))) 𝛼 ∈Ada * is invariant when 𝜂 varies over C.

  Ada(Σ) from the rank row profile of 𝑀 and delete the other rows 23 end 24 for 𝜂 ∈ 𝐿 do 25 Φ 𝜂 ← Sign pattern of (ℎ 𝛼 𝑗 (𝜂)) for 𝛼 ∈ Ada and 1 ≤ 𝑗 ≤ rk 𝛼 as in[START_REF] Bonnard | Determinantal sets, singularities and application to optimal control in medical imagery[END_REF]

	26

15 for 𝜂 ∈ 𝐿 do 16 𝑇 𝜂 ← Sign(H 𝒈 𝛼 𝑖 (𝜂)) 𝛼 ∈Ada 17 Solve 𝑀 • 𝑐 𝜂 = 𝑇 𝜂 to compute 𝑐 𝜂 18 Deduce Σ 𝜂 corresponding to nonzero entries in 𝑐 𝜂 19 end 20 Σ ← 𝜂 ∈𝐿 Σ 𝜂 21 Delete in 𝑀 columns whose index is not in Σ 22 Deduce Ada =

  Note that one can evaluate a multivariate polynomial of degree at most 𝐷 in 𝑘 variables within O (M 𝐷,𝑘 ) arithmetic operations.Let 𝒇 = (𝑓 1 , . . . , 𝑓 𝑝 ) ⊆ Q[𝒚] [𝒙] be a regular sequence satisfying Assumptions A and B and 𝒈

	𝑏,𝑐 =	𝑎 + 𝑏 + 𝑐 𝑎	and M 𝑎,𝑏 =	𝑎 + 𝑏 𝑎	.

  , this is done in time O 𝛿 2 T 𝑡,𝑑,𝜆 log 2 T 𝑡,𝑑,𝜆 log log T 𝑡,𝑑,𝜆 . Summing the cost of the two steps together ends the proof. □ Proposition 4.11. Suppose that 𝒇 = (𝑓 1 , . . . , 𝑓 𝑝 ) ⊂ Q[𝒚] [𝒙] is a regular sequence satisfying Assumptions A and B. Then any parametric Hermite matrix H 𝑔 occurring in Algorithm 2 with 𝑔 ∈ Q[𝒚] [𝒙] of degree 𝑑 𝑔 can be computed within O T 𝑡,𝑑 𝑔 ,2𝜆 𝑑 2𝑛 T 𝑡,𝑑 𝑔 ,2𝜆 + 𝑑 𝜔𝑛 (6) arithmetic operations in Q. Moreover, any minor of H 𝑔 can be computed using O M 𝑡,(𝑑 𝑔 +𝜆)𝑑 𝑛 𝑑 2𝑛 T 𝑡,𝑑 𝑔 ,2𝜆 + 𝑑 𝜔𝑛

  2, we compute parametric Hermite matrices H 𝒈 𝛼 , with 𝒈 𝛼 = 𝑔 𝛼 𝑖 𝑖 with 𝛼 ∈ {0, 1, 2} 𝑠 . So, the degree of 𝑔 is bounded by 2𝑑𝑠. Hence, the degree of any minor in Minors is bounded by 𝔇 (2𝑑𝑠 + 𝜆)𝑑 𝑛 . Let 𝑟 𝑖 be the size of Σ at the end of iteration 𝑖 of the loop. By [1], we have At iteration 𝑖, we compute at most 2𝑟 new Hermite matrices, so we add at most 2𝛿𝑟 new minors in the set Minors. Let 𝑀 𝑖 be the size of the set Minors after the loop iteration 𝑖. We have 𝑀 𝑖 ≤ 2𝛿𝑖𝑟 ≤ 2𝛿𝑠𝑟 . So we call the routine SamplePoints with at most 2𝑑 𝑛 𝑠𝑟 polynomials, because as 𝒇 satisfies Assumption B, we can omit 𝑤 ∞ = 1. By [21, Thm. 2], the set of sample points 𝐿 contains at most (4𝑑 𝑛 𝑠𝑟𝔇) 𝑡 points and this set can be computed using O M 𝑡,𝔇 (2𝑑 𝑛 𝑠𝑟 ) 𝑡 +1 2 3𝑡 𝔇 2𝑡 +1

	𝑟 𝑖 ≤ 𝑟	𝑠 𝑡	4

𝑡 +1 𝑑 (2𝑑 -1) 𝑛+𝑡 -1 .

Table 1 :

 1 Generic dense system

			Hermite		RF
	𝑛 𝑡 𝑠 𝑑	hm min det	sp	dv	cad	bp
	2 2 2 2 0.15 s 0.4 s 0.1 s	5 s	0.14 s	2 s	0.11 s
	2 2 3 2 0.7 s	2 s 0.1 s 10 s	0.9 s	10 s	1 s
	3 2 1 2 0.5 s	9 s 0.4 s 33 s	10 m	11 m	7 m
	3 2 2 2	3 s	1 m 0.4 s 57 s	10 m	13 m	14 m
	2 3 2 2 0.3 s	4 s 0.1 s 18m	0.7 s	>50 h	0.2 s
	3 3 1 2	1 s	4 m	6 s >50 h >50 h	>50 h	>50 h
	2 2 1 3 0.9 s 30 s 0.8 s	3m	52 m	57 m	47 s
	2 2 2 3	5 s	5 m	1 s	6m	57 m 1h 16 m 2 m