Huu Phuoc Le

Mohab Safey
email: mohab.safey@lip6.fr

El Din

FASTER ONE BLOCK QUANTIFIER ELIMINATION FOR REGULAR POLYNOMIAL SYSTEMS OF EQUATIONS

Keywords: Quantifier elimination, Effective real algebraic geometry, Polynomial system solving

Quantifier elimination over the reals is a central problem in computational real algebraic geometry, polynomial system solving and symbolic computation. Given a semi-algebraic formula (whose atoms are polynomial constraints) with quantifiers on some variables, it consists in computing a logically equivalent formula involving only unquantified variables. When there is no alternation of quantifiers, one has a one block quantifier elimination problem.

This paper studies a variant of the one block quantifier elimination in which we compute an almost equivalent formula of the input. We design a new probabilistic efficient algorithm for solving this variant when the input is a system of polynomial equations satisfying some regularity assumptions. When the input is generic, involves 𝑠 polynomials of degree bounded by 𝐷 with 𝑛 quantified variables and 𝑡 unquantified ones, we prove that this algorithm outputs semi-algebraic formulas of degree bounded by 𝒟 using 𝑂 ̃ ( (𝑛 -𝑠 + 1) 8 𝑡 𝒟 3𝑡+2 ( 𝑡+𝒟 𝑡 ) ) arithmetic operations in the ground field where 𝒟 = 2(𝑛 + 𝑠) 𝐷 𝑠 (𝐷 -1) 𝑛-𝑠+1 ( 𝑛 𝑠 ) . In practice, it allows us to solve quantifier elimination problems which are out of reach of the state-of-the-art (up to 8 variables).

This consists in computing a logically equivalent quantifier-free semi-algebraic formula Φ(𝑦), i.e. Φ is a finite disjunction of conjonctions of polynomial constraints in Q[𝑦] which is true if and only if the input quantified formula is true. The 𝑥 variables are called quantified variables and the 𝑦 variables are called parameters.

Let 𝜋 be the projection (𝑥, 𝑦) ↦ → 𝑦. Note that, geometrically, Φ describes the projection on the 𝑦-space of the real algebraic set 𝒱 R ⊂ R 𝑡 × R 𝑛 defined by simultaneous vanishing of the 𝑓𝑖's. In this paper, we focus on solving a variant of the classical one block quantifier elimination, which computes a semi-algebraic formula which defines a dense subset of the interior of 𝜋(𝒱 R ). Example 1. Consider the toy example 𝑥 2 + 𝑦 2 = 1. Its projection on the 𝑦 coordinate is described by the quantifierfree formula (𝑦 ≥ -1) ∧ (𝑦 ≤ 1) while for our variant quantifier elimination problem, an admissible output is (𝑦 > -1) ∧ (𝑦 < 1).

Except for proving theorems, this is sufficient for most of applications of quantifier elimination in engineering sciences or computing sciences where either the output formula only needs to define a sufficiently large subset of the 𝜋(𝒱 R ) or is evaluated with parameters's values which are subject to numerical noise.

Prior works. The real quantifier elimination is a fundamental problem in mathematical logic and computational real algebraic geometry. It naturally arises in many problems in diverse application areas. The works of Tarski and Seidenberg [START_REF] Tarski | A Decision Method for Elementary Algebra and Geometry[END_REF][START_REF] Seidenberg | A new decision method for elementary algebra[END_REF] imply that the projection of any semi-algebraic set is also semi-algebraic and give an algorithm, which is however not elementary recursive, to compute this projection. The Cylindrical Algebraic Decomposition (CAD) [START_REF] Collins | Quantifier elimination for real closed fields by cylindrical algebraic decomposition: a synopsis[END_REF] is the first effective algorithm for this problem whose complexity is doubly exponential in the number of indeterminates [START_REF] Davenport | Real quantifier elimination is doubly exponential[END_REF]. Since then, there have been extensive researches on developing this domain. We can name the CAD variants with improved projections [START_REF] Mccallum | An improved projection operation for Cylindrical Algebraic Decomposition of threedimensional space[END_REF][START_REF] Hong | An improvement of the projection operator in Cylindrical Algebraic Decomposition[END_REF][START_REF] Mccallum | On projection in CAD-based quantifier elimination with equational constraint[END_REF][START_REF] Brown | Improved projection for Cylindrical Algebraic Decomposition[END_REF] or the partial CAD [START_REF] Collins | Partial Cylindrical Algebraic Decomposition for quantifier elimination[END_REF]. Following the idea of [START_REF] Grigor'ev | Complexity of deciding Tarski algebra[END_REF] that exploits the block structure, [START_REF] Renegar | On the computational complexity and geometry of the first-order theory of the reals. Part III: Quantifier elimination[END_REF][START_REF] Basu | On the combinatorial and algebraic complexity of quantifier elimination[END_REF] introduced algorithms of only doubly exponential complexity in the order of quantifiers (number of blocks). For one-block quantifier elimination, the arithmetic complexity and the degree of polynomials in the output of these algorithms are of order 𝑠 𝑛+1 𝐷 𝑂 (𝑛𝑡) where 𝐷 is the bound on the degree of input polynomials (see [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Algo 14.6]). However, obtaining efficient implementations of these algorithms remains challenging. We also cite here some other works in real quantifier elimination [START_REF] Volker | The complexity of linear problems in fields[END_REF][START_REF] Sturm | Computational geometry problems in REDLOG[END_REF][START_REF] Weispfenning | A new approach to quantifier elimination for real algebra[END_REF][START_REF] Brown | Efficient preprocessing methods for quantifier elimination[END_REF][START_REF] Strzeboński | Cylindrical Algebraic Decomposition using validated numerics[END_REF] and applications to other fields [START_REF] Liska | Applying Quantifier Elimination to Stability Analysis of Difference Schemes[END_REF][START_REF] Anai | Reach set computations using real quantifier elimination[END_REF][START_REF] Sturm | Verification and synthesis using real quantifier elimination[END_REF].

In spite of this tremendous progress, many important applications stay out of reach of the state-of-the-art of the classic quantifier elimination. This motivates the researches on its variants. Generic quantifier elimination, in which the input and output formulas are equivalent for only almost every parameter, is studied in [START_REF] Dolzmann | A new approach for automatic theorem proving in real geometry[END_REF][START_REF] Seidl | A generic projection operator for partial cylindrical algebraic decomposition[END_REF]. A practically efficient algorithm is presented in [START_REF] Hong | Variant real quantifier elimination: Algorithm and application[END_REF][START_REF] Hong | Variant quantifier elimination[END_REF] for the same problem but under some assumptions on the input. The variant studied in this paper is a particular instance of the one in [START_REF] Hong | Variant real quantifier elimination: Algorithm and application[END_REF][START_REF] Hong | Variant quantifier elimination[END_REF].

Main results. In this paper, we consider the input 𝑓 = (𝑓1, . . . , 𝑓𝑠) satisfying the assumptions below.

Assumption A.

• The ideal of Q[𝑥, 𝑦] generated by 𝑓 is radical.

• The algebraic set 𝒱 ⊂ C 𝑡+𝑛 of 𝑓 is equi-dimensional of dimension 𝑑 + 𝑡. Its singular locus has dimension at most 𝑡 -1. Assumption B. The Zariski closure 𝜋(𝒱) of 𝜋(𝒱) is the whole parameter space C 𝑡 and 𝜋(𝒱 R ) is not of zero-measure in R 𝑡 .

The first result of the paper is a new probabilistic algorithm for solving the aforementioned variant of the quantifier elimination on such an input 𝑓 . Our algorithm applies the algorithm of [START_REF] Safey | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF] to the system 𝑓 considering Q(𝑦) as the based field. This allows to reduce our problem to zero-dimensional polynomial systems in Q(𝑦) [𝑥]. Next, we compute semi-algebraic formulas that describe approximate projections of these systems on the 𝑦-space through the algorithm of [START_REF] Phuoc | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]. This algorithm relies on a parametric variant of Hermite matrices for real root counting [START_REF] Pedersen | Counting real zeros in the multivariate case[END_REF][START_REF] Hermite | Sur le nombre des racines d'une équation algébrique comprises entre des limites données. extrait d'une lettre á m. borchardt[END_REF]. A similar outline is also presented in [START_REF] Weispfenning | A new approach to quantifier elimination for real algebra[END_REF][START_REF] Dolzomann | Generic hermitian quantifier elimination[END_REF], in which the author computes an expensive comprehensive Gröbner bases [START_REF] Volker | Comprehensive gröbner bases[END_REF] to analyze all cases before applying the real root counting algorithm of [START_REF] Pedersen | Counting real zeros in the multivariate case[END_REF]. The relaxation of the output allows us to replace this exhaustive computation by the real root finding algorithm of [START_REF] Safey | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF].

Our second goal is to analyze the complexity of this new algorithm. For generic inputs, we bound the degree of the outputs and establish an arithmetic complexity which depends on this bound. The precise notion of genericity is as follows.

Let Even though our complexity result has the same order as the one of [4, Algo 14.6], we obtain explicitly the degree bounds on the output formulas and the constant in the 𝑂 notation in the exponent.

C[𝑥, 𝑦] ≤𝐷 = {𝑝 ∈ C[𝑥, 𝑦] | deg(𝑝) ≤ 𝐷}. A
On the practical aspect, our implementation in MAPLE of this algorithm outperforms real quantifier elimination functions in MAPLE and MATHEMATICA. It allows us to solve examples, both generic and non-generic, that are out of reach of these softwares (up to 8 indeterminates). These timings are reported in Section 6.

Structure of the paper. In Section 2, we start by recalling some basic notions. In Section 3, we resume the algorithm for real root finding of [START_REF] Safey | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]. Also in the same section, we prove some auxiliary results in order to apply this algorithm parametrically. Next, we dedicate Section 4 for the description of our algorithm for solving the targeted problem and proving its correctness. The complexity of this algorithm is analyzed in Section 5. Finally, we report on some experimental results in Section 6.

Preliminaries

Algebraic sets and critical points. Let F be a subfield of C and 𝐹 ⊂ F[𝑥1, . . . , 𝑥𝑛]. The algebraic subset of C 𝑛 at which the elements of 𝐹 vanish is denoted by 𝑉 (𝐹 ). For an algebraic set 𝒱 ⊂ C 𝑛 , we denote by 𝐼(𝒱) ⊂ C[𝑥1, . . . , 𝑥𝑛] the radical ideal associated to 𝒱. The singular locus of 𝒱 is denoted by sing(𝒱). Given any subset 𝒮 of C 𝑛 , we denote by 𝒮 the Zariski closure of 𝒮, i.e., the smallest algebraic set containing 𝒮. An algebraic set 𝒱 is equi-dimensional if its irreducible components share the same dimension.

A map 𝜙 between two algebraic sets 𝒱 ⊂ C 𝑛 and 𝒲 ⊂ C 𝑖 is a polynomial map if there exist 𝜙1, . . . , 𝜙𝑖 ∈ C[𝑥1, . . . , 𝑥𝑛] such that 𝜙(𝜂) = (𝜙1(𝜂), . . . , 𝜙𝑖(𝜂)) for 𝜂 ∈ 𝒱. Let 𝒱 ⊂ C 𝑛 be an equi-dimensional algebraic set. We denote by crit(𝜙, 𝒱) the set of critical points of the restriction of 𝜙 to the non-singular locus of 𝒱. If 𝑐 is the codimension of 𝒱 and (𝑓1, . . . , 𝑓𝑠) generates the ideal 𝐼(𝒱), the subset of 𝒱 at which the Jacobian matrix jac(𝑓1, . . . , 𝑓𝑠, 𝜙1, . . . , 𝜙𝑖) of (𝑓1, . . . , 𝑓𝑠, 𝜙1, . . . , 𝜙𝑖) has rank less than or equal to 𝑐 is the union of crit(𝜙, 𝒱) and sing(𝒱) (see, e.g., [START_REF] Safey | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]Subsection 3.1]).

Gröbner bases and zero-dimensional ideals. Let F be a field and F be its algebraic closure. We fix an admissible monomial order ≻ (see [START_REF] Cox | Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF]Sec. 2.2]) over F [𝑥] where 𝑥 = (𝑥1, . . . , 𝑥𝑛). For 𝑝 ∈ F[𝑥], the leading monomial of 𝑝 with respect to ≻ is denoted by lm≻(𝑝).

A Gröbner basis 𝐺 of an ideal 𝐼 ⊂ F[𝑥] w.r.t. the order ≻ is a finite generating set of 𝐼 such that the set of leading monomials {lm≻(𝑔) | 𝑔 ∈ 𝐺} generates ⟨lm≻(𝑝) | 𝑝 ∈ 𝐼⟩. For 𝑝 ∈ F[𝑥], the remainder of the division of 𝑝 by 𝐺 using the order ≻ is uniquely defined and is called the normal form of 𝑝 w.r. Change of variables. Given a field F, we denote by GL(𝑛, F) the set of invertible matrices of size 𝑛 × 𝑛 with entries in F. Let 𝑝 ∈ F[𝑥] be a polynomial. For any 𝐴 ∈ GL(𝑛, F), we denote by 𝑝 𝐴 the polynomial 𝑝(𝐴

• 𝑥) ∈ F[𝑥]. For any algebraic set 𝑉 ⊂ F 𝑛 , 𝑉 𝐴 denotes the algebraic set {𝐴 -1 • 𝑥 | 𝑥 ∈ 𝑉 }.
For two blocks of indeterminates 𝑥 and 𝑦, we consider frequently the matrices that act only on the variables 𝑥 and leave 𝑦 invariant. Those matrices form a subset denoted by GL(𝑛, 𝑡, F) of GL(𝑛 + 𝑡, F).

3 Algorithm for real root finding

The 𝑆 2 algorithm

We recall the algorithm in [START_REF] Safey | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF], which we refer to as the 𝑆 2 algorithm, that computes at least one point per connected component of a smooth real algebraic set.

Let 𝑓 = (𝑓1, . . . , 𝑓𝑠) be a polynomial sequence in R[𝑥1, . . . , 𝑥𝑛]. For 1 ≤ 𝑖 ≤ 𝑑, let 𝜑𝑖 be the projection (𝑥1, . . . , 𝑥𝑛) → (𝑥1, . . . , 𝑥𝑖). When 𝑓 defines a smooth equi-dimensional algebraic set 𝒱 ⊂ C 𝑛 and generates a radical ideal, one can build a polynomial system using appropriate minors of jac(𝑓 ) to define crit(𝜑𝑖, 𝒱). Note that the critical loci are nested

crit(𝜑1, 𝒱) ⊂ crit(𝜑2, 𝒱) ⊂ • • • crit(𝜑 𝑑 , 𝒱) ⊂ crit(𝜑 𝑑+1 , 𝒱) = 𝒱.
Note also that in generic coordinates crit(𝜑𝑖, 𝒱) has expected dimension 𝑖 -1. The algorithm in [START_REF] Safey | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF] then exploits stronger properties of these critical loci under some genericity assumption on the coordinate system (which are satisfied through a generic linear change of coordinates).

Proposition 2. [30, Theorem 2] Assume that 𝑓 defines a smooth equi-dimensional algebraic set and generates a radical ideal.

Then, there exists a non-empty Zariski open set A 𝑓 ∈ GL(𝑛, C) such that for 𝐴 ∈ A 𝑓 the following holds:

• the restriction of 𝜑𝑖-1 to crit(𝜑𝑖, 𝒱 𝐴 ) is proper;

• the set crit(𝜑𝑖, 𝒱 𝐴 ) is either empty or of dimension 𝑖 -1 for 1 ≤ 𝑖 ≤ 𝑑 + 1.
The first item in Proposition 2 implies the second one. The index in the notation A 𝑓 indicates that the non-empty Zariski open set depends on 𝑓 . Algorithm 𝑆 2 considers fibers of the above critical loci with the convention 𝜋0 : 𝑥 → •. Proposition 2 is the cornerstone of the 𝑆 2 algorithm which can be derived from the following one. Proposition 3. [30, Theorem 2] Assume that 𝑓 defines a smooth equi-dimensional algebraic set and generates a radical ideal.

For 𝐴 ∈ A 𝑓 ∩ GL(𝑛, Q) as defined in Proposition 2 and 𝛼 = (𝛼1, . . . , 𝛼 𝑑 ) ∈ R 𝑑 , the union of the sets

crit(𝜑𝑖, 𝒱 𝐴 ) ∩ 𝜑 -1 𝑖-1 ((𝛼1, . . . , 𝛼𝑖-1)), 1 ≤ 𝑖 ≤ 𝑑 + 1
is finite and meets all connected components of 𝒱 ∩ R 𝑛 .

Example 4. Let 𝒱 be the smooth surface defined by 𝑥 2 1 -𝑥 2 2 -𝑥 2 3 = 1. The Jacobian matrix jac(𝑓 ) writes simply (2𝑥1, -2𝑥2, -2𝑥3). It turns out that the identity matrix lies in the set A defined in Proposition 2. Taking 𝛼 = (0, 0), we obtain 3 zero-dimensional systems:

• crit(𝜑1, 𝒱): {-2𝑥2, -2𝑥3, 𝑥 2 1 -𝑥 2 2 -𝑥 2 3 -1}, • crit(𝜑2, 𝒱) ∩ 𝜑 -1 1 (0): {-2𝑥3, 𝑥 2 1 -𝑥 2 2 -𝑥 2 3 -1, 𝑥1}, • 𝒱 ∩ 𝜑 -1 2 (0): {𝑥 2 1 -𝑥 2 2 -𝑥 2 3 -1, 𝑥1, 𝑥2}.
The first system admits two real solutions (1, 0, 0) and (-1, 0, 0). The other systems do not have any real solution.

The two points (1, 0, 0) and (-1, 0, 0) intersect the two connected components of 𝒱.

Of course, on general examples, one would need to perform a randomly chosen linear change of variables but this example illustrates already how 𝑆 2 works.

Parametric variant of 𝑆 2

We present now a parametric variant of 𝑆 2 . We let 𝑓 = (𝑓1, . . . , 𝑓𝑠) ⊂ Q[𝑦][𝑥] where 𝑦 = (𝑦1, . . . , 𝑦𝑡) are considered as parameters and 𝑥 = (𝑥1, . . . , 𝑥𝑛) are variables. The algebraic set defined by 𝑓 is denoted by 𝒱 ⊂ C 𝑡 × C 𝑛 . Let 𝜋 denote the projection (𝑥, 𝑦) ↦ → 𝑦 and 𝜋𝑖 denote the projection (𝑦, 𝑥) ↦ → (𝑦, 𝑥1, . . . , 𝑥𝑖).

Considering Q(𝑦) as the ground field, the parametric variant of 𝑆 2 computes on the input 𝑓 a list of finite subsets of Q[𝑦][𝑥], each of which generates a zero-dimensional ideal of Q(𝑦) [𝑥]. These subsets are basically

𝑓 𝐴 ∪ Δ 𝐴 𝑖 ∪ {𝑥1 -𝛼1, . . . , 𝑥𝑖-1 -𝛼𝑖-1}
, where (𝐴, 𝛼) is randomly chosen in GL(𝑛, 𝑡, Q) × Q 𝑛 and Δ 𝐴 𝑖 is the set of all (𝑛 -𝑑)-minors of the Jacobian matrix of 𝑓 𝐴 w.r.t. 𝑥𝑖, . . . , 𝑥𝑛.

The rest of this subsection is devoted to the auxiliary results that allow us to use the 𝑆 2 algorithm parametrically as above. 4 One-block QE algorithm

Description

In this subsection, we describe our algorithm for solving our variant of the quantifier elimination problem. The input is a polynomial sequence 𝑓 = (𝑓1, . . . , 𝑓𝑠) ⊂ Q[𝑥, 𝑦] satisfying Assumptions (A) and (B). Further, we denote by 𝑍(Ψ) the zero set of any semi-algebraic formula Ψ, i.e., 𝑍(Ψ) = {𝑦 ∈ R 𝑡 | Ψ(𝑦) is true}.

By Assumptions (A) and (B), the fiber dimension theorem [START_REF] Shafarevich | Basic Algebraic Geometry 1: Varieties in Projective Space[END_REF]Theorem 1.25] implies that there exists a nonempty Zariski open subset of C 𝑡 such that 𝜋 -1 (𝜂) has dimension 𝑑. The idea is to apply the parametric variant of 𝑆 2 with Q(𝑦) as a ground field.

More precisely, we start by picking randomly (𝐴, 𝛼) in GL(𝑛, 𝑡, Q) × Q 𝑛 and apply the change of variables 𝑥 ↦ → 𝐴 • 𝑥 to the input 𝑓 to obtain a new sequence 𝑓 𝐴 . As 𝐴 acts only on 𝑥, 𝜋(𝑉 (𝑓 𝐴 ) ∩ R 𝑛+𝑡 ) = 𝜋(𝒱 R ). Hence, a quantifier-free formula that solves our problem for 𝑓 𝐴 is also a solution of the same problem for 𝑓 .

Let jac 𝑥 (𝑓 𝐴 ) be the Jacobian matrix of 𝑓 𝐴 w.r.t. the variables 𝑥 = (𝑥1, . . . , 𝑥𝑛). We denote by 𝐽1, . . . , 𝐽𝑛 the columns of jac 𝑥 (𝑓 𝐴 ) respectively. For 1 ≤ 𝑖 ≤ 𝑑, let 𝑊 𝐴,𝛼 𝑖 be the union of 𝑓 𝐴 , all the (𝑛 -𝑑)-minors of the matrix consisting of the columns 𝐽𝑖+1, . . . , 𝐽𝑛 and {𝑥1 -𝛼1, . . . , 𝑥𝑖-1 -𝛼𝑖-1}. In particular, 𝑊 𝐴,𝛼 𝑑+1 denotes 𝑓 𝐴 ∪ {𝑥1 -𝛼1, . . . , 𝑥 𝑑 -𝛼 𝑑 }.

We prove later in Lemma 8 that, for generic (𝐴, 𝛼), the ideals of Q(𝑦)[𝑥] generated by 𝑊 𝐴,𝛼 𝑖 are radical and zero-dimensional.

We now solve the quantifier elimination problem for each of the polynomial sets 𝑊 𝐴,𝛼 𝑖 . For this step, we refer to a subroutine called RealRootClassification that takes as input a polynomial sequence 𝐹 ⊂ Q[𝑦][𝑥] such that the ideal of Q(𝑦)[𝑥] generated by 𝐹 is radical and zero-dimensional and computes a quantifier-free formula Φ𝐹 in 𝑦 such that 𝑍(Φ𝐹 ) is dense in the interior of 𝜋(𝑉 (𝐹 ) ∩ R 𝑛+𝑡 ). For this task, we refer to the algorithm of [START_REF] Phuoc | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]. We will explain the essential details of this subroutine later in Subsection 4.2.

Calling the subroutine RealRootClassification on the inputs 𝑊 𝐴,𝛼 𝑖 gives us the lists of semi-algebraic formulas Φ𝑖. Finally, we return Φ = ∨ 𝑑+1 𝑖=1 Φ𝑖 as the output of our algorithm. The pseudo-code below summarizes our algorithm, we introduce two additional subroutines:

• GenericDimension which takes the sequence 𝑓 and computes the dimension of the ideal generated by 𝑓 in Q(𝑦)[𝑥]. • (𝑛 -𝑑) Minors which takes as input a matrix 𝑀 whose coefficients are in Q[𝑥, 𝑦] and computes all of its (𝑛 -𝑑)-minors.

Real root classification

Now we explain the general ideas of the algorithm presented in [START_REF] Phuoc | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF] that is used in the RealRootClassification subroutine.

Let 𝐹 ⊂ Q[𝑦][𝑥] be a polynomial sequence such that the ideal ⟨𝐹 ⟩ generated by 𝐹 in Q(𝑦)[𝑥] is radical and zero-dimensional.

For such an input 𝐹 , RealRootClassification computes a semi-algebraic formula Φ𝐹 and a polynomial 𝑤∞ ∈ Q[𝑦] that satisfies:

Algorithm 1: One-block quantifier elimination

Input: 𝑓 ∈ Q[𝑦][𝑥] satisfying Assumptions (A) and (B). Output: A formula Φ s.t 𝑍(Φ) is dense in the interior of 𝜋(𝒱 R ). 1 Choose randomly (𝐴, 𝛼) ∈ GL(𝑛, Q) × Q 𝑛 2 𝑓 𝐴 ← 𝑓 (𝐴 • 𝑥) 3 [𝐽1, . . . , 𝐽𝑛] ← jac 𝑥 (𝑓 𝐴 ) 4 𝑑 ← GenericDimension(𝑓 𝐴 ) 5 for 1 ≤ 𝑖 ≤ 𝑑 + 1 do 6 𝑊 𝐴,𝛼 𝑖 ← (𝑛 -𝑑) Minors([𝐽𝑖+1, . . . , 𝐽𝑛]) ∪ {𝑓 𝐴 , 𝑥1 -𝛼1, . . . , 𝑥𝑖-1 -𝛼𝑖-1} 7 Φ𝑖 ← RealRootClassification(𝑊 𝐴,𝛼 𝑖 ) 8 return Φ ← ∨ 𝑑+1 𝑖=1 Φ𝑖 • 𝑍(Φ𝐹 ) ⊂ 𝜋(𝑉 (𝐹 ) ∩ R 𝑛+𝑡 ), • 𝑍(Φ𝐹 ) ∖ 𝑉 (𝑤∞) = 𝜋(𝑉 (𝐹 ) ∩ R 𝑛+𝑡 ) ∖ 𝑉 (𝑤∞).
The algorithm in [START_REF] Phuoc | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF] is based on constructing a symmetric matrix 𝐻𝐹 with entries in Q(𝑦) associated to 𝐹 . This matrix is basically a parametric version of the classical Hermite matrix for the ideal ⟨𝐹 ⟩ (see, e.g., [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]Chap. 4]), which provides the number of distinct real/complex solutions of the system 𝐹 (𝜂, •) through the signature/rank of the specialization of 𝐻𝐹 at 𝜂 [22, Corollary 17].

Let 𝐺𝐹 be the reduced Gröbner basis of the ideal in Q[𝑥, 𝑦] generated by 𝐹 w.r.t. the grevlex(𝑥) ≻ grevlex(𝑦) order. We consider the leading coefficients of the elements of 𝐺𝐹 in variables 𝑥 w.r.t. the grevlex(𝑥) order, which are polynomials in Q[𝑦]. Then, 𝑤𝐹 is taken as the square-free part of the product of these leading coefficients. The polynomial 𝑤𝐹 defines a proper algebraic subset of 𝑦-space over which the matrix 𝐻𝐹 does not have good specialization property [START_REF] Phuoc | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]Proposition 16]).

Next, we choose randomly a matrix 𝑄 ∈ GL(𝛿, Q). As the entries of 𝐻𝐹 lie in Q(𝑦), so do the leading principal minors 𝑀1, . . . , 𝑀 𝛿 of 𝑄 𝑇 • 𝐻𝐹 • 𝑄. Let 𝑚1, . . . , 𝑚 𝛿 be the numerators of those minors, which are in Q[𝑦]. A sufficiently generic matrix 𝑄 ensures that none of the 𝑚𝑖's is identically zero, hence allowing us to determine the signature of 𝐻𝐹 according to the signs of the 𝑚𝑖's. We then compute a finite set of points 𝐿 of Q 𝑡 that intersects every connected component of the semi-algebraic set defined by ∧ 𝛿 𝑖=1 (𝑚𝑖 ̸ = 0) ∧ (𝑤𝐹 ̸ = 0). Over those connected components, the polynomials 𝑚𝑖 are sign-invariant. Since the signature of 𝐻𝐹 (𝜂) can be deduced from the signs of the 𝑚𝑖(𝜂), the number of real solutions of 𝐹 (𝜂, •) is also invariant when 𝜂 varies in each connected component.

Let 𝐿0 = {𝜂 ∈ 𝐿 | 𝐹 (𝜂, •) admits at least one real solution} and

Φ𝐹 = ( ∨𝜂∈𝐿 0 ( ∧ 𝛿 𝑖=1 sign 𝑀𝑖 = sign 𝑀𝑖(𝜂) )) ∧ (𝑤𝐹 ̸ = 0).
Then, 𝑤∞ is taken as the product of the 𝑚𝑖's and 𝑤𝐹 . We return Φ𝐹 , 𝑤∞ as the output of RealRootClassification for 𝐹 . The correctness of this algorithm is given in [START_REF] Phuoc | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]Proposition 28].

In the pseudo-code below, we introduce the subroutines

• HermiteMatrix which takes as input a polynomial sequence • PrincipalMinors computes the leading principal minors of the matrix 𝑄 𝑇 • 𝐻𝐹 • 𝑄.

𝐹 ⊂ Q[𝑦][𝑥] such that the ideal ⟨𝐹 ⟩ ⊂ Q(𝑦)[𝑥] is zero-dimensional
• SamplePoints which takes as input a polynomial sequence 𝑚1, . . . , 𝑚 𝛿 , 𝑤𝐹 ∈ Q[𝑦] and computes a finite set of points that intersects every connected component of the semi-algebraic set defined by ∧ 𝛿 𝑖=1 𝑚𝑖 ̸ = 0 ∧ 𝑤𝐹 ̸ = 0. We describe such a subroutine in [START_REF] Phuoc | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]Sec. 3].

• Signature which evaluates the signature of a symmetric matrix of entries in Q.

We end this subsection by an example to illustrate our algorithm.

∪ 𝑑+1 𝑖=1 𝜋(𝑉 (𝑊 𝐴,𝛼 𝑖 ) ∩ R 𝑛+𝑡 ) ∖ 𝒲. We have that ∪ 𝑑+1 𝑖=1 𝜋(𝑉 (𝑊 𝐴,𝛼 𝑖 ) ∩ R 𝑛+𝑡 ) ∖ 𝒲 = ∪ 𝑑+1 𝑖=1 (𝜋(𝑉 (𝑊 𝐴,𝛼 𝑖 ) ∩ R 𝑛+𝑡 ) ∖ 𝒲) = ∪ 𝑑+1 𝑖=1 (𝑍(Φ𝑖) ∖ 𝒲) = (∪ 𝑑+1 𝑖=1 𝑍(Φ𝑖)) ∖ 𝒲.
Therefore, 𝑍(Φ) ∖ 𝒲 = 𝜋(𝒱 R ) ∖ 𝒲 and 𝜋(𝒱 R ) ∖ 𝑍(Φ) is of measure zero in R 𝑡 . By Assumption (B), we conclude that 𝑍(Φ) is a dense subset of the interior of 𝜋(𝒱 R ).

Complexity analysis

We now estimate the arithmetic complexity of Algorithm 1 once 𝐴 ∈ O ∩ GL(𝑛, 𝑡, Q) and 𝛼 ∈ X ∩ Q 𝑛 as in Proposition 6 are found from a random choice. In this section, the input 𝑓 forms a regular sequence of Q[𝑥, 𝑦] (then, 𝑠 = 𝑛 -𝑑) satisfying Assumptions (A) and (B). As the calls to RealRootClassification on the systems 𝑊 𝐴,𝛼 𝑖 are the most costly parts of our algorithm, we focus on estimating their complexities. To this end, we introduce the following assumption.

Assumption C. Let 𝐹 ⊂ Q[𝑥, 𝑦] and 𝐺 be the reduced Gröbner basis of 𝐹 w.r.t. the grevlex(𝑥) ≻ grevlex(𝑦) order. Then 𝐹 is said to satisfy Assumption (C) if and only if for any 𝑔 ∈ 𝐺, the total degree of 𝑔 in both 𝑥 and 𝑦 equals the degree of 𝑔 w.r.t. only 𝑥.

In [START_REF] Phuoc | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]Lemma 13], it is proven that, on an input 𝐹 satisfying Assumption (C), the polynomial 𝑤∞ in Real-RootClassification is simply 1 and the entries of the Hermite matrix 𝐻𝐹 are in Q[𝑦]. Therefore, the SamplePoints subroutine is called on the sequence of leading principal minors of the parametric Hermite matrices. Again, with Assumption (C), the degree of these leading principal minors can be bounded (see [START_REF] Phuoc | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]Lemma 32]). Therefore, one obtains the complexity bound for RealRootClassification for such 𝐹 .

Back to our problem, we will establish a degree bound for the polynomials given into SamplePoints. Some notations that will be used further are introduced below.

Let 𝐷 be a bound of the total degree of elements of 𝑓 . The zero-dimensional ideal of Q(𝑦) It remains to estimate the sum ∑ 𝑏∈𝐵 𝑖 deg(𝑏). A bound is obtained by simply taking the product of the highest degree appeared in 𝐵𝑖 and its cardinality. As the Hilbert series of Q(𝑦)[𝑥]/⟨𝑊 𝐴,𝛼 𝑖 ⟩ when 𝑓 is a generic system are known (see, e.g., [START_REF] Faugère | On the complexity of the generalized minrank problem[END_REF][START_REF] Spaenlehauer | On the complexity of computing critical points with Gröbner bases[END_REF]), explicit bounds of these quantities are easily obtained. Lemma 11. Let 𝐵𝑖 be defined as above. There exists a dense Zariski open subset Q of C[𝑥, 𝑦] 𝑠 ≤𝐷 such that, for 𝑓 ∈ Q, the following inequality holds for 1 ≤ 𝑖 ≤ 𝑑 + 1:

∑ 𝑏∈𝐵 𝑖 deg 𝑥 (𝑏) ≤ (𝑛 + 𝑠 -𝑖) 𝐷 𝑠 (𝐷 -1) 𝑛-𝑖-𝑠+2 ( 𝑛-𝑖+1 𝑠 ) .
Proof. By [26, Theorem 2.2], there exists a dense Zariski open subset Q1,1 ⊂ C[𝑥, 𝑦] 𝑠 ≤𝐷 such that for 𝑓 ∈ Q1,1, the degree of ⟨𝑊 𝐴,𝛼 1 ⟩, which equals to the cardinality of 𝐵1, is bounded by

𝐷 𝑠 ∑ 𝑛-𝑠 𝑘=0 ( 𝑘+𝑠-1 𝑠-1 ) (𝐷 -1) 𝑘 ≤ 𝐷 𝑠 (𝐷 -1) 𝑛-𝑠 ( 𝑛 𝑠 ) .
On the other hand, by [START_REF] Spaenlehauer | On the complexity of computing critical points with Gröbner bases[END_REF]Corollary 3.2], there exists a dense Zariski open subset Q1,2 ⊂ C[𝑥, 𝑦] 𝑠 ≤𝐷 such that for 𝑓 ∈ Q1,2, the witness degree, i.e., the highest degree appeared in the reduced Gröbner basis of 𝑊 𝐴,𝛼 1 w.r.t. grevlex(𝑥), is bounded by (𝑛+𝑠-1)𝐷-2𝑛+2. Thus, the highest degree in 𝐵1 is bounded by (𝑛+𝑠-1)𝐷-2𝑛+1. Thus, let Q1 = Q1,1 ∩ Q1,2 and, for 𝑓 ∈ Q1, we obtain

∑ 𝑏∈𝐵 1 deg(𝑏) ≤ (𝑛 + 𝑠 -1) 𝐷 𝑠 (𝐷 -1) 𝑛-𝑠+1 ( 𝑛 𝑠 ) .
For 1 ≤ 𝑖 ≤ 𝑑, the system 𝑊 𝐴,𝛼 𝑖 can also be interpreted as the system defining the critical locus of the projection (𝑥𝑖, . . . , 𝑥𝑛) ↦ → 𝑥𝑖 restricted to 𝑉 ( 𝑓 𝐴 (𝛼1, . . ) for each 𝑝 ∈ 𝐹 . Further, ⟨ ℎ 𝐹 ⟩ ℎ denotes the ideal of C[𝑥, 𝑦, 𝑦𝑡+1] generated by ℎ 𝐹 .

We consider the following property (C1): The leading terms appearing in the reduced Gröbner basis of ⟨ ℎ 𝐹 ⟩ ℎ w.r.t. grevlex(𝑥 ≻ 𝑦 ≻ 𝑦𝑡+1) do not involve any of the variables 𝑦1, . . . , 𝑦𝑡+1. By the proof of [START_REF] Phuoc | Solving parametric systems of polynomial equations over the reals through Hermite matrices[END_REF]Prop. 30], the property (C1) implies Assumption (C).

Following the proof of [2, Prop. 7], if 𝑦𝑗+1 is not a zero-divisor of the quotient ring C[𝑥, 𝑦, 𝑦𝑡+1]/⟨ ℎ 𝐹, 𝑦1, . . . , 𝑦𝑗⟩ ℎ for every 0 ≤ 𝑗 ≤ 𝑡, then 𝐹 satisfies the property (C1). This property means that (𝑦1, . . . , 𝑦𝑡+1) forms a regular sequence in the quotient ring C[𝑥, 𝑦, 𝑦𝑡+1]/⟨ ℎ 𝐹 ⟩ ℎ . We name this property as (C2).

Experiments

We compare the practical behavior of Algorithm 1 with QuantifierElimination (MAPLE's RegularChains) and Resolve (MATHEMATICA) on an Intel(R) Xeon(R) Gold 6244 3.60GHz machine of 754GB RAM. The timings are given in seconds (s.), minutes (m.) and hours (h.). The symbol ∞ means that the computation is stopped after 72 hours without getting the result. We use our MAPLE implementation for Hermite matrices, in which FGB package [START_REF] Faugère | FGb: A Library for Computing Gröbner Bases[END_REF] is used for Gröbner bases computation. The computation of sample points is done by RAGLIB [START_REF] Safey | Real alebraic geometry library[END_REF] which uses msolve [START_REF] Berthomieu | msolve: A Library for Solving Polynomial Systems[END_REF] for polynomial system solving.

For RealRootClassification, we use the following notations:

• HM: timings of computing Hermite matrices and their minors.

• SP: total timings of computing the sample points.

• SIZE: the largest size of the Hermite matrices.

• DEG: the highest degree appeared in the output formulas.

Start with random dense systems, we fix the total degree 𝐷 = 2 and run our algorithm for various (𝑡, 𝑛, 𝑠). In Table 1, SamplePoints accounts for the major part of our timings. While our algorithm can tackle these examples, neither MAPLE nor MATHEMATICA finish within 72h. The theoretical degree bound agrees with the practical observations. This agrees with our complexity result. On smaller problems, we observe that formulas computed by MAPLE and MATHEMATICA have larger degrees than our output. Hence, these implementations, based on CAD, suffer from its doubly exponential complexity while our implementation takes advantage of the singly exponential complexity of our algorithm. Table 2 shows the timings for sparse systems. Each polynomial is generated with 𝐷 = 2 and has 2𝑛 terms. Even Assumption (C) is not satisfied, our algorithm still applies. Thanks to the sparsity, the size and degree of the matrices in our algorithm are smaller than in the dense cases. Thus, our algorithm runs faster here than in Table 1

𝑡 𝑛 𝑠

1

 1 Introduction Problem statement. Let 𝑓 = (𝑓1, . . . , 𝑓𝑠) ⊂ Q[𝑦][𝑥] with 𝑥 = (𝑥1, . . . , 𝑥𝑛) and 𝑦 = (𝑦1, . . . , 𝑦𝑡). We aim at solving the following quantifier elimination problem over the reals ∃(𝑥1, . . . , 𝑥𝑛) ∈ R 𝑛 𝑓1(𝑥, 𝑦) = • • • = 𝑓𝑠(𝑥, 𝑦) = 0.

Lemma 5 .Proposition 6 .

 56 When Assumptions (A) and (B) hold, there exists a non-empty Zariski open subset B of C 𝑡 such that for every 𝜂 ∈ B, the specialization 𝑓 (𝜂, •) of 𝑓 at 𝜂 generates a radical equi-dimensional ideal whose algebraic set is either empty or has dimension 𝑑.Proof. Under Assumption (B), by the fiber dimension theorem[START_REF] Shafarevich | Basic Algebraic Geometry 1: Varieties in Projective Space[END_REF] Theorem 1.25], there exists a non-empty Zariski open subset B ′ of C 𝑡 such that 𝜋 -1 (𝜂) ∩ 𝒱 is an algebraic set of dimension 𝑑.Let 𝒲 denote the set of points of 𝒱 at which the Jacobian matrix jac 𝑥 (𝑓 ) of 𝑓 w.r.t. 𝑥 has rank at most 𝑛-𝑑-1. We note that 𝒲 = crit(𝜋, 𝒱) ∪ sing(𝒱). The algebraic version of Sard's theorem[START_REF] Safey | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF] Proposition B2] implies that 𝜋(crit(𝜋, 𝒱)) is contained in a proper Zariski closed subset of C 𝑡 . On the other hand, as Assumptions (A) hold, the dimension of 𝜋 (sing(𝒱)) is less than 𝑡. Thus, it is also contained in a proper Zariski closed subset of C 𝑡 . Hence, the Zariski closure of 𝜋(𝒲) is a proper Zariski closed subset of C 𝑡 . Let B be the intersection of the complement in C 𝑡 of this Zariski closure with B ′ . For 𝜂 ∈ B, the set {𝑥 ∈ C 𝑛 | 𝑓 (𝜂, 𝑥) = 0, rank jac 𝑥 (𝑓 )(𝜂) < 𝑛 -𝑑} is empty. Since the dimension of 𝜋 -1 (𝜂)∩𝒱 is 𝑑 and the Jacobian matrix jac 𝑥 (𝑓 )(𝜂, •) of 𝑓 (𝜂, •) w.r.t. the variables 𝑥 is of rank 𝑛 -𝑑 for every (𝜂, 𝑥) ∈ 𝒱 ∩ 𝜋 -1 (𝜂), the ideal 𝑓 (𝜂, •) is radical and defines a smooth and equi-dimensional set of dimension 𝑑 by Jacobian criterion [14, Theorem 16.19]. Lemma 5 shows that when specializing 𝑦 = (𝑦1, . . . , 𝑦𝑡) to a generic point 𝜂 ∈ B ∩ R 𝑡 in 𝑓 , one obtains 𝑓 (𝜂, •) satisfying the assumptions of Proposition 2. One could then apply Algorithm 𝑆 2 to 𝑓 (𝜂, •) to grab sample points in the real algebraic set it defines. However, proceeding this way would lead us to use a change of variables encoded by a matrix 𝐴 depending on 𝜂. The result below shows that choosing one generic change of variables will be valid for most of parameters' values. Assume that Assumptions (A) and (B) hold. There exists a dense Zariski open subset O of GL(𝑛, 𝑡, C) such that for every 𝐴 ∈ O ∩ GL(𝑛, 𝑡, Q) the following holds. There exists a dense Zariski open subset Y𝐴 of C 𝑡 such that Y𝐴 is a subset of the Zariski open set B in Lemma 5 and 𝐴 lies in the Zariski open set A 𝑓 (𝜂,.) defined in Proposition 2 for every 𝜂 ∈ Y𝐴.Proof. Let C(𝑦) denote the algebraic closure of C(𝑦). We consider C(𝑦) as the coefficient field. The proof of [30, Theorem 1] is purely algebraic and then is valid over the based field C(𝑦). Hence, there exists a non-empty Zariski open subset Õ of GL(𝑛, 𝑡, C(𝑦)) such that for 𝐴 ∈ Õ ∩ GL(𝑛, 𝑡, Q), the variables (𝑥1, . . . , 𝑥𝑖-1) is in Noether position w.r.t. the ideal in Q(𝑦)[𝑥] generated by 𝑓 𝐴 + Δ 𝐴 𝑖 for 1 ≤ 𝑖 ≤ 𝑑 + 1 where Δ 𝐴 𝑖 is the set of maximal minors of the truncated Jacobian matrix of jac(𝑓 𝐴 ) with all the partial derivatives w.r.t. 𝑦 and 𝑥𝑗 for 1 ≤ 𝑗 ≤ 𝑖 being removed (hence these minors are the ones defining crit(𝜋𝑖, 𝒱) ∪ sing(𝒱)). This is equivalent to the following. For 1 ≤ 𝑖 ≤ 𝑑 + 1, 𝑖 ≤ 𝑗 ≤ 𝑛, there exist the polynomials 𝑝𝑖,𝑗 ∈ Q(𝑦)[𝑥1, . . . , 𝑥𝑖-1, 𝑥𝑗] such that each 𝑝𝑖,𝑗 lies in the ideal of Q(𝑦)[𝑥] generated by 𝑓 𝐴 ∪ Δ 𝐴 𝑖 and it is monic when considering 𝑥𝑗 as the only variable (with the coefficients in Q(𝑦)[𝑥1, . . . , 𝑥𝑖-1]). The denominators of 𝑝𝑖,𝑗 are then polynomials in Q[𝑦]. We choose Y𝐴 to be the intersection of the nonempty Zariski open set B defined in Lemma 5 and the non-empty Zariski open set defined by the non-vanishing of all the denominators appeared in the 𝑝𝑖,𝑗's. Thus, for 𝜂 ̸ ∈ Y𝐴, 𝑝𝑖,𝑗(𝜂, •) ∈ Q[𝑥1, . . . , 𝑥𝑖-1, 𝑥𝑗] is monic in 𝑥𝑗. Consequently, (𝑥𝑖, . . . , 𝑥𝑛) is in Noether position w.r.t. the ideal of C[𝑥] generated by 𝑓 𝐴 (𝜂, •) ∪ Δ 𝐴 𝑖 (𝜂, •). Finally, taking O = Õ ∩ GL(𝑛, 𝑡, C), the conclusion follows.

  and computes the parametric Hermite matrix associated to 𝐹 w.r.t. the grevlex(𝑥) order. The description of this subroutine is given in [22, Algo. 2].

  [𝑥] generated by 𝑊 𝐴,𝛼 𝑖 is denoted by ⟨𝑊 𝐴,𝛼 𝑖 ⟩. The quotient ring Q(𝑦)[𝑥]/⟨𝑊 𝐴,𝛼 𝑖 ⟩ is a finite dimensional Q(𝑦)-vector space. Let 𝐺𝑖 be the reduced Gröbner basis of the ideal of Q[𝑥, 𝑦] generated by 𝑊 𝐴,𝛼 𝑖 w.r.t. grevlex(𝑥) ≻ grevlex(𝑦) and 𝐵𝑖 be the monomial basis of Q(𝑦)[𝑥]/⟨𝑊 𝐴,𝛼 𝑖 ⟩ constructed using 𝐺𝑖 as in Section 2. We begin with the following lemma. Lemma 10. When Assumption (C) holds for 𝑊 𝐴,𝛼 𝑖 , any leading principal minor of the matrix 𝐻𝑖 has degree bounded by 2 ∑ 𝑏∈𝐵 𝑖 deg(𝑏). Proof. The proof can be deduced from [22, Lemma 13, Proposition 31, Lemma 32]. It is mainly based on the control of degrees appearing in the normal form computation in Q(𝑦)[𝑥]/⟨𝑊 𝐴,𝛼 𝑖 ⟩.

From the proof of [ 35 , 1 ⟩ 1 ,

 3511 Lemma 2.1, Lemma 2.2] and [14, Proposition 18.13], there exists a dense Zariski open subset P1 ⊂ C[𝑥, 𝑦] 𝑠 ≤𝐷 such that for 𝑓 ∈ P1, there exists a dense Zariski open subset K 𝑓 ,1 ⊂ GL(𝑛, 𝑡, C) × C 𝑛 such that for (𝐴, 𝛼) ∈ K 𝑓 ,1 , the quotient ring C[𝑥, 𝑦, 𝑦𝑡+1]/⟨ ℎ 𝑊 𝐴,𝛼 ℎ is a Cohen-Macaulay ring of dimension 𝑡 + 1 and the ideal ⟨ ℎ 𝑊 𝐴,𝛼 𝑦1, . . . , 𝑦𝑡+1⟩ ℎ has dimension 0. By the unmixedness theorem [14, Corollary 18.14], (𝑦1, . . . , 𝑦𝑡+1) is a regular sequence over C[𝑥, 𝑦, 𝑦𝑡+1]/⟨ ℎ 𝑊 𝐴,𝛼 1 ⟩ ℎ . Thus, 𝑊 𝐴,𝛼 1 satisfies the property (C2) and Assumption (C) holds. Similar for 2 ≤ 𝑖 ≤ 𝑑 + 1, we obtain dense Zariski subsets P𝑖 ⊂ C[𝑥, 𝑦] 𝑠 ≤𝐷 and K 𝑓 ,𝑖 ⊂ GL(𝑛, 𝑡, C) × C 𝑛 for each 𝑓 ∈ P𝑖. Taking P = ∩ 𝑑+1 𝑖=1 P𝑖, and K 𝑓 = ∩ 𝑑+1 𝑖=1 K 𝑓 ,𝑖 , we conclude the proof. Proof of Theorem 1. It is well-known that Assumptions (A) and (B) are generic. Also, the set of regular sequences is dense in C[𝑥, 𝑦] 𝑠 ≤𝐷 . Thus, there exists a dense Zariski open subset R ⊂ C[𝑥, 𝑦] 𝑠 ≤𝐷 such that for any 𝑓 ∈ R, 𝑓 forms a regular sequence satisfying Assumptions (A) and (B). As 𝑉 (𝑓 ) has dimension 𝑑 + 𝑡 and 𝑓 forms a regular sequence in Q[𝑥, 𝑦], 𝑑 = 𝑛 -𝑠. Algorithm 1 consists of (𝑑 + 1) calls to RealRootClassification on 𝑊 𝐴,𝛼 𝑖 . Let P be the dense Zariski open set in Proposition 12 and Q = P ∩ R. Then, for 𝑓 ∈ Q, SamplePoints is called on a list of polynomials in Q[𝑦] of degree bounded by 𝒟. The number of principal minors is equal to the dimension of the quotient ring Q(𝑦)[𝑥]/⟨𝑊 𝐴,𝛼 𝑖 ⟩, which is also bounded by 𝒟. Applying [22, Theorem 2], each call to RealRootClassification on 𝑊 𝐴,𝛼 𝑖 costs at most 𝑂 ̃ ( 8 𝑡 𝒟 3𝑡+2 ( 𝑡+𝒟 𝑡 )) arithmetic operations in Q. In total, the arithmetic complexity of Algorithm 1 is bounded by 𝑂 ̃ ( (𝑛 -𝑠 + 1) 8 𝑡 𝒟 3𝑡+2 ( 𝑡+𝒟 𝑡 )) .

  property 𝑃 is said to be generic over C[𝑥, 𝑦] 𝑠 𝐷 if and only if there exists a non-empty Zariski open subset P ⊂ C[𝑥, 𝑦] 𝑠𝐷 such that the property 𝑃 holds for every 𝑓 ∈ P.Our complexity result is then stated below. The notation 𝑂 ̃(𝑔) means 𝑂(𝑔 log 𝜅 (𝑔)) for some 𝜅 > 0.

	𝑂 ̃	( (𝑛 -𝑠 + 1) 8 𝑡 𝒟 3𝑡+2 ( 𝑡+𝒟

Theorem 1. Let 𝒟 = 2(𝑛 + 𝑠) 𝐷 𝑠 (𝐷 -1) 𝑛-𝑠+1 ( 𝑛 𝑠 ) . There exists a non-empty Zariski open subset F of C[𝑥, 𝑦] 𝑠 ≤𝐷 and a probabilistic algorithm such that, for every 𝑓 ∈ F , this algorithm, in case of success, computes a semi-algebraic formula Φ defining a dense subset of the interior of 𝜋(𝑉 (𝑓 ) ∩ R 𝑡+𝑛 ) within 𝑡 )) arithmetic operations in Q and Φ involves only polynomials in Q[𝑦] of degree at most 𝒟.

  t. 𝐺. A polynomial 𝑝 is reduced by 𝐺 if 𝑝 equals to its normal form w.r.t. 𝐺. 𝑖 is proper at 𝛽 ∈ C 𝑖 if there exists a neighborhood 𝒪 of 𝛽 such that 𝜙 -1 (𝒪) is compact, where 𝒪 denotes the closure of 𝒪 in the Euclidean topology. If 𝜙 is proper everywhere on its image, we say that the map 𝜙 is proper. The properness is strongly related to the following notion of Noether normalization.Let F be a field and 𝐼 be an ideal of F[𝑥1, . . . , 𝑥𝑛]. The variables (𝑥𝑖+1, . . . , 𝑥𝑛) are in Noether position w.r.t. 𝐼 if their canonical images in the quotient algebra F[𝑥1, . . . , 𝑥𝑛]/𝐼 are algebraic integers over F[𝑥1, . . . , 𝑥𝑖] and F[𝑥1, . . . , 𝑥𝑖] ∩ 𝐼 = ⟨0⟩. Once F = C and the variables (𝑥𝑖+1, . . . , 𝑥𝑛) is in Noether position w.r.t. 𝐼, the projection of 𝑉 (𝐼) on (𝑥1, . . . , 𝑥𝑖) is proper.

	An ideal 𝐼 is said to be zero-dimensional if the algebraic set 𝑉 (𝐼) ⊂ F	𝑛 is finite and non-empty. When this
	holds, by [10, Sec. 5.3, Theorem 6], the quotient ring F[𝑥]/𝐼 is a F-vector space of finite dimension. The dimension
	of this vector space is also called the algebraic degree of 𝐼; it coincides with the number of points of 𝑉 (𝐼) counted
	with multiplicities [4, Sec. 4.5].

For any Gröbner basis of 𝐼, the set of monomials in 𝑥 which are irreducible by 𝐺 forms a monomial basis, denoted by 𝐵, of this vector space. For 𝑝 ∈ F[𝑥], the normal form of 𝑝 by 𝐺 can be interpreted as its image in F[𝑥]/𝐼 and is a F-linear combination of elements of 𝐵.

Properness & Noether normalization. A map 𝜙 : 𝑉 ↦ → C

  . , 𝛼𝑖-1, 𝑥𝑖, . . . , 𝑥𝑛) ) . Therefore, by replacing 𝑛 by 𝑛 -𝑖 + 1 in the above bound, we deduce that, for 1 ≤ 𝑖 ≤ 𝑑, there exists a dense Zariski open subset Q𝑖 ⊂ C[𝑥, 𝑦] 𝑠 ≤𝐷 such that ∑ 𝑏∈𝐵 𝑖 deg(𝑏) ≤ (𝑛 + 𝑠 -𝑖) 𝐷 𝑠 (𝐷 -1) 𝑛-𝑖-𝑠+2 ( 𝑛-𝑖+1 For 𝑖 = 𝑑 + 1, the cardinality of 𝐵 𝑑+1 is bounded by 𝐷 𝑠 and the highest degree in 𝐵 𝑑+1 is bounded by 𝑠(𝐷 -1). Thus, the bound holds for 𝑖 = 𝑑 + 1. Taking Q = ∩ 𝑑+1 𝑖=1 Q𝑖, we conclude the proof. Further, 𝒟 denotes 2(𝑛 + 𝑠 -1)𝐷 𝑠 (𝐷 -1) 𝑛-𝑠+1 ( 𝑛 Proposition 12. exists a dense Zariski open subset P ⊂ C[𝑥, 𝑦] 𝑠 ≤𝐷 such that, for every 𝑓 ∈ P, there exists a dense Zariski open subset K 𝑓 ⊂ GL(𝑛, 𝑡, C) × C 𝑛 such that for (𝐴, 𝛼) ∈ K 𝑓 , Assumption (C) holds for every system 𝑊 𝐴,𝛼 𝑖 . Proof. Let 𝑦𝑡+1 be a new variable and ℎ Q[𝑥, 𝑦, 𝑦𝑡+1]𝐷 be the set of homogeneous polynomials in Q[𝑥, 𝑦, 𝑦𝑡+1] of degree 𝐷. For 𝐹 ⊂ Q[𝑥, 𝑦], we denote by ℎ 𝐹 ⊂ Q[𝑥, 𝑦, 𝑦𝑡+1] the homogenization of 𝐹 w.r.t. all the variables (𝑥, 𝑦), that means ℎ 𝐹 = 𝑦 𝑦 𝑡+1 , . . . , 𝑥𝑛 𝑦 𝑡+1 , 𝑦 1 𝑦 𝑡+1 , . . . , 𝑦 𝑡

					𝑠	) .
	then prove Theorem 1.			𝑠	) . Now we show that Assumption (C) holds generically
	deg(𝑝) 𝑡+1	• 𝐹	(	𝑥 1	𝑦 𝑡+1

Table 1 :

 1 Generic systems with 𝐷 = 2

		HM	SP	SIZE	DEG	MAPLE	MATHEMATICA
	2 3 2	.2 s.	3 s.	8	24	∞	∞
	2 4 2	9 s.	1 m.	12	40	∞	∞
	2 5 2	2 m.	15 m.	16	56	∞	∞
	2 6 2 20 m. 2.5 h.	20	72	∞	∞
	2 7 2 1.5 h.	6 h.	24	88	∞	∞
	3 3 2	6 s.	1 m.	8	24	∞	∞
	3 4 2	5 m.	15 m.	12	40	∞	∞
	3 5 2	2 h.	5 h.	16	56	∞	∞
	3 6 2	8 h.	16 h.	20	72	∞	∞
	4 3 2	40 s.	30 m.	8	24	∞	∞
	4 4 2	6 h.	40 h.	12	40	∞	∞
	5 3 2	5 m.	14 h.	8	24	∞	∞

Table 2 :

 2 while these examples are out of reach of MAPLE and MATHEMATICA. Sparse systems with 𝐷 = 2

	𝑡 𝑛 𝑠	HM	SP	SIZE	DEG	MAPLE	MATHEMATICA
	3 3 2	3 s.	37 s.	7	22	∞	∞
	3 4 2 2 m. 10 m.	9	34	∞	∞
	3 5 2 2 m. 10 m.	9	32	∞	∞
	4 3 2 20 s. 20 m.	7	22	∞	∞
	4 4 2 15 s. 18 m.	5	20	∞	∞

Table 3

 3 gives the timings for structured systems. We separate the variables 𝑥 into blocks of total degree 1; [𝑖, 𝑛 -𝑖] means that the degree in [𝑥1, . . . , 𝑥𝑖] and [𝑥𝑖+1, . . . , 𝑥𝑛] are respectively 1. Here, entries of the Hermite matrices have non-trivial denominators with high degree. Computation those matrices takes the major part. However, our algorithm still outperforms the two other software.

	𝑡 𝑛 𝑠 Block	HM	SP	SIZE	DEG	MAPLE	MATHEMATICA
	3 3 2 [1, 2]	5 s.	45 s.	4	20	∞	∞
	3 4 2 [2, 2]	4 m.	1 m.	8	32	∞	∞
	3 5 2 [2, 3]	2 h.	9 m.	8	40	∞	∞
	3 6 2 [3, 3]	30 h. 45 m.	14	60	∞	∞

Table 3 :

 3 Structured systems

Huu Phuoc Le and Mohab Safey El Din are supported by the ANR grants ANR-18-CE33-0011 SESAME, and ANR-19-CE40-0018 DE RERUM NATURA, the joint ANR-FWF ANR-19-CE48-0015 ECARP project and the European Union's Horizon 2020 research and innovative training network program under the Marie Skłodowska-Curie grant agreement N°813211 (POEMA).

Applying the parametric variant of 𝑆 2 for 𝐴 = 𝐼3 and 𝛼 = (0, 0), we obtain 2 systems 𝑊1 = {2𝑦1𝑥2 + 𝑦2, 𝑓 } and 𝑊2 = {𝑓, 𝑥1}. Next, we call RealRootClassification on these systems, choosing 𝑄 = 𝐼2 to simplify the calculation. We obtain then 𝑤1,∞ = 𝑤2,∞ = 𝑦1 and the Hermite matrices:

) .

The sequences of leading principal minors are respectively [2, Δ/𝑦1] and [2, Δ/𝑦 2 1 ]. We compute then 4 points representing 4 connected components of the semi-algebraic set defined by 𝑦1 ̸ = 0 ∧ Δ ̸ = 0:

(1, 1/8, 0), (-1, 1/8, 0), (1, 1/8, 1/128), (-1, 1/8, -1/128).

The matrix 𝐻2 has non-zero signature over the first and second points, which both lead to the sign condition Δ > 0 ∧ 𝑦 2 1 > 0. Thus, we have Φ2 = (Δ > 0 ∧ 𝑦 2 1 > 0) ∧ (𝑦1 ̸ = 0). For 𝐻1, non-zero signatures are satisfied at the first and fourth points. Evaluating the sign of Δ and 𝑦1 at those points gives

The final output is therefore Φ = Φ1 ∨ Φ2, which is equivalent to

Correctness of Algorithm 1

We start by proving that the polynomial sequences 𝑊

Let Y𝐴 be the non-empty Zariski open subset of C 𝑡 in Proposition 6 (Y𝐴 depends on the matrix 𝐴). We denote 𝒲 = ∪ 𝑑+1 𝑖=1 𝑉 (𝑤𝑖,∞) ∪ (C 𝑡 ∖ Y𝐴).

We will show that, for 𝜂 ∈ 𝜋(𝒱 𝐴 R ) ∖ 𝒲, 𝜂 ∈ 𝑍(Φ). Since 𝜂 ∈ 𝜋(𝒱 𝐴 R ), 𝑉 (𝑓 𝐴 (𝜂, •)) ∩ R 𝑛 is not empty. On the other hand, as 𝜂 ∈ 𝒴𝐴, 𝑓 𝐴 (𝜂, •) generates a radical equi-dimensional ideal whose algebraic set is either empty or smooth of dimension 𝑑. By Proposition 3, 𝑉 (𝑓 𝐴 (𝜂, •)) ∩ R 𝑛 is not empty if and only if ∪ 𝑑+1 𝑖=1 𝑉 (𝑊 𝐴,𝛼 𝑖 (𝜂) ∩ R 𝑛 ) is not empty either. We deduce that 𝜂 ∈


Georges Calas
email: georges.calas@sorbonne-universite.fr

Laurence Galoisy

Alexis Geisler

SODIUM NANOPARTICLES IN ALKALI HALIDE MINERALS: WHY IS VILLIAUMITE RED AND HALITE BLUE?

Keywords: villiaumite, halite, fluorite, peralkaline rocks, color, radiation damage, UV-visible spectroscopy, nanoparticles

The presence of metal Na nanoparticles causes the bright, thermally unstable colors of villiaumite, NaF, and halite, NaCl. These nanoparticles have been suspected since a long time to be caused by external irradiation. Metal nanoparticles, often referred to as metal colloids, cause surface plasmon resonance effects, characterized by a single Lorentzian-shaped absorption band.

The color of these minerals is due to metal Na nanoparticles of 2.5-3 nm. A key point is that the resonance wavelength, which corresponds to the maximum of the absorption band, is inversely related to the value of the refractive index of the embedding mineral. This causes the position of the main absorption band to be offset downwards by 140 nm in halite relative to villiaumite. As a consequence, the optical transmission window is shifted from the long to the short wavelength domain, explaining the color of blue halite and red villiaumite, respectively. Similar refractive index dependence may explain the purple color of fluorite, caused by metallic Ca nanoparticles.

Finally, the origin of the villiaumite irradiation may be the presence of Th-rich (about 8.8wt%

ThO 2 ) nano-inclusions, about 500 nm large, illustrating the specific geochemistry of peralkaline rocks where villiaumite is found.

INTRODUCTION

One of the outstanding properties of alkali halides is their optical transparency from the vacuum UV to the far infrared. Though they are intrinsically colorless, they sometimes show a thermally unstable coloration, which, in the absence of chemical impurities, has long been recognized to result from radiation damage (e.g., [START_REF] Przibram | Verfärbung und Lumineszenz[END_REF][START_REF] Stormer | Villiaumite and the occurrence of fluoride minerals in igneous rocks[END_REF].

The simplest radiation-induced defect is the so-called F center, i.e. an electron trapped in an anion vacancy. The F center creates a singly occupied electronic level in the band gap, which colors the crystal. The aggregation of two or three F centers on nearest neighbor sites, gives rise to binary M-and ternary R-centers, respectively. Eventually, color centers aggregate to form metallic alkali nanoparticles, also referred to as colloids, caused by an irradiation at room temperature or higher temperatures (see e.g., [START_REF] Schwartz | Effect of electronic energy loss and irradiation temperature on color-center creation in LiF and NaCl crystals irradiated with swift heavy ions[END_REF]. Optical properties of metal nanoparticles have unique characteristics that give rise to brilliant colors. For instance, during external irradiation of synthetic halite, the change from a yellow color due to F-centers to a bright blue color indicates the formation of Na metal nanoparticles [START_REF] Kreibig | Optical properties of metal clusters[END_REF].

Natural halite, NaCl, presents various radiation-induced colors (Zelek et al., 2015), but blue hues with a broad range of saturation are the most frequent (Supplemental Figure 1). The blue color has been assigned to colloidal Na metal formed by irradiation with ionizing radiation [START_REF] Rossman | Mineral spectroscopy server[END_REF]. Radiation defects in halite provide information on the sedimentary history of salt deposits [START_REF] Sonnenfeld | The color of rock salt -a review[END_REF][START_REF] Zelek | Lattice deformation of blue halite from Zechstein evaporate basin: Klodawa Salt Mine, Central Poland[END_REF]2015) or the stability of nuclear waste repositories [START_REF] Levy | Radiation damage studies on synthetic NaCl crystals and natural rock salt for radioactive waste disposal applications[END_REF]. Recently, they have been used to assess the exposure duration of the surface of icy moons [START_REF] Poston | Spectral behavior of irradiated sodium chloride crystals under Europa-like conditions[END_REF] and ordinary chondrites [START_REF] Chan | Organic matter in extraterrestrial water-bearing salt crystals[END_REF], subject to cosmic radiation. Villiaumite, NaF, is an accessory phase formed during a late pegmatitic stage associated with peralkaline nepheline syenites [START_REF] Stormer | Villiaumite and the occurrence of fluoride minerals in igneous rocks[END_REF][START_REF] Marks | A global review on agpaitic rocks[END_REF]. It is generally characterized by its intense carmine red color (Supplemental Figure S2).

The origin of the red color of natural villiaumite has not yet been investigated, though it is suspected to arise from radiation damage [START_REF] Rossman | Mineral spectroscopy server[END_REF]. By contrast, blue halite received much attention, with pioneering studies on samples from Strassfurt, Germany [START_REF] Przibram | Verfärbung und Lumineszenz[END_REF][START_REF] Doyle | Coagulation, optical absorption and photoconductivity of colloid centres in alkali halides[END_REF][START_REF] Howard | Blue halite[END_REF][START_REF] Arun | Ion beam radiation effects on natural halite crystals[END_REF] and, more recently, Kłodawa, Poland [START_REF] Wesełucha-Birczynska | Blue halite colour centre aggregates studied by micro-Raman spectroscopy and X-ray diffraction[END_REF]Zelek et al., 2014 and 015) and Morleben, Germany [START_REF] Arun | Ion beam radiation effects on natural halite crystals[END_REF] salt mines. This study shows that the red color of villiaumite is a result of a surface plasmon resonance [START_REF] Kreibig | Optical properties of metal clusters[END_REF] due to Na metal nanoparticles. The optical spectra of blue halite have a similar origin. The outstanding color change between blue halite and red villiaumite is rationalized in terms of the dependence of the wavelength resonance of the nanoparticles on the refractive index of the embedding mineral. The same formalism may be extended to explain the origin of the purple color of fluorite, due to the presence of calcium metallic nanoparticles. The origin of the villiaumite irradiation may be the presence of Th-rich (about 8.8wt% ThO 2 ) nano-inclusions, about 500 nm large, illustrating the geochemistry of peralkaline rocks where villiaumite is found.

MATERIALS AND METHODS

Villiaumite crystals come from the agpaitic suite of nepheline syenites of the type locality of the Los Archipelago, Guinea [START_REF] Lacroix | Sur l'existence du fluorure de sodium cristallisé comme élément des syénites néphéliniques des îles de Los[END_REF][START_REF] Moreau | The Los Archipelago nepheline syenite ring-structure: a magmatic marker of the evolution of the Central and Equatorial Atlantic[END_REF]. A sedimentary navy blue halite from Strassfurt (Germany) was used for comparison. Optical absorption spectra were measured at room temperature and at 10K in the spectral range 200-3300 nm (50,000 cm -1 -3,030 cm -1 ), using a double-beam computerized Perkin-Elmer Lambda 1050 UV-Visible-NIR spectrophotometer. The spectral resolution varies from 0.8 nm in the UV region to 2 nm in the near IR -visible region. A He-cryostat under vacuum (around 3.4 × 10 -7 mbar) was used to record spectra at 10 K. The optical absorption spectra were obtained in transmission mode on cleaved crystals (Supplemental Figure S3). The spectra were normalized to sample thickness and background corrected using a polynomial function. The data are presented and analyzed as a function of wavelength, as the absorption is caused by surface plasmon resonance effects interpreted in terms of the Mie theory (see e.g., [START_REF] Kreibig | Optical properties of metal clusters[END_REF]. Preliminary scanning electron microscopy with field emission gun (SEM-FEG) analyses were obtained at 15 kV and a beam current of 200 nA with a Zeiss Ultra 55 instrument fitted with a high-resolution Schottky FEG and a UHR Gemini® column. Semi-quantitative analyses were performed using a Bruker Quantax XFlash 4010 energy-dispersive X-ray spectrometer.

RESULTS AND DISCUSSION

Optical absorption spectra of villiaumite

The samples investigated present an intense red color, which disappears in a couple of minutes at 500 °C and after 2 hrs at 400°C. The room temperature optical absorption spectrum (Supplemental Figure S4) shows the presence of a background due to light scattering by inclusions and fractures that result from the easy {100} cleavage of this cubic mineral. After subtracting this background contribution, the most salient feature is an intense absorption band at 494 nm. The two other contributions are a shoulder near 415 nm and a small band at 328 nm (Figure 1a). This spectrum is similar to the one of villiaumite from Mont Saint Hilaire, Canada [START_REF] Rossman | Mineral spectroscopy server[END_REF], which is dominated by a main absorption band peaking at 510 nm.

The optical absorption spectra have been fitted using a minimum of components, chosen to correspond to spectroscopic events. Gaussian and Lorentzian lineshapes of the spectral components have been tested. Indeed, by contrast to the Gaussian shape of absorption bands caused by color centers (see e.g. Jenkins et al., 2000;[START_REF] Hoya | Ab initio study of F-centers in alkali halides[END_REF], surface plasmon resonances exhibited by metallic nanoparticles give rise to Lorentzian-shaped absorption bands, as predicted by Mie theory [START_REF] Kreibig | Optical properties of metal clusters[END_REF][START_REF] Weerkamp | Radiation damage in NaCl. I. Optical-absorption experiments on heavily irradiated samples[END_REF][START_REF] Ruiz-Fuertes | Reversible tuning of Ca nanoparticles embedded in a superionic CaF 2 matrix[END_REF]. A good fit of the main band is achieved by using a Lorentzian function peaking at 494 nm.

The full width at half-maximum (FWHM) of this band, 86 nm, is larger than that of the other contributions due to color centers. This Lorentzian lineshape explains the presence of a long tail extending towards long wavelengths, at the origin of the intense red hue of villiaumite. Such a Lorentzian line-shape characterizes the optical spectra of free neutral Na clusters [START_REF] Selby | Photoabsorption spectra of sodium clusters[END_REF], Na nanoparticles in NaCl [START_REF] Weerkamp | Radiation damage in NaCl. I. Optical-absorption experiments on heavily irradiated samples[END_REF] and NaF [START_REF] Seifert | The influence of defects and defect clusters on alkali atom desorption stimulated by low energy electron bombardment of alkali halides[END_REF] or Ca nanoparticles in CaF 2 [START_REF] Ruiz-Fuertes | Reversible tuning of Ca nanoparticles embedded in a superionic CaF 2 matrix[END_REF]Ryskin et al., 2020).

The two minor contributions at 328 nm and 414 nm have a Gaussian lineshape. The former corresponds to a F-center, widely investigated in synthetic NaF [START_REF] Seifert | The influence of defects and defect clusters on alkali atom desorption stimulated by low energy electron bombardment of alkali halides[END_REF][START_REF] Tiwald | Ab initio perspective on the Mollwo-Ivey relation for F centers in alkali halides[END_REF][START_REF] Hoya | Ab initio study of F-centers in alkali halides[END_REF]. The latter may be assigned to a R-center (Amenu- [START_REF] Amenu-Kpodo | Color centers in sodium fluoride[END_REF][START_REF] Bryukvina | Formation and properties of metallic nanoparticles in lithium and sodium fluorides with radiation-induced color centers[END_REF][START_REF] Bryukvina | Relationships between lithium and sodium nanoparticles and color centers formation in LiF and NaF crystals with hydroxide and magnesium ions impurities[END_REF]. Recent ab-initio calculations [START_REF] Tiwald | Ab initio perspective on the Mollwo-Ivey relation for F centers in alkali halides[END_REF][START_REF] Hoya | Ab initio study of F-centers in alkali halides[END_REF] have shown that the absorption energy E a of the F-center (in eV) may be approximated by: E a = 16.5 a -1. 76 (1)

where a is the anion-cation distance. Relation (1) gives a physical ground to the classical empirical Mollwo-Ivey relation [START_REF] Ivey | Spectral location of the absorption due to color centers in alkali halide crystals[END_REF]. The predicted values, 345 ands 415 nm, are in good agreement with the experimental values, 328 and 414 nm. In the optical absorption spectrum of villiaumite from Mont Saint Hilaire, Canada [START_REF] Rossman | Mineral spectroscopy server[END_REF], the main absorption band at 510 nm shows a slightly different lineshape and additional weak contributions around 400 nm. As in natural blue halite (Zelek et al., 2015), the relative proportion of isolated defect centers and metallic nanoparticles may vary among the samples.

Evidence of a plasmon resonance in villiaumite

As indicated above, a Lorentzian lineshape is consistent with a surface plasmon resonance.

The position of this resonance is similar to that in synthetic NaF [START_REF] Chandra | Taxonomy of F-aggregate centers in NaF[END_REF][START_REF] Bryukvina | Formation and properties of metallic nanoparticles in lithium and sodium fluorides with radiation-induced color centers[END_REF][START_REF] Bryukvina | Relationships between lithium and sodium nanoparticles and color centers formation in LiF and NaF crystals with hydroxide and magnesium ions impurities[END_REF]. The resonance wavelength may be predicted from the Mie theory by considering spherical metal particles [START_REF] Doyle | Absorption of light by colloids in alkali halide crystals[END_REF][START_REF] Hunault | Nondestructive redox quantification reveals glassmaking of rare French gothic stained glasses[END_REF]. In this approximation, the average size of the nanoparticles is derived from:

R = V f λ p 2 /(2πcΔλ) ( 2
)
where R is the average radius of the metallic clusters, V f is the Fermi velocity of the electrons in the bulk metal (for Na, V f = 1.07 × 10 6 m.s -1 ), λ p is the characteristic wavelength at which the surface plasmon resonance (SPR) occurs, Δλ is the full width at half-maximum and c is the speed of light. This predicts an average diameter of Na nanoparticles slightly smaller than 3 nm. At 10 K, this absorption band only slightly shifts by about 10 nm towards higher wavenumbers, without any narrowing. This is consistent with an assignment to a surface plasmon resonance, which does not change in energy or amplitude with temperature, by contrast to the transitions related to color centers [START_REF] Kreibig | Optical properties of metal clusters[END_REF].

Color centers in alkali halides have a limited thermal stability above room temperature relative to Na colloids, [START_REF] Schwartz | Effect of electronic energy loss and irradiation temperature on color-center creation in LiF and NaCl crystals irradiated with swift heavy ions[END_REF]. This explains why, in the geological samples, a plasmon resonance is predominant over the electronic transitions expected from these color centers.

Similar mechanisms have been observed in glasses where alkali ions can act as electron traps upon irradiation and form metal colloids [START_REF] Boizot | Migration and segregation of sodium under β-irradiation in nuclear glasses[END_REF]. Such processes are thermally activated and demonstrate that alkali ions agglomerate to form bigger complexes after trapping electrons at temperatures reaching a few hundreds °C.

Comparison with halite

The shape of the optical absorption spectrum of blue halite from Stassfurt is similar to some of the blue halites above mentioned. It is almost identical to the first absorption spectra published on blue halite (also from Stassfurt: Doyle, 1960) (Supplemental Figure S5). The main absorption band peaks at 640 nm, the same value as reported by previous authors (e.g., [START_REF] Doyle | Coagulation, optical absorption and photoconductivity of colloid centres in alkali halides[END_REF][START_REF] Howard | Blue halite[END_REF]. Using several Gaussian-Lorentzian spectral components, assigned to Na colloids and various color centers, gives a good fit [START_REF] Zelek | Lattice deformation of blue halite from Zechstein evaporate basin: Klodawa Salt Mine, Central Poland[END_REF]2015). However, fitting the spectra is non equivocal. Here, we use a minimum number of spectral components, as for villiaumite. The main band, at 640 nm, is fitted with a single Lorentzian component (Fig. 1b), because it arises from a surface plasmon resonance of Na nanoparticles (e.g., [START_REF] Weerkamp | Radiation damage in NaCl. I. Optical-absorption experiments on heavily irradiated samples[END_REF].

The FWHM, 105 nm, is similar to the values found in the Klodawa mine (Wesełucha-irc s a et al., 2012) and larger than in villiaumite (86 nm) . Minor additional Gaussian-shape contributions at 430, 531 and 744 nm may be assigned to F-, R-(3 neighboring F-centers) and M

(2 neighboring F-centers) color centers, respectively. The actual position of these bands is shifted relative to that expected from relation (1), at 473, 550 and 705 nm for the F-, R-and M-centers-, respectively. The same centers are found in the halite from Klodawa mine and a similar discrepancy with the Mollwo-Ivey relation is observed (Wesełucha-irc s a et al., 2012).

Finally, a fourth minor Gaussian contribution occurs at 385 nm as in other natural halites ( o le, Wesełucha-irc s a et al., 2012), but its origin is unclear.

Scaling the spectra of red villiaumite and blue halite

The halite spectrum presents similarities with that of villiaumite, but occurs at larger wavelengths. As a consequence, the transmission window does not occur in the same spectral region, being located on the long or short wavelength side of the main band in red villiaumite and blue halite, respectively (Figures 1a and1b). This explains the difference in the color of these minerals, despite both show a broad Lorentzian shape plasmon resonance with spectral properties independent of temperature, which is assigned to the presence of Na nanoparticles. For spherical particles that are smaller than the wavelength of light, the value of the resonance wavelength depends on the refractive index of the surroundings [START_REF] Kreibig | Optical properties of metal clusters[END_REF]. The wavelength of maximum absorption  max may be predicted within the Mie theory, following the Doyle relation [START_REF] Doyle | Absorption of light by colloids in alkali halide crystals[END_REF][START_REF] Davenas | Correlation between absorption bands and implanted alkali ions in LiF[END_REF][START_REF] Seifert | The influence of defects and defect clusters on alkali atom desorption stimulated by low energy electron bombardment of alkali halides[END_REF]:

 max = c (1+2n 0 2 ) 1/2 (3)
where n 0 is the refractive index of the host medium and  c is the critical wavelength for the onset of ultra-violet transparency of sodium. The ratio between the  max values in villiaumite and halite, allows elimination of the  c term. The ratio calculated from the refractive index of these minerals is 1.13 to compare to an experimental value of 1.29. This explains qualitatively the redshift of the plasmon band with the increasing refractive index of the mineral. The underestimation of this shift when using relation (3) may come from non-spherical shape effects or size distribution of the Na colloids in geological samples with a complex histor relative to laborator samples…

IMPLICATIONS

The comparison of the optical absorption spectra of halite and villiaumite provides a nice illustration of Mie theory, through the dramatic influence of the refractive index of halides on the energy of the plasmon resonance of the embedded metal nanoparticles. Temperatures up to 300-500°C (Zelek et al., 2015;[START_REF] Weerkamp | Radiation damage in NaCl. I. Optical-absorption experiments on heavily irradiated samples[END_REF], crystal dislocations and substituted impurities favor the aggregation of color centers leading to the formation of Na colloids. This explains the predominance of these colloids in natural halides [START_REF] Seifert | The influence of defects and defect clusters on alkali atom desorption stimulated by low energy electron bombardment of alkali halides[END_REF], as demonstrated by their bright colors. The formation of Na colloids goes with that of free dihalogen molecules, as in the villiaumite from Kola Peninsula, Russia [START_REF] Celinski | Trace determination and pressure estimation of fluorine F 2 caused by irradiation damage in minerals and synthetic fluorides[END_REF] and can only occur once the crystal cooled down to avoid the annealing of these colloids. It is of interest that natural purple fluorites also owe their color to the presence of Ca nanoparticles. Their optical absorption spectra show an intense, broad absorption band near 560 nm that has been suggested to come from Ca metal colloids (Bill and Calas, 1983;[START_REF] Rossman | Mineral spectroscopy server[END_REF][START_REF] Gaft | Red photoluminescence and purple color of naturally irradiated fluorite[END_REF]Ryskin et al., 2020). The same band is found in additively colored synthetic CaF 2 [START_REF] Angervaks | Optical study of calcium precipitates in additively colored CaF 2 crystals[END_REF]. This absorption band has a Lorentzian shape, which indicates a plasmon resonance origin (Ryskin et al., 2020). Its position, near 560 nm, is intermediate between that in red villiaumite, 494 nm, and blue halite, 640 nm. This absorption band allows light transmission in both the red and blue regions of the spectrum, resulting in the characteristic purple color of irradiated fluorites. It may be pointed out that the position of the colloid band ranges in the order villiaumite (494 nm)fluorite (560 nm)-halite (640 nm), i.e. the same ranking as for the refractive indices, 1.3253, 1.4338 and 1.5442, hence qualitatively following the prediction of Relation (3).

Natural halite exhibits a broad range of colors, navy-blue, blue, purple or colorless arising from various proportions of color centers and Na colloids [START_REF] Wesełucha-Birczynska | Blue halite colour centre aggregates studied by micro-Raman spectroscopy and X-ray diffraction[END_REF]. [START_REF] Zelek | Lattice deformation of blue halite from Zechstein evaporate basin: Klodawa Salt Mine, Central Poland[END_REF] have shown that this may result from the complex sedimentary geology that governs in the mine the spatial distribution of halite and sylvinite, as 40 K is suspected to be the main radiation source. In villiaumite, radiation damage is caused by a specific geological context.

Agpaitic rocks are always enriched in Th and U (Sorensen, 1992). Though XRD only indicates the presence of NaF, preliminary SEM-EDS investigations of our samples (Figure 2) show the presence of nanospheres, about 500 nm large, which show a preferential alignment that apparently guides the {100} cleavage steps. These nanoinclusions contain about 8.8wt% ThO 2 (Supplemental Figure S6) and may be at the origin of a permanent irradiation of the mineral, able to create defects once the mineral cooled down to a few hundreds °C. This explains the presence of isolated color centers, which otherwise have a limited thermal stability (Schwartz et al., 1994) and the stability of the Na nanoparticles that are at the origin of the red color. The presence of thorium in the villiaumite from the Khibiny and Lovozero alkaline massifs in the Kola Peninsula, Russia [START_REF] Chukanov | On the problem of the formation and geochemical role of bituminous matter in pegmatites of the Khibiny and Lovozero alkaline massifs, Kola Peninsula, Russia[END_REF] has been explained by its complexation by organic matter, which was revealed by infrared spectroscopy. Preliminary infrared spectra on the villiaumite from the Los Archipelago also reveal the presence of aliphatic hydrocarbon groups and carboxylates in our samples (A. Geisler, unpublished report). The red color of villiaumite, prized in mineral collections, appears to be also a useful "color indicator" of the conditions of emplacement of the evolved stages of peralkaline systems.

Figure 1 .

 1 Figure 1. Room temperature optical absorption spectra of red villiaumite (a) and blue halite (b).

Figure 2 .

 2 Figure 2. Scanning Electron Microscopy micrograph in backscattered electron mode of a

ACKNOWLEDGMENTS

We are grateful to Jean-Claude Boulliard for providing the samples and their pictures from the mineral collection of Sorbonne-Université, Maxime Guillaumet for his help on the IMPMC spectroscopy platform and Imene Esteve for the preliminary SEM analyses. We thank Charles Geiger and George Rossman for fruitful suggestions that greatly improved the manuscript.


Simon Delamare

Lucas Nussbaum

Kwollect: Metrics Collection for Experiments at Scale

Keywords: testbeds, experiments, metrics collection, measurement, monitoring

It has become a common requirement for testbeds to provide a service in charge of collecting and exposing metrics, thus assisting experimenters with the central task of data collection. This paper describes Kwollect, a service designed and developed in the context of the Grid'5000, to collect infrastructure metrics (including high-frequency wattmeters) and expose them to experimenters. Kwollect scales to high frequencies of metrics collection for hundreds of nodes. It can also be leveraged by the experimenter to collect custom metrics.

I. INTRODUCTION

Most testbed experiments require collecting metrics about the system, service or application under test, and its surrounding environment. This encompasses different kinds of metrics, such as (1) metrics about the experimental environment, reflecting aspects that can influence the experiment -for example, environmental metrics (temperature, humidity) can influence performance, as a hotter machine limits the ability of its CPU to temporarily increase its performance; [START_REF] Balouek | Adding virtualization capabilities to the Grid'5000 testbed[END_REF] metrics that are part of the output of experiments, such as power consumption of the system under test, measured outside the node, or inside it, using interfaces such as Intel RAPL; [START_REF] Massie | The ganglia distributed monitoring system: Design, implementation, and experience[END_REF] metrics that help understand the experiment behavior, such as network metrics as seen from network equipments.

Whether testbeds address experiments on IoT, 5G, HPC or clouds, it has thus become a common requirement for them to provide services supporting users through the process of accessing and collecting those metrics, by providing interfaces to infrastructure metrics and facilitating data collection. However, as we will detail later, those services are often limited in terms of features, and in terms of their ability to scale up to large number of metrics collected at high frequency.

This paper describes Kwollect, a service to provide access to infrastructure metrics (including high-frequency wattmeters, hence the name) and facilitate data collection from all nodes involved in an experiment. It has been developed in the context of the Grid'5000 testbed, but it is designed to be used on any infrastructure. Kwollect can collect metrics at high frequency (sub-second), and then expose them to the experimenter either through a REST API, or through a web interface that provides interactive visualization. In addition to providing access to a wide range of infrastructure metrics, Kwollect can also be extended by the experimenter to collect additional custom metrics. Kwollect is also built from the lessons learned while operating a first version of a monitoring service, Kwapi [START_REF] Clouet | A unified monitoring framework for energy consumption and network traffic[END_REF].

The paper is organized as follows. Section II provides background about Grid'5000 (II-A), and analyzes related work (II-B). Section III details Kwollect's design. Its deployment on Grid'5000, along with an example use case, is presented in Section IV. Performance is evaluated in Section V.

II. BACKGROUND

A. The Grid'5000 testbed Grid'5000 [START_REF] Balouek | Adding virtualization capabilities to the Grid'5000 testbed[END_REF] focuses on all areas of distributed systems research, including High Performance Computing (HPC), cloud and edge computing, and AI. It can be seen as an European equivalent to testbeds like Chameleon and CloudLab.

In the research areas addressed by Grid'5000, the ability to experiment at scale is crucial, and the testbed optimizes for this use case, for example by encouraging rather short reservations of many simultaneous resources. The testbed is composed of sites, with each site gathering up to 374 nodes (servers), for a total of 806 nodes. It is not unusual to see experiments running on hundreds of nodes, which stresses correspondingly the monitoring service. Also, in those research areas (and especially in HPC), experimenters are often interested in subtle behavior that is only visible when metrics are collected at a high frequency (1 Hz or higher).

The main historical motivation for providing a measurement service to Grid'5000 users was the very active national research community around energy efficiency. Their experiments rely heavily on specific hardware (wattmeters) for precise power measurements, able to uncover the impact of application behavior on power consumption.

B. Related work

There are three types of solutions that serve similar, yet different purposes.

Testbed infrastructure monitoring services (TIMS) are services that are used by testbed operators to monitor the health of the testbed, using solutions such as Munin, Nagios, Ganglia [START_REF] Massie | The ganglia distributed monitoring system: Design, implementation, and experience[END_REF] or more recently Prometheus [START_REF]Prometheus monitoring system[END_REF]. Given they serve this purpose very well, it might be tempting to design a service exposed to experimenters on top of such solutions. However those services are generally designed to provide coarse-grained metrics at low frequency (one measurement every few seconds, or more), and the design of their metrics storage solution makes them hardly compatible with the requirements of most experiments, that need high frequency measurements to understand subtle system or application behavior. In addition, these solutions are primarily designed to monitor metrics collected by nodes' operating systems. Their ability to monitor external devices, such as Power Delivery Unit (PDU) or server's Baseboard Management Controller (BMC, such as Dell's iDRAC) is often provided as a second-class extension, whereas it is a primary objective of Kwollect.

Testbed-provided measurement services (TPMS) are services, like Kwollect, that are responsible for collecting data and exposing it. They can cover infrastructure data (from network equipment, power distribution equipment, baseboard management cards), data from environmental sensors, and also sometimes experimenter-provided data (by running an agent on nodes). A common such service on wireless testbeds, deployed for example on the COSMOS testbed [START_REF] Yu | COSMOS: Optical architecture and prototyping[END_REF], is OML [START_REF] Singh | Orbit measurements framework and library (OML): Motivations, implementation and features[END_REF], [START_REF]Orbit measurement library[END_REF] (ORBIT Measurement Library), which is part of the Orbit Management Framework (OMF) [START_REF] Rakotoarivelo | OMF: A control and management framework for networking testbeds[END_REF]. On the Chameleon Cloud testbed, the OpenStack Gnocchi service [9] is used for the same purpose, relying on collectd as the agent running on each node (with data retrieved every 10s), and completing it with power data retrieved over IPMI [START_REF]Metrics using Gnocchi in the Chameleon tested[END_REF]. On the Grid'5000 testbed, Kwapi [START_REF] Clouet | A unified monitoring framework for energy consumption and network traffic[END_REF] was used before Kwollect replaced it. In the past, PlanetLab provided COMon [START_REF] Park | Comon: A mostly-scalable monitoring system for planetlab[END_REF] to expose statistical information about testbed nodes and slices allocated to users.

Experimenter-managed measurement services (EMMS) are services installed and managed by the experimenter, as part of the experiment setup, that are responsible for collecting data. They range from basic tracing scripts and system tracing tools (strace, eBPF, etc.) to more complex solutions such as Monex [START_REF] Saif | MonEx: An Integrated Experiment Monitoring Framework Standing on Off-The-Shelf Components[END_REF], that combines off-the-shelf solutions such as Prometheus, InfluxDB and Grafana.

While TIMS are out of scope for this work, TPMS and EMMS both provide complementary perspectives. With an EMMS, experimenters are fully in charge of designing how data will be extracted from their experiments, which brings a lot of power and flexibility at the expense of the corresponding engineering burden. With a TPMS, the experimenter has to fit into the provided model for metrics collection, but is freed from most of the corresponding engineering burden. A compelling advantage of TPMS over EMMS is that they can provide access to metrics that are not normally accessible to users (data from infrastructure components such as network equipment, power distribution equipment, servers management cards, sensors, etc.) while limiting the impact on the security of the infrastructure, because the necessary filters can be implemented inside the TPMS if needed.

III. KWOLLECT DESIGN

This section describes Kwollect's design and explain choices that were made. Figure 1 gives an overview of Kwollect components that will be presented here. At its core, Kwollect leverages TimescaleDB (a PostgreSQL extension) to provide efficient metrics storage. Its REST API is directly provided through another PostgreSQL extension, maximizing performance. Metrics are collected by a set of Kwollectors,

A. Metrics storage

Kwollect uses a PostgreSQL database with its TimescaleDB extension for metric storage. Using a well established relational database such as PostgreSQL delivers many benefits: it allows to associate metrics with other data available to PostgreSQL (made available using PostgreSQL's foreign data wrappers) using standard SQL joins. It also takes advantage of PostgreSQL's maturity and rich ecosystem.

However, by default, PostgreSQL do not offer strong performance when managing large timeseries-oriented datasets. A naive approach consisting in inserting data into a single table would not scale, as the table would keep growing which would eventually cause performance problems: table's indexes would not fit in system memory, causing intensive input/output operations each time data are accessed.

TimescaleDB solves this problem by performing automatic partitioning of tables according to the timestamps of the data being inserted: It assumes that for most workloads, it is likely that data being inserted or accessed relate to a recent time period. Slicing tables such as the most recent partition would always fit in system memory, and would ensure consistent performance over time, even if large amount of data is being inserted.

TimescaleDB also comes with other useful features for timeseries, such as compression, used by Kwollect to decrease disk usage by a factor of 100, continuous data aggregation and customizable retention policy.

B. Metrics format

Kwollect stores every metrics it collects inside a database table named metrics, using the schema described in Table I.

This format is largely inspired by Prometheus and its derived standard named OpenMetrics.

Each metric data is associated with this information:

C. Collecting metrics

Kwollectors are in charge of reading metrics from devices and storing resulting values into the database. Kwollectors are autonomous processes: they only need to access the database and the devices they monitor. Therefore there can be several Kwollectors running to monitor different devices and their deployment can be distributed over additional machines. This design allows reading and storing metrics task to easily scale with a very high number of monitored devices.

The implementation we propose for the main Kwollector currently supports reading metrics from Simple Network Management Protocol (SNMP), Intelligent Platform Management Interface (IPMI) and Prometheus export protocols. It is written in Python, using the asyncio library to exploit the high concurrency of I/O operations performed by the monitoring task. A single core from a standard server is enough to run a Kwollector that take cares of hundreds of devices with hundreds of metrics each. Kwollectors accept configuration files describing devices and metrics to fetch. An example is provided in Figure 2.

Some Kwollectors dedicated to particular devices have been implemented to address their specificities, such as a Kwollector for high frequency wattmeters available in Grid'5000. Kwollect provides a REST API for users to retrieve metrics values. The API accepts parameters such as devices list from which to retrieve values, the start and the end of the time period, or to filter by metric name. It returns results in JSON format. An example of result is provided in Figure 3.

The REST API is provided by PostgREST3 , that provides a REST API over a PostgreSQL database. Existence of Post-gREST highlights the benefits of using mainstream storage solution such PostgreSQL: it allows Kwollect to provide an API without any need of in-house software development.

Pushing values to the database is also possible for authenticated users (access control is based on user privileges defined inside the database).

E. Graphical interface

Using a PostgreSQL-based storage allows using existing visualization solutions, such as Grafana 4 . Kwollect provides a preconfigured Grafana dashboard to display metrics values. An example of such dashboard is given in Figure 4.

As Grid'5000 has specific needs conflicting with what Grafana offers (i.e. we require a more constrained interface as we are facing untrusted users), we also developed an alternative dashboard 5 using Jupyter notebooks and IPywidgets6 , and Voila7 to convert the notebook to a standard Web application. Each results is the average of 5 measurements (dispersion is negligible).

F. Specific features

The versatility of PostgreSQL allows to implement specific features required by a testbed-oriented monitoring solution directly at the database definition level, without requiring any other development, as illustrated by the following examples.

1) Job scheduler integration: Kwollect provides its users an easy way of retrieving metrics from an experiment. In Grid'5000, experiments are orchestrated by OAR, a job scheduling system (an experiment being represented by a job).

Integrating metrics information with job scheduler information is performed by PostgreSQL using JOIN operation between metrics table and data imported from OAR. As a result, metrics can be selected according to a job identification number from a PostgreSQL VIEW, which is in turn automatically available through the REST API for users.

2) On demand metrics: To avoid unnecessary disk space and resource consumption, Kwollect allows some metrics not to be collected by default but only on demand. On-demand metrics monitoring must be enabled by filling a dedicated database table, listing devices and on-demand metrics to enable. The table is exposed to Kwollectors to inform them of the on-demand metrics to retrieve on the devices they monitor.

In Grid'5000, not every possible metrics are activated by default, but we allow Kwollect users to enable them by specifying appropriate options to their job submission command. Internally, as information about OAR job scheduler is available to Kwollect's PostgreSQL, it is straightforward to fill the ondemand metrics table with metrics requested by users for their jobs.

IV. GRID'5000 DEPLOYMENT AND USE CASE SCENARIO

In this section, we present Kwollect deployment on Grid'5000 an give an example scenario demonstrating the use of Kwollect by users.

Grid'5000 is distributed over 9 sites and each of them has an independent Kwollect instance deployed on a virtual machine hosting the database and a single Kwollector to monitor the site's nodes and devices.

The following metrics are monitored by default:

• Energy consumption measured at the power outlet, every second, for nodes connected to a monitorable PDU or a dedicated wattmeter using SNMP protocol. • Most important metrics from nodes' BMC sensors, every 5 seconds using SNMP or IPMI protocols, depending on what the device supports. • Network equipments traffic, every second using SNMP.

• Most important metrics from Prometheus exporters (including some GPU metrics), every 15 seconds. • Arbitrary metrics pushed by users from nodes by writing to a specific file periodically parsed by Kwollectors. In addition, more metrics are available on demand, when users enable them explicitly. This is used to instruct wattmeters to perform 50 measurements per second or to enable BMC or Prometheus metrics not kept by default.

In total, 88 distinct metrics on 2500 different devices are available for monitoring on Grid'5000 and between 5000 and 10000 values are collected each second. We now consider an example use case consisting in an investigation of causes of energy consumed by a server. Using Kwollect, a user is able to visualize energy consumed by a Grid'5000 node over time, using values reported by dedicated wattmeters and node BMC (Figure 6). Fig. 6: Evolution of energy consumption reported by server BMC and dedicated wattmeter during the example scenario After an idle period, the node is rebooted. Power consumption increases as the node is being busy and operating system energy saving mechanisms are missing. Once boot is completed at step 3, node goes back to an idle state.

Measurements performed by the two devices seem sound: they follow the same global evolution, BMC values being shifted by a few seconds in time and a few Watts less.

A remarkable observation is consumption spikes reported by wattmeter devices which are absent from values reported by BMC. One might wonder if they correspond to noise or to an actual consumption which cannot be seen by only looking at consumption reported by BMC, being not precise enough. It appears that some of the spikes are caused by the Prometheus Exporter installed on the node, which is queried every 15 seconds. After stopping it (step 4), the spikes disappear.

This example shows that Kwollect can be used to analyze power consumption, including comparing data from several sources and at different resolutions to analyze spikes. By averaging the values provided by Kwollect during idle steps with or without Prometheus running, we can estimate the power cost of running this service to be 0.35 W.

V. PERFORMANCE EVALUATION

In this section, we present Kwollect performance results from two contexts: an experimental setup and the real-world deployment of Kwollect in Grid'5000.

A. Experimentation Setup

We evaluate Kwollect in an experimental setup where 1000 devices are monitored. Each device has 100 different metrics collected every 5 seconds. Database is filled in advance with data representing two days of monitoring (using a longer period would not have any effect, as database partitioning is set to a 2-hour period and compression is enabled for 24-hourold data). Evaluation is performed with Kwollect installed on a single server. Different server characteristics, described in Table II, are compared to exhibit performance that can be achieved according to hardware available.

We measure maximum metrics ingestion rate using parallel SQL COPY statements (similarly to what Kwollector does) according to the number of parallel workers performing COPYs. We also measure the time needed to retrieve metrics values using the API, using different parameters where the number of devices involved or the time period requested vary. Results are presented in Figure 5.

Maximum ingestion rate is achieved when several workers perform insertions in parallel (16 in our case). Using too many workers is inefficient as ingestion will be limited by storage performance and parallelization overhead. We found that a single instance of Kwollect is able to ingest more than 350000 metrics each second if SSD storage is used.

In our measurement, we observe that requests response time scales linearly with the size of the workload, except for taurus configuration. For the others, we did not get significant differences between the different machines as requested workload were small enough to fit in system memory and not to be limited by storage, but by the CPU. On this kind of hardware, Kwollect is able to serve 500000 metrics values in about 10 seconds. The taurus configuration has less memory and performance degrade once the request size becomes important.

This analysis confirms that, with appropriate hardware, Kwollect can manage several hundreds of thousands of metrics per second and can deliver millions of metrics values to users in less than a minute.

B. Grid'5000 Deployment

We now present some performance results from Kwollect deployment in Grid'5000, from two Grid'5000 sites: Nancy, which is the largest (by default and for results presented in this section, 1350 distinct devices are monitored, for an average of 4000 metrics per seconds) and Lyon, which is of average size, but has many devices monitored by high-frequency wattmeters (by default, 250 devices are monitored giving 850 metrics per second, and in addition for results presented here, 20 high frequency wattmeters performing 50 measures per second each, have been activated on demand). Virtual machines hosting Kwollect have 4 virtual CPUs, 16 GB or memory, 500GB of storage space (mechanical disks at Lyon, SSD at Nancy). The CPU load of Nancy Kwollect virtual machine under normal service conditions with or without user queries being performed is presented in Figure 7.

Results show that in the absence of requests, less than one unit of CPU is required to run Kwollect, used by the Kwollector to get data from devices and ingest it: Kwollect does not require more than a single CPU to monitor hundred of devices. We also find that one request keeps approximately one CPU busy, indicating CPU requirement to handle more requests in parallel (even if storage performance would become another bottleneck).

Request latency is presented in Figure 8, where users ask Kwollect to get metrics associated to a 5-minute-long job, a two-hour-long job and to this same job, but 24 hours after it has ended (they are requested as soon as the job finishes otherwise). Different job configurations are considered: they might include 2 or 20 nodes (thus including 10 times more metrics) or be located at Nancy or Lyon (thus including 50 wattmeter metrics per nodes and per second of job). The approximate number of metrics corresponding to each request is also indicated on the figure.

Results show that, even on modest hardware in used for Grid'5000 deployment, Kwollect can deliver tens of thousands of values in few seconds and millions of values in few minutes. These durations are largely compatible with the experimentation needs of Grid'5000 users.

Fig. 1 :

 1 Fig. 1: Kwollect components

-Fig. 2 :

 2 Fig. 2: Kwollector configuration example

Fig. 3 :Fig. 4 :

 34 Fig. 3: Example result from Kwollect's REST API

  (a) Maximum number of metrics which can be ingested each second, according to the number of workers performing insertions in parallel. (b) Time needed to retrieve metrics values, according to the number of devices involved (over a period of 10 minutes).(c) Time needed to retrieve metrics values, according to the length of the time period (requesting values for 10 devices.

Fig. 5 :

 5 Fig. 5: Performance results of the experimentation setup where devices have 100 different metrics monitored every 5 seconds. Each results is the average of 5 measurements (dispersion is negligible).

Fig. 7 :Fig. 8 :

 78 Fig. 7: Virtual machine CPU load as unit of CPU being busy (reported not being in the idle state by the vmstat tool), depending on the number of simultaneous user requests ongoing (average load over 60 seconds for each results)

TABLE I :

 I Kwollect metrics format used in database

TABLE II :

 II Hardware characteristics of each server hosting Kwollect in the experimentation setup

https://gitlab.inria.fr/grid5000/kwollect

https://postgrest.org/

https://grafana.com/

https://gitlab.inria.fr/grid5000/kwollect-dashboard

http://ipython.org/

https://github.com/voila-dashboards/voila

VI. CONCLUSIONS

In this article, we presented the design, performance evaluation and use cases for Kwollect, a testbed service to collect and expose metrics in the context of experiments. Kwollect has been successfully deployed in the Grid'5000 testbed, met user expectations, and overcame all limitations of our previous solution. We will further extend Kwollect to monitoring more metrics and improve its integration with experiment control tools and libraries. We also now look forward to porting Kwollect to other environments, such as wireless or IoT testbeds.