Carlos D'andrea
email: cdandrea@ub.edu

SINGULAR FACTORS OF RATIONAL PLANE CURVES

Keywords: . 2010 Mathematics Subject Classification. Primary 14Q05; Secondary 13P15, 68W30 Rational plane curves, rational parameterizations, µ-bases, Dresultants, subresultants, invariant factors

We give a complete factorization of the invariant factors of resultant matrices built from birational parameterizations of rational plane curves in terms of the singular points of the curve and their multiplicity graph. This allows us to prove the validity of some conjectures about these invariants stated by Chen, Wang and Liu. As a byproduct, we also give a complete factorization of the D-resultant for rational functions in terms of the similar data extracted from the multiplicities.

Introduction

Curves in Computer Aided Geometric Design and in Visualization are often given in parametric form. Their singularities are usually points where the shape of the graphic gets more complicated. Hence, understanding the nature and character of these singular points has been an active area of research in the last years, see for instance [START_REF] Chionh | On the minors of the implicitization Bézout matrix for a rational plane curve[END_REF][START_REF] Park | Effective computation of singularities of parametric affine curves[END_REF][START_REF] Song | Axial moving lines and singularities of rational planar curves[END_REF][START_REF] Pérez-Díaz | Computation of the singularities of parametric plane curves[END_REF][START_REF] Chen | Computing singular points of plane rational curves[END_REF][START_REF] Busé | On the equations of the moving curve ideal of a rational algebraic plane curve[END_REF][START_REF] Jia | Using Smith forms and µ-bases to compute all the singularities of rational planar curves[END_REF] and the references therein.

In this article, we will focus on parametric plane curves defined over the complex numbers, although our results are valid for any field of characteristic zero, and the computational aspects can be performed also on any field containing the coefficients of the input polynomials. Let a, b, c ∈ C[s, v] be homogeneous polynomials of the same degree n ≥ 3 with gcd(a, b, c) = 1, such that the map [START_REF] Shreeram | Algebraic geometry for scientists and engineers[END_REF] φ :

P 1 C → P 2 C
(s 0 : v 0 ) → (a(s 0 , v 0 ) : b(s 0 , v 0 ) : c(s 0 , v 0 )) parameterizes a plane rational algebraic curve C birationally onto its image (which is equivalent to say that the degree of C is n). As it was shown by Abhyankar in [START_REF] Shreeram | Algebraic geometry for scientists and engineers[END_REF] for c = v n , and later in general by Sendra and Winkler in [START_REF] Sendra | Tracing index of rational curve parametrizations[END_REF], Gutierrez, Rubio and Yie in [START_REF] Gutierrez | D-resultant for rational functions[END_REF], and Pérez-Diaz in [START_REF] Pérez-Díaz | Computation of the singularities of parametric plane curves[END_REF] among others, the parameterization φ can be used to detect the singular points of C, which are those P ∈ C such that their multiplicity m P (C) is strictly greater than 1. As φ is generically one-to-one, m P (C) is actually the number of points in the preimage of φ -1 (P ) counted with multiplicities (for a proper "parameterization-free" definition of m P (C) as well as its properties, see [START_REF] Shreeram | Algebraic geometry for scientists and engineers[END_REF][START_REF] Walker | Algebraic Curves[END_REF]). This explains why from a computational point of view, the parameterization φ provides a lot of information about the singularities of C. The purpose of this paper is to shed some light in this area. We will use the notation and definitions given in [START_REF] Brieskorn | Plane algebraic curves. Translated from the German by John Stillwell[END_REF] (see also [START_REF] Stadelmeyer | On the computational complexity of resolving curve singularities and related problems[END_REF]). Let {P 1 , . . . , P r } be the proper singular points of C, and for all i = 1, . . . , r denote by • z i j , j ∈ I i , the irreducible branch-curves of C at P i , • (t i,j : u i,j ), j ∈ I i , the point of P 1 C such that z i j (t i,j : u i,j ) = P i ,

• (P i j,h ) 0≤h the neighboring point sequence of z i j at P i , • (m i j,h ) 0≤h the multiplicity sequence of z i j at P i , • (∼ h ) o≤h the equivalence relations of the multiplicity graph of C.

For a virtual point P i j,h of C, we define its multiplicity as m P i j,h (C) := j ∼ h j m i j ,h . Set [START_REF] Apéry | Élimination: le cas d'une variable. Collection Méthodes[END_REF] F (s, v; t, u) := a(s, v)c(t, u) -a(t, u)c(s, v) G(s, v; t, u) := b(s, v)c(t, u) -b(t, u)c(s, v),

and let Res (s,v) (-, -) be the Sylvester resultant operator which eliminates the homogeneous variables s and v . If c = v n , then it is shown in [START_REF] Shreeram | Algebraic geometry for scientists and engineers[END_REF] that there exists 0 = γ ∈ C such that

(3) Res (s,v) F (s, v; t, u) su -tv , G(s, v; t, u) su -tv = γ i=1,...,r j∈Ii (u i,j t -t i,j u) i,j

where for all i = 1, . . . , r and j ∈ I i i,j = h≥0 m i j,h (m P h j,h (C) -1).

From now on we will most of the time omit the nonzero constants. Hence, all identities involving polynomials should be understood up to a nonzero γ ∈ C. Let B F,G (t, u) ∈ C[t, u] n×n be the square Bézout matrix built from F (s, v; t, u), G(s, v, t; u) regarded as polynomials in the variables (s, v) (see Section 5 for its precise definition and construction). Clearly, B F,G (t, u) does not have maximal rank as su -tv is a common factor of both F and G. In [START_REF] Chionh | On the minors of the implicitization Bézout matrix for a rational plane curve[END_REF], Chiohn and Sederberg showed that by analyzing the maximal minors of this matrix, one can obtain all the singular points of C in a very direct way. This approach was improved and refined by Chen, Wang and Liu in [START_REF] Chen | Computing singular points of plane rational curves[END_REF], where (2) is replaced with [START_REF] Busé | On the equations of the moving curve ideal of a rational algebraic plane curve[END_REF] p φ (s, v; t, u) = p 1 (s, v)a(t, u) + p 2 (s, v)b(t, u) + p 3 (s, v)c(t, u) q φ (s, v; t, u) = q 1 (s, v)a(t, u) + q 2 (s, v)b(t, u) + q 3 (s, v)c(t, u), with {p, q} := {(p 1 , p 2 , p 3 ), (q 1 , q 2 , q 3 )} being a basis of the free C[s, v]-module of syzygies of (a, b, c). Suppose w.l.o.g. that deg(p) ≤ deg(q) and set µ := deg(p). We then easily have µ ≤ n -µ = deg(q). In the Computer Aided Geometric Design community, the set {p, q} is called a µ-basis of the parameterization φ.

Let now B p φ ,q φ (t, u) ∈ C[t, u] (n-µ)×(n-µ) be the hybrid Bézout matrix associated to p φ (s, v; t, u), q φ (s, v; t, u) (for a definition of hybrid Bézout matrices, se also Section 5). It is shown in [START_REF] Chen | Computing singular points of plane rational curves[END_REF] that by computing the invariant factors of this matrix, one gets some kind of stratification of the singularities of C with respect to their multiplicities (Theorem 4 in [START_REF] Chen | Computing singular points of plane rational curves[END_REF]). This stratification is well understood when all the singularities of C are ordinary (i.e. when there are no virtual points P i j,h with h > 0) and one can get an explicit description of the invariant factors of this matrix in terms of the singular points of C and their multiplicities (Theorems 5 and 6 in [START_REF] Chen | Computing singular points of plane rational curves[END_REF]).

In the case where C has singularities that are not ordinary, Chen, Wang and Liu stated a couple of conjectures (Conjectures 1 and 2 in [START_REF] Chen | Computing singular points of plane rational curves[END_REF]) relating the invariant factors with the multiplicity of the virtual points appearing in the process of desingularization of the curve. The main result of this paper is a complete factorization of the singular factors of B p φ ,q φ (t, u) and as a consequence a complete proof and clarification of both conjectures.

To be more precise, let S p φ ,q φ (t, u) be the Sylvester matrix of (4). It is simply the square (n × n)-matrix of the C[t, u]-linear map

C[t, u] ⊗ C C[s, v] n-µ-1 ⊕ C[t, u] ⊗ C C[s, v] µ-1 → C[t, u] ⊗ C C[s, v] n-1 (5) α ⊕ β → αp φ + βq φ in the canonical monomial bases (the notation C[s, v] d , d ∈ N, stands for the C-vector space of homogeneous polynomials of degree d in C[s, v]). A collection of homogeneous polynomials d 1 (t, u), d 2 (t, u), . . . , d n (t, u) in C[t, u] such that, for i = 1, . . . , n the product d n (t, u) n-i+1 d n-1 (t, u) n-i • • • d i+1 (t, u) 2 d i (t, u) ∈ C[t, u]
is equal to the greatest common divisor of the (n + 1 -i)-minors of S p φ ,q φ (t, u), is called a collection of singular factors of the parameterization φ. The existence of these polynomials is guaranteed by homogenizing with some care the invariant factors of S p φ ,q φ (t, 1).

The terminology of singular factors is taken from [START_REF] Chen | Computing singular points of plane rational curves[END_REF]. Note also that if a, b, c ∈ k[s, v] with k a subfield of C, then the singular factors will have their coefficients in k. This observation is of importance for computational purposes. Now we are ready to present the main result of this paper.

Theorem 1.1. With the notation established above, we have

d n-µ+1 (t, u) = • • • = d n (t, u) = 1,
and for k = 2, . . . , n -µ d k (t, u) = i=1,...,r, j∈Ii (u i,j t -t i,j u) k i,j
where

k i,j = h such that m P i j,h (C)=k m i j,h
We will see how this theorem implies Conjectures 1 and 2 in [START_REF] Chen | Computing singular points of plane rational curves[END_REF] in Section 2 and prove it in Section 4. We also point out that the factorization of invariant factors of matrices related to this problem is also considered in [START_REF] Jia | Using Smith forms and µ-bases to compute all the singularities of rational planar curves[END_REF].

The reader may have already noticed that we just claimed above that the conjectures posted in [START_REF] Chen | Computing singular points of plane rational curves[END_REF] where made over the matrix B p φ ,q φ (t, u) instead of S p φ ,q φ (t, u). We will show in Section 5 that the cokernels of these two matrices plus a whole family of hybrid resultant matrices are isomorphic, thus Theorem 1.1 can also be formulated over the invariant factors of any of them. Our results in Section 5 can be regarded as an extension of those shown already by Apéry and Jouanolou in [2, Proposition 18].

We will also see in Section 6 that there is an explicit connection between B p φ ,q φ (t, u) and B F,G (t, u), which will allow us to get a complete description of the invariant factors of the latter. As a direct consequence of this, we get a complete factorization into irreducible factors of D-resultants. These are a natural generalization of Abhyankar's formula (3) for c = v n . Indeed, in [START_REF] Gutierrez | D-resultant for rational functions[END_REF], it is shown that if we take

(6) ∆(t, u) := Res (s,v) F (s, v; t, u) su -tv , G(s, v; t, u) su -tv ,
for a general rational parameterization, it turns out that if φ(t 0 : u 0 ) is a singularity of C, then ∆(t 0 , u 0 ) = 0, but there may be other roots coming from curves being parameterized by permutations of (a, b, c) see [8, Theorem 3.1], and there was no known analogue of a factorization like (3) for ∆(t, u).

In [START_REF] Busé | On the equations of the moving curve ideal of a rational algebraic plane curve[END_REF], the first author shows that by replacing (2) with (4) in the definition of ∆(t, u), one gets a polynomial ∆(t, u) which factorizes like (3). We will review the properties of ∆(t, u) in Section 2.

However, there was still missing a complete factorization of ∆(t, u). In Theorems 6.3 and 6.4 we give a precise description of the factors of the D-resultant, completing the information given in [START_REF] Gutierrez | D-resultant for rational functions[END_REF]Theorem 3.1].

Understanding the algebraic structure of these matrices may lead to new algorithms for studying the geometry of singular points of rational curves. We will see for instance in Example 2.1 that in some non trivial cases one can reconstruct the whole multiplicity graph of C from the invariant factors of these matrices, with operations only over the ground field of the parameterization. From a symbolic point of view, this problem has already been studied in [START_REF] Sendra | Symbolic parametrization of curves[END_REF][START_REF] Stadelmeyer | On the computational complexity of resolving curve singularities and related problems[END_REF][START_REF] Pérez-Díaz | Computation of the singularities of parametric plane curves[END_REF].

Organization of the paper. In Section 2 we introduce some basic definitions and results, and also show how Theorem 1.1 implies Conjectures 1 and 2 in [START_REF] Chen | Computing singular points of plane rational curves[END_REF]. In Section 3 we prove the main theorem for curves having only ordinary singularities. The proof of the general case is given in Section 4. Section 5 is devoted to show that any resultant matrix can be used in Theorem 5. In Section 6, we describe all the invariant factors of B F,G (t, u) and show the complete factorization of D-resultants.

Acknowledgements. We would like to thank José Ignacio Burgos, Eduardo Casas-Alvero and Teresa Cortadellas for very interesting comments, suggestions and clarifications on topics about singularities of curves and commutative algebra. The second author would also like to thank the Fields Institute in Toronto, where part of this work was done.

Preliminary results and the singular factors conjectures

Throughout this paper, we will work over the field of complex numbers C. However, it should be noted that all the statements and proofs work over any algebraically closed field of characteristic zero. We recall here again that every identity involving polynomials should be understood up to a nonzero constant.

Let (x 1 : x 2 : x 3 ) be the homogeneous coordinates of P 2 C . By Hilbert-Burch's theorem, the first syzygy module of the sequence a(s, v), b(s, v), c(s, v) is a free C[s, v]-module of rank 2. Moreover, if µ denotes the smallest degree of a nonzero syzygy, then this syzygy module is generated in degrees µ and n -µ. A µ-basis of the parameterization φ is then a choice of a basis of this syzygy module. Identifying any syzygy (g 1 , g 2 , g 3 ) with the bi-homogeneous form g 1 x 1 + g 2 x 2 + g 3 x 3 , a µ-basis corresponds to a couple of bi-homogeneous forms p, q

∈ C[s, v] ⊗ C C[x 1 , x 2 , x 3 ] of bi-degree (µ, 1) and (n -µ, 1) respectively, such that 1 ≤ µ ≤ n -µ.
As C is a rational projective curve, we have that its number of singular points, counted properly, is given by the well known genus formula:

(n -1)(n -2) = P ∈Sing(C) m P (C)(m P (C) -1)
where Sing(C) stands for the singular points, proper as well as infinitely near, of the curve C and m P (C) stands for the multiplicity of the singular point P on C. Notice that in our case we know that there exists at least one (proper) singular point on C, since n ≥ 3.

It is a well known fact that Res (s,v) (p, q) ∈ C[x 1 , x 2 , x 3 ] is an implicit equation of the curve C, meaning that it is an irreducible and homogeneous degree n polynomial whose zero locus is exactly the curve C (recall that the parametrization φ is assumed to be birational onto C). Another interesting property is the following (see also [START_REF] Chen | Computing singular points of plane rational curves[END_REF]Lemma 2]):

Proposition 2.1. Let Q = (α 1 : α 2 : α 3 ) be a point in P 2
C and denote by H Q (s, v) a greatest common divisor of the two forms 3 i=1 α i p i (s, v) and

3 i=1 α i q i (s, v) in C[s, v]. Then H Q (s, v) is a homogeneous polynomial of degree m Q (C) and if m Q (C) ≥ 1 we have H Q (s, v) = N i=1 (v i s -s i v) mi
where N is the number of irreducible branch-curves of C centered at Q and m i denotes the multiplicity of Q with respect to the irreducible branch-curve z such that z(s i :

v i ) = Q.
Proof. By a linear change of coordinates in P 2 C , one can assume that Q = (0 : 0 : 1), because µ-bases have the expected property under linear changes of coordinates. By Hilbert Burch's theorem we have that, up to a constant,

a(s, v) = p 2 (s, v) p 3 (s, v) q 2 (s, v) q 3 (s, v) and b(s, v) = p 3 (s, v) p 1 (s, v) q 3 (s, v) q 1 (s, v) . If h(s, v
) is a divisor of p 3 (s, v) and q 3 (s, v), then it follows that h(s, v) divides both a(s, v) and b(s, v). Reciprocally, suppose that h(s, v) is a nontrivial divisor of a(s, v) and b(s, v). Then, as

p 1 (s, v)a(s, v) + p 2 (s, v)b(s, v) + p 3 (s, v)c(s, v) = 0
and c(s, v) does not share any nontrivial common factor with neither a(s, v) nor b(s, v), then h(s, v) must divide p 3 (s, v). The same argument works for q 3 (s, v) and we deduce that gcd(p 3 (s, v), q 3 (s, v)) = gcd(a(s, v), b(s, v)). From here, the claimed equality follows from the definition of the multiplicity of a point on an irreducible branch-curve.

Remark 1. As an easy consequence of Proposition 2.1, we have that if

Q is a proper singular point on C then either 2 ≤ m Q (C) ≤ µ or m Q (C) = n -µ, a fact
that has already been noticed in [START_REF] Song | Axial moving lines and singularities of rational planar curves[END_REF].

Proposition 2.1 shows that a µ-basis of φ provides nontrivial information on the proper singularities of C. It turns out that it also carries informations on the infinitely near singularities of C. Recall that we have the following property:

m P i j,h (C) = j ∼ h j m i j ,h ≥ m i j,h .
Also, denote with SRes(p, q) ∈ C[x 1 , x 2 , x 3 ] the first principal subresultant of p and q with respect to the couple of homogeneous variables (s, v). It is simply a certain minor of the Sylvester matrix of p and q with respect to (s, v) (see e.g. [START_REF] Apéry | Élimination: le cas d'une variable. Collection Méthodes[END_REF][START_REF] Kahoui | D-resultant and subresultants[END_REF][START_REF] Busé | On the equations of the moving curve ideal of a rational algebraic plane curve[END_REF] for a precise definition). The following result is a slight refinement of [4, Section 4].

Theorem 2.2. We have

(7) ∆(t, u) = SRes(p, q)(a(t, u), b(t, u), c(t, u)) = γ i=1,...,r j∈Ii (u i,j t -t i,j u) i,j
where 0 = γ ∈ C and for all i = 1, . . . , r and j

∈ I i i,j = h≥0 m i j,h (m P h j,h (C) -1).
In particular,

deg(∆(t, u)) = (deg(C) -1)(deg(C) -2) = P ∈Sing(C) m P (C)(m P (C) -1).
Proof. Although not stated explicitly under this form, this theorem follows from the results contained in [4, Section 4]. Indeed, the proof of Theorem 4.8 in loc. cit. shows that all the inequalities given in Proposition 4.6, always in loc. cit., are actually equalities for the first principal subresultant of p and q. Since these equalities occur at the level of irreducible branch-curves, they imply the above theorem which requires the use of the multiplicity graph of C. In fact, the properties (P1), (P2) and (P3) in loc. cit. are consequences of this theorem but they constitute the finer result one can state without introducing the multiplicity graph of C.

Notice that Theorem 1.1 can be regarded as a refinement of the above theorem, since it provides non trivial factors of ( 7) that are in relation with the multiplicities of the singular points of the curve C.

Let us now show how Theorem 1.1 implies the two conjectures stated in [START_REF] Chen | Computing singular points of plane rational curves[END_REF]. For each proper singular point P i ∈ C, i = 1, . . . , r, we have

H Pi (t, u) = j∈Ii (u i,j t -t i,j u) m P i (z i j ) = j∈Ii (u i,j t -t i,j u) m i j,0 . For all 2 ≤ k ≤ n -µ, set h k (t, u) = Pi such that m P i (C)=k H Pi (t, u). From Theorem 1.1, it is clear that h k (t, u) divides d k (t, u)
. Actually, we have:

d k (t, u) = h k (t, u) i=1,...,r j∈Ii (u i,j t -t i,j u) k i,j ,
where

k i,j = h>0 such that m P i j,h (C)=k m i j,h = k i,j - m i j,0 if m Pi (C) = k 0 otherwise.
Therefore, following the notation in [5, Conjecture 1], we can establish the validity of the first conjecture:

d k (t, u) = h k (t, u) n-µ s=k Ψ s k (t, u),
where for all pair 2 ≤ k, s ≤ n -µ,

Ψ s k (t, u) = i=1,...,r j∈Ii m P i (C)=s (u i,j t -t i,j u) k i,j .
Obviously Ψ s k (t, u) = 0 if s < k (for multiplicities cannot increase through blowing up). Moreover, it is not hard to check that deg(Ψ s k (t, u)) is k times the number of infinitely near and non-proper singularities of multiplicity r above a proper singular point of multiplicity s, which proves and makes more precise [5, Conjecture 1]. Now, define for all k = 2, . . . , n -µ the reduced singular factor dk (t, u) by the following procedure:

• Set dk (t, u) := d k (t, u).

• Then, for all l = n -µ down to k + 1 do dk (t, u) := dk (t,u) gcd( dk (t,u),d l (t,u)) .

Theorem 1.1 then implies that dk (t, u) = i=1,...,r, j∈Ii

(u i,j t -t i,j u) ˜ k i,j ,
where

˜ k i,j = max{ k i,j - n-µ s=k+1 s i,j , 0}. Therefore ˜ k i,j = 0 if and only if m Pi (C) = k and in this case it is equal to k i,j . It follows that dk (t, u) = i=1,...,r j∈Ii m P i (C)=k (u i,j t -t i,j u) k i,j = Pi such that m P i =k H Pi (t, u) li ,
where l i is the number of infinitely near points of multiplicity k above P i , including P i . This proves [5, Conjecture 2].

Before moving on to the next section, from a computational as well as theoretical point of view, it is interesting to point out that C[t] is a principal ideal domain, and hence one can use the theory of invariant factors over principal domains in order to get that the matrix S p φ ,q φ (t, 1) is equivalent to a diagonal matrix whose nonzero elements are

d n (t, 1), d n (t, 1)d n-1 (t, 1), • • • , d n (t, 1)d n-1 (t, 1) . . . d 3 (t, 1)d 2 (t, 1), 0.
We will recall and use this property for proving Theorem 1.1. Notice also that a single Smith normal form computation of S p φ ,q φ (t, 1) yields all the singular factors of φ, after a linear change of coordinates of P 1 if necessary -see Lemma 3.3. Let us conclude this section with an illustrative example.

Example 2.1. Take the following parameterization of a rational algebraic plane curve of degree n = 10:

   a = s 2 (2 s + v) 2 (s + v) 6 b = s 3 (2 s + v) 5 3 s 2 + 2 sv + v 2 c = -(s + v) 10
The computation of the µ-basis gives µ = 4 and

p = (s + v) 4 x 1 + s 2 (2 s + v) 2 x 3 q = s 3 s 2 + 2 sv + v 2 (2 s + v) 3 x 1 -(s + v) 6 x 2
The associated Bézout matrix is then a 6 × 6-matrix from which we get, after dehomogenization u = 1 and a single Smith form computation, the following singular factors Although it is not always possible in general, we can recover here the multiplicity graph of the curve by using Theorem 1.1. For that purpose, we start by inspecting d 6 , the non-trivial singular factor with the highest index. We deduce that there is an irreducible singularity of multiplicity 6 corresponding to the parameter value t = -1. Looking at the other singular factors, we obtain that this singular point has a multiplicity 4 singular point in its first neighborhood and then has singular points of multiplicity 2 in its third, fourth and fifth neighborhood. So we obtain the first branch of the multiplicity graph, see Fig. 1. Now, by inspecting d 4 , we deduce that there is a singular point of multiplicity 4 which is formed by two irreducible branch-curves, one, say z 1 centered at t = -1/2 and another one, say z 2 centered at t = 0. The singular factor d 3 then shows that these two irreducible branches split up at the third neighborhood and have the multiplicities given in Fig. 1 in the second neighborhood (the horizontal bar stands for the equivalence relation of the multiplicity graph). Then, since d 2 does not vanish at t = -1/2 or t = 0 the mutliplicity graph at this multiplicity 4 point is known; see Fig. 1.

d 6 (t) = (t + 1) 6 , d 5 (t) = 1, d 4 (t) = 1 4 (2 t + 1) 2 (t + 1) 4 t 2 , d 3 (t) = 1 4 (2 t + 1) 2 t
Finally, a simple additional computation shows that the discriminant of d 2 /(t + 1) 6 is nonzero. Therefore, it only remains to add 3 ordinary double points to the multiplicity graph to complete it.

The case of ordinary curves

To prove Theorem 1.1, we will proceed by induction on the minimal length of a resolution of singularities of C. The initial step would then correspond to the case where C is an ordinary curve, i.e. C has only ordinary singularities. Although a proof of this result already appeared in [5, Theorem 5], we provide in this section an alternative proof for the sake of completeness and also as the preparation for the proof of Theorem 1.1.

We start by recalling very briefly some results of invariant factors and Fitting ideals theory we will need in the sequel. The reader may consult any book on Algebra like [10, Chapter III, §7 and Chapter XIX, §2] for proofs of these statements.

Let R be a principal ideal domain and M a finitely generated R-module. There exists a sequence of non invertible elements (α 1 , . . . , α ) such that i) For all i = 1, . . . , -1,

α i divides α i+1 . ii) M is isomorphic to R (α1) ⊕ R (α2) ⊕ • • • ⊕ R (α ) .
The elements α 1 , . . . , α are unique up to multiplication by a unit and are called the invariant factors of the R-module M . They can be recovered from the Fitting ideals of M , denoted F i (M ), since

F 0 (M ) = (α 1 . . . α ) ⊂ F 1 (M ) = (α 1 . . . α -1 ) ⊂ . . . ⊂ F -1 (M ) = (α 1 ) ⊂ F (M ) = F +1 (M ) = • • • = R
The smallest integer r such that F r (M ) = 0 is called the rank of M.

It is important to notice for further use that the Fitting invariants of M commute with localization: if S is a multiplicatively closed subset of R not containing the zero element, then for every integer ν ≥ 0 we have

(8) F ν (M )R S = F ν (M S )
Also, the Fitting invariants of M can be computed from any finite R-presentation of M . Such a presentation corresponds to a matrix, say A, with entries in R. The above results mean that this matrix is equivalent to a diagonal matrix, sometimes called the Smith normal form of A, whose nonzero elements are the invariant factors of M = coker(A).

We will also use later in the text the following result which is due to Thompson [START_REF] Robert | An inequality for invariant factors[END_REF].

α i1 α i2 • • • α im β j1 β j2 • • • β jm |γ i1+j1-1 γ i2+j2-2 • • • γ im+jm-m
whenever the integer subscripts satisfy

1 ≤ i 1 < i 2 < • • • < i m , 1 ≤ j 1 < j 2 < • • • < j m , i m + j m ≤ m + n.
Now, we examine the behavior of the singular factors under linear change of coordinates, it will also be very useful in the sequel.

Lemma 3.2. The singular factors of a proper parameterization do not depend neither on the choices of the µ-basis nor the coordinates of P 2 .

Proof. Indeed, a change of µ-bases or a change of coordinates of P 2 correspond to elementary transformation of the Sylvester matrix S p φ ,q φ (t, u). Therefore, its Fitting invariants remains unchanged so that the same holds for their codimension one part.

Recall that a linear change of coordinates of P 1 , that is to say an isomorphism

ψ : P 1 ∼ -→ P 1 : (t : u ) → (αt + βu : δt + γu )
where α, β, δ, γ ∈ C and αγ -βδ = 0, corresponds to the isomorphism of graded rings ("base change" map)

ψ : C[t, u] ∼ -→ C[t , u ] t → (γt -βu )/(αγ -βδ) u → (δt -αu )/(αγ -βδ).
The following lemma shows that computing singular factors "commutes" with linear changes of coordinates of P Hence, the lemma is proved.

Let M stand for the cokernel of the Sylvester matrix S p φ ,q φ (t, 1) defined in [START_REF] Chen | Computing singular points of plane rational curves[END_REF]. Note that M is a C[t]-module. Proposition 3.4. With above notation, we have F 0 (M ) = 0 and F 1 (M ) = (∆(t, 1)); in particular, M has rank 1. Moreover, F (M ) = R for all > n -µ.

Proof. Since (5) provides a finite presentation of M , one can compute the Fitting invariants of M as the determinantal ideals of ( 5), namely the Sylvester matrix of p φ and q φ . Thus, F 0 (M ) is generated by the determinant of this Sylvester matrix, which is equal to zero.

Recall the following classic property of the Sylvester matrix: the corank of the Sylvester matrix of two given polynomials is equal to the degree of the gcd of these two polynomials. So, by using Proposition 2.1 and Remark 1, we have that the Fitting invariants of M are supported on the singular locus of C and F (M ) = A for all > n -µ since there are no singular points on C of multiplicity > n -µ.

To prove that F 1 (M ) = (∆(t, 1)), we proceed as follows: let

P (s, v; t) = p φ (s,v;t,1) s-t v Q(s, v; t) = q φ (s,v;t,1)
s-t v . Applying the results given in [7, Theorem 2.2], we get that

(9) S 1 (p φ , q φ ; s, v) = Res (s,v) (P (s, v; t), Q(s, v; t)) (s -t v)v n-3 ,
where S 1 denotes the first subresultant polynomial operator applied to the sequence p φ , q φ with respect to the homogeneous variables (s, v). By taking leading coefficients with respect to s in both sides of the latter equality, we get ∆(t, 1) = SRes(p, q)(a(t, 1), b(t, 1), c(t, 1)) = Res (s,v) (P (s, v; t), Q(s, v; t)), the first equality is given by Theorem 2.2. Now, we can decompose the map (5) as the composition between:

C[t] ⊗ C C[s, v] n-µ-1 ⊕ C[t] ⊗ C C[s, v] µ-1 ψ1 → C[t] ⊗ C C[s, v] n-2 α ⊕ β → α p φ (s,v;t,1) s-tv + β q φ (s,v;t,1) s-tv and
C[t] ⊗ C C[s, v] n-2 ×(s-tv) → C[t] ⊗ C C[s, v] n-1 γ → (s -tv)γ.
By setting v = 1, it is now clear that all the minors of size (n -1) in the matrix S(a(t, 1), b(t, 1), c(t, 1)) are linear combinations of maximal minors of ψ 1 times maximal minors of the multiplication map in the right. If we build the matrices of these morphisms using the basis {(s-tv) j s n-1-j } instead of {s j v n-1-j } and compute the matrices of these linear transformations, then the morphism of multiplication by s -tv would have an n × (n -1) matrix of the form

       0 0 . . . 0 1 0 . . . 0 0 1 . . . 0 . . . . . . . . . . . . 0 0 . . . 1        .
This essentially implies that in these bases there is only one nonzero minor of ψ 1 to be considered, and due to [START_REF] Jia | Using Smith forms and µ-bases to compute all the singularities of rational planar curves[END_REF], it is easy to see that this minor is actually SRes(p, q)(a(t, 1), b(t, 1), c(t, 1)) = Res (s,v) (P (s, v; t), Q(s, v; t)). The proof follows straightforwardly from here.

Corollary 3.5. With the above notation, up to multiplicition by a nonzero constant in C we have d k (t, u) = 1 for all k > n -µ and

∆(t, u) = d n-µ (t, u) n-µ-1 d n-µ-1 (t, u) n-µ-2 • • • d 2 (t, u)
Proof. Perform a sufficiently general linear change of coordinates in P 2 in such a way that there are no singularities of C at {x 3 = 0}, and then apply Proposition 3.4 and Lemma 3.3.

Remark 2. If instead of P (s, v; t), Q(s, v; t) we used in the proof of Proposition 3.4

F (s,v;t,1) s-tv , G(s,v;t,1)
s-tv then we would not have ∆(t, 1) equals to the resultant of these two polynomials anymore, as we may loose some kind of uniqueness by allowing this symmetry (see for instance the statement of Theorem 3.1 in [START_REF] Gutierrez | D-resultant for rational functions[END_REF]). We will give a proper factorization of this polynomial in Section 6. Proposition 3.6. For any proper singularity Q on C, the polynomial H Q (t, u) defined in Proposition 2.1 divides d m Q (C) (t, u). Also, we have that H Q (t, u) and

d k (t, u) are coprime for all k > m Q (C) = deg H Q (t, u) .
Proof. Let S p,q (x 1 , x 2 , x 3 ) be the Sylvester matrix of the polynomials 3 i=1 x i p i (s, v) and 3 i=1 x i q i (s, v) with respect to the homogeneous variables (s, v). Its entries are linear forms in C[x 1 , x 2 , x 3 ]. Therefore, its determinantal ideals, denoted

I k (-), k = 1, . . . , n, are homogeneous ideals in C[x 1 , x 2 , x 3 ].
Then, by using Proposition 2.1 we deduce that

V (I k (S p,q (x 1 , x 2 , x 3 ))) = ∅ ⊂ P 2 C
for all k = 1, . . . , µ, as there cannot be any common factor of degree more than n -µ of these two forms after specializing the x i (see Remark 1). It follows then that

V (I k (S p,q (a(t, u), b(t, u), c(t, u)))) = ∅ ⊂ P 1 C
for all k = 1, . . . , µ, and this implies d k (t, u) = 1 for all k > n -µ. Now, assume for simplicity that Q = (0 : 0 : 1) as both H Q (t, u) and d m Q (C) (t, u) are invariant under linear changes of coordinates in P 2 C , and set m := deg(H Q (t, u)). As we did above, we have Q / ∈ V (I k (S p,q (x 1 , x 2 , x 3 ))) for all k = 1, . . . , n -m which implies that H Q (t, u) and d k (t, u) are relatively prime polynomials for all k > m. On the other hand, Q ∈ V (I n-m+1 (S p,q (x 1 , x 2 , x 3 ))), that is I n-m+1 (S p,q (x 1 , x 2 , x 3 )) ⊂ (x 1 , x 2 ), and hence

I n-m+1 (S p,q (a(t, u), b(t, u), c(t, u))) ⊂ (a(t, u), b(t, u)) ⊂ (H Q (t, u)) ⊂ C[t, u] It follows that H Q (t, u) divides d n-1 (t, u) n-m • • • d m+1 (t, u) 2 d m (t, u). As it is co- prime with d n-1 (t, u) n-m • • • d m+1 (t, u) 2 , we conclude that H Q (t, u) divides d m (t, u).
As a corollary we recover Theorem 5 in [START_REF] Chen | Computing singular points of plane rational curves[END_REF].

Corollary 3.7. The curve C has no infinitely near singularities if and only if for all k = 2, . . . , n -1

d k (t, u) = Q∈Singp(C) such that m Q (C)=k H Q (t, u)
where Sing p (C) denotes the subset of Sing(C) consisting exclusively of the proper singularities of the curve C.

In particular, if the curve C has only ordinary singularities then Theorem 1.1 holds.

Proof. By Proposition 3.6,

H Q (t, u) divides d m Q (t, u). Note that if Q = Q , then the polynomials H Q (t, u
) and H Q (t, u) are coprime as each of them provides an inversion formula for the parameterization around two different points. We deduce from here that Q∈Singp(C): m Q =k H Q (t, u) divides d k (t, u), and hence that

Q∈Singp(C): m Q =k H Q (t, u) m Q -1 divides d k (t, u) k-1 . Finally, this implies that Q∈Singp(C) H Q (t, u) m Q (C)-1 divides d n-µ (t, u) n-µ-1 d n-µ-1 (t, u) n-µ-2 • • • d 2 (t, u)
and that these two polynomials are equal (up to a nonzero multiplicative constant) if and only if for all k = 2, . . . , n -µ

d k (t, u) = Q∈Singp(C) such that m Q (C)=k H Q (t, u).
As the polynomial H Q (t, u) has degree m Q (C), we deduce that [START_REF] Lang | Algebra[END_REF] deg

  Q∈Singp(C) H Q (t, u) m Q (C)-1   = Q∈Singp(C) m Q (C)(m Q (C) -1).
But by Corollary 3.5

d n-µ (t, u) n-µ-1 d n-µ-1 (t, u) n-µ-2 • • • d 2 (t, u) = ∆(t, u),
and by Theorem 2.2, ∆(t, u) has degree equal to [START_REF] Lang | Algebra[END_REF] if and only if Sing p (C) = Sing(C), i.e. if and only if all the singularities are ordinary.

Proof of the main theorem

To prove Theorem 1.1 we will proceed by induction on the minimal length of a resolution of C. Define the following property for any integer N ≥ 0: (H N ) : Theorem 1.1 holds for any rational projective plane curve C whose singularities can be resolved after a sequence of N blow-ups, assuming that (5) is built from a µ-basis of a proper parameterization of C. Corollary 3.7 implies that the property (H 0 ) holds. Now, assume that C can be resolved by a sequence of N blow-ups and that (H N -1 ) holds. By hypothesis, there exists a sequence of rational projective plane curves

C = C 0 ← C = C 1 ← C 2 ← • • • ← C N -1 ← C N
such that each arrow corresponds to a blow-up (quadratic transformation) at a singular point and C N has only ordinary singularities. It is clear that C can be resolved by a sequence of N -1 blow-ups, so Theorem 1.1 holds for C by our inductive hypothesis.

The curve C is obtained by blowing-up C at a singular point P of C. To simplify the notation, we will hereafter denote by m ≥ 2 the multiplicity of P on C, by z i the irreducible branch-curve of C such that z i (t i ) = P, i = 1, . . . , i P and by 1 ≤ ν i ≤ m the multiplicity of P on z i . We will also denote by

• (P = P i 0 , P i 1 , . . .) the sequence of points infinitely near to P in the blow-up sequence of z i , • (m = m i 0 , m i 1 , . . .) the sequence of the corresponding multiplicities of the P i j as points on C, • and by (ν i = ν i 0 , ν i 1 , . . .) the sequence of the corresponding multiplicities as points on z i . Given f (t) ∈ C[t] and a ∈ C, the notation val a f (t) stands for the valuation of f (t) at a, that is to say the largest integer k such that (t -a) k divides f (t).

For i ∈ {1, . . . , i P }, let p i be the principal ideal in

C[t] generated by t -t i . Consider the R pi -module M pi . It satisfies F ν (M )R pi = F ν (M pi ) for all ν ∈ N.
From the proof of Proposition 3.6, we already know that F 0 (M pi ) = 0 and that

F j (M pi ) = R pi for all j ≥ m, so that val ti (d n-1 (t)) = val ti (d n-2 (t)) = • • • = val ti (d m+1 (t)) = 0
Moreover, from Proposition 3.4 and Theorem 2.2 we obtain that

F 1 (M pi ) is gener- ated by d m (t) m-1 d m-1 (t) m-2 . . . d 3 (t) 2 d 2 (t) and (11) val ti d m (t) m-1 d m-1 (t) m-2 . . . d 3 (t) 2 d 2 (t) = m k=2   (k -1) m i j =k ν i j   .
Recall that C is obtained after blowing up a point in C. We want to assume w.l.o.g. that the point being blown up is (0 : 0 : 1), and that the quadratic transformation is X = X and Y = X Y . In order to do this correctly, we will perform a general change of coordinates of P 1 and of P 2 that will simplify the blow-up computations.

Recall that the R-module M is not affected by a change of coordinates of P 2 thanks to Lemma 3.2, and Lemma 3.3 shows that Theorem 1.1 can be proved w.l.o.g. in any choice of coordinates of P 1 . After then a general change of coordinates in both spaces, we can assume w.l.o.g. that (i) our singular point above is P = (0 : 0 : 1), (ii) the only singularity of C on the line {x 1 = 0} is P , (iii) the line {x 1 = 0} is not tangent to C at P , (iv) φ(1 : 0) is not a singular point of C, (v) (0 : 1 : 0) / ∈ C and (1 : 0 : 0) / ∈ C, i.e. gcd(a, c) = gcd(b, c) = 1, (vi) φ(1 : 0) ∈ {x 3 = 0}, which essentially means that deg t (c(t, u)) < n, (vii) there are no singularities of C on the line {x 3 = 0}. Now, since we assumed (i)-(iii), we apply the quadratic transformation X = X and Y = X Y so that the exceptional divisor corresponds to the line X = 0. The curve C is then properly parameterized on affine coordinates as follows:

A 1 C φ -→ A 2 C : s 0 → a(s 0 , 1) c(s 0 , 1) , b(s 0 , 1) c(s 0 , 1) .
We write a(s,

1) = h(s)ã(s), b(s, 1) = h(s) b(s),
with gcd(ã, b) = 1. Note that with the notation of Proposition 2.1, we have

(12) h(s) = H P (s, 1) = λ * i P i=1 (t -t i ) νi
with λ * a nonzero constant in C. By (iv), we have m = i P i=1 ν i , and by (v), C has degree 2n -ν and is properly parameterized by

A 1 C φ -→ A 2 C : s 0 → a(s 0 , 1) c(s 0 , 1) , b(s 0 ) ã(s 0 ) = a(s 0 , 1)ã(s 0 ) ã(s 0 )c(s 0 , 1) , c(s 0 , 1) b(s 0 ) ã(s 0 )c(s 0 , 1) .
From here, it is not hard to see that a µ-basis associated to φ is given by

p = ãh (s, v)x 2 -bh (s, v)x 3 , q = c(s, v)x 1 -a(s, v)x 3 ,
with ãh and bh being the homogenizations of ã and b respectively up to degree n -ν. Now, let M be the R-module built from this µ-basis, i.e.

M := coker Sylv (s,v) ãh (s, v)c(t, 1) b(t) -bh (s, v)ã(t)c(t, 1), c(s, v)a(t, 1)ã(t) -a(s, v)ã(t)c(t, 1) .
Recall from ( 12) that H P (s, v) is the homogenization of h(s). As we have

ã(t) 2 (b(s, v)c(t, 1) -c(s, v)b(t, 1)) = -b(t) (c(s, v)a(t, 1)ã(t) -a(s, v)ã(t)c(t, 1)) + ã(t)H P (s, v) bh (s, v)c(t, 1)ã(t) -ãh (s, v)c(t, 1) b(t) ,
we deduce, after setting v = 1, that for any prime p of C[t] such that ã(t) / ∈ p, the multiplication by b(s, 1)c(t, 1) -b(t, 1)c(s, 1) in the quotient ring

R p [s]/ c(s, 1)a(t, 1)ã(t) -a(s, 1)ã(t)c(t, 1) = R p [s]/ c(s, 1)a(t, 1) -a(s, 1)c(t, 1)
decomposes as the multiplication by h(s) times the multiplication by b(s)c(t, 1)ã(t) -ã(s)c(t, 1) b(t) (notice that since ã(t) / ∈ p, one can here cancel it out without changing the valuations of the above quantities). The leading coefficient of a(s, 1)c(t, 1) -a(t, 1)c(s, 1) as a polynomial in s is equal to a n c(t, 1) by (vi), and we have c(t i , 1) = 0 as otherwise we will have a singularity of C at {x 3 = 0}, a contradiction with (vii). So, we can use the following Lemma 4.1 ([2, §3.3]). Given a commutative ring A and two polynomials f (X), g(X) in A[X] such that the leading coefficient of f is a unit in A, then the cokernel of the Sylvester matrix of f (X) and g(X) is isomorphic, as an A-module, to the cokernel of the multiplication by g(X) in the quotient ring A[X]/(f (X)).

We deduce that for every prime p i = (t -t i ), the cokernel of the localized Sylvester matrix M is isomorphic to the cokernel of the product of the matrices associated to the multiplication by h(s) times the multiplication by b(s)c(t, 1)ã(t) -ã(s)c(t, 1) b(t) in R pi [s]/ c(s, 1)a(t, 1) -a(s, 1)c(t, 1) . Lemma 4.2. Let p i = (t -t i ) with φ(t i : 1) a singular point of C. The invariant factors of the multiplication map by h(s) in the quotient ring R pi [s]/(a(s, 1)c(t, 1)a(t, 1)c(s, 1)) are

α 1 = 1, . . . , α n-m = 1, α n-m+1 = a(t, 1), α n-mi+2 = a(t, 1), . . . , α n = a(t, 1).
In particular, we have

val ti (α k ) = 0, 1 ≤ k ≤ n -m, val ti (α k ) = ν i , n -m + 1 ≤ k ≤ n.
Proof. As the leading coefficient of a(s, 1)c(t, 1) -a(t, 1)c(s, 1) as a polynomial in s is invertible R pi [t], then by using Lemma 4.1, it turns out that the cokernel of the multiplication map is actually isomorphic to the cokernel of the following Sylvester matrix: coker Sylv s (a(s, 1)c(t, 1) -a(t, 1)c(s, 1), h(s)) ⊗ R pi [t] cokerSylv s (a(t, 1)c(s, 1), h(s)) ⊗ R pi [t]. The matrix Sylv s (a(t, 1)c(s, 1), h(s)) has m = deg(h) rows multiplied by a(t, 1), and also has maximal rank as Res s (c(s, 1), h(s)) = 0. This means that all the Fitting ideals of this matrix are not zero, and moreover from i = n + 1 to n + h they are multiples of a(t, 1) i-1 . From here, the claim follows straightforwardly. Now we are ready for dealing with the inductive step and complete the proof of the main Theorem. As we already know that the singular factors of M are supported in the singularities of φ by Proposition 3.4, it is enough to prove the claim for localizations of the type M p0 with p 0 = (t -t 0 ), φ(t 0 : 1) being a singular point of C.

Let us pick then t 0 ∈ C with this property. As c(t 0 , 1) = 0 due to (vii) then, as we already used above, we have coker Sylv s (a(s, 1)c(t, 1) -c(s, 1)a(t, 1), b(s, 1)c(t, 1) -c(s, 1)b(t, 1)

) ⊗ R p0 coker M h M b(s)c(t,1)ã(t)-ã(s)c(t,1) b(t) ,
where M * is a matrix of the multiplication map in R p0 [s]/(a(s, 1)c(t, 1)-c(s, 1)a(t, 1)).

If h(t 0 ) = 0, then the character of φ(t 0 : 1) does not change before and after the blow up. In addition, M h is an isomorphism and hence coker M h M b(s)c(t,1)ã(t)-ã(s)c(t,1) b(t)

coker M b(s)c(t,1)ã(t)-ã(s)c(t,1) b(t)

coker Mp0 , M being the matrix of the syzygies of φ. Here, we apply the inductive hypothesis and conclude. Suppose now that h(t 0 ) = 0. This means that t 0 ∈ {t 1 , . . . , t i P }. Suppose w.l.o.g. that t 0 = t 1 .

After localization, we denote the invariant factors of the matrix corresponding to the blow-up curve C with

β 1 = 1, . . . , β d-m = 1, β d-m+1 = dm , β d-m+2 = dm dm-1 , . . . , β d-1 = dm dm-1 . . . d2 , β d = 0
and those of the matrix corresponding to C are set as Therefore, we deduce that

γ 1 = 1, . . . , γ d-m = 1, γ d-m+1 = d m , γ d-m+2 = d m d m-1 , . . . , γ d-1 = d m d m-1 . . .
val t1 (d m (t) m-1 d m-1 (t) m-2 . . . d 3 (t) 2 d 2 (t)) = m-1 i=1 val t1 (d m . . . d m-i+1 ) = (m -1)ν 1 + m i=2 i + val t1 ( dm (t) m-1 dm-1 (t) m-2 . . . d3 (t) 2 d2 (t)).
By [START_REF] Park | Effective computation of singularities of parametric affine curves[END_REF] we know that the left hand side of this equality is equal to

m k=2   (k -1)
m 1 i =k ν 1 i   .
On the other hand, using our inductive hypothesis, the right hand side of this equality must be equal to

m k=2   (k -1)
m 1 i =k ν 1 i   + i m-i+d .
Comparing the two above quantities, we deduce that i m-i+d = 0 and therefore that all i = 0 for all i = 2, . . . , m. It follows that d m (t) = (t -t 1 ) ν1 dm (t) and that d i (t) = di (t) for all i = 2, . . . , m -1. Therefore, we deduce that (H N ) holds.

Cokernels of resultant matrices

In this section, we show that the singular factors can be computed not only from the Sylvester matrix of the µ-basis, but from a collection of matrices of smaller matrix known as the hybrid Bézout matrices.

Let R be a commutative ring, m, n ∈ N with n ≥ m ≥ 1, and

f (t) = a 0 + a 1 t + . . . + a n t n , g(t) = b 0 + b 1 t + . . . + b m t m polynomials in R[t].
For k = 0, . . . , m -1, set

f k (t) := a n t n-m+k + a n-1 t n-m+k-1 + . . . + a m-k , g k (t) := b m t k + b m-1 t k-1 + . . . + b m-k ,
and define p k (t) := g k (t)f (t) -f k (t)g(t). Note that as

f (t) = f k (t)t m-k + a m-k-1 t m-k-1 + . . . + a 1 t + a 0 g(t) = g k (t)t m-k + b m-k-1 t m-k-1 + . . . + b 1 t + b 0 , then it turns out that deg(p k (t)) ≤ n -1 ∀ k = 0, . . . m -1.
For j ∈ {0, 1, . . . , m}, we consider the following map of R-modules of finite rank:

ψ j : R j ⊕ R[t] ≤m-j-1 ⊕ R[t] ≤n-j-1 → R[t] ≤m+n-j-1 e i , a(t), b(t) → p m-j+i-1 (t) + a(t)f (t) + b(t)g(t)
It is easy to see that ψ 0 is the Sylvester map of (f, g). We will call ψ m the hybrid Bézout map of these polynomials, and its matrix in the monomial bases is what we have referred to as the hybrid Bézout matrix all along the text. If n = m, we just call them Bézout map and Bézout matrix respectively. For 1 ≤ j ≤ m -1, ψ j it is also a hybrid type map in the sense that it has a piece of Sylvester type and a piece of Bézout.

In [START_REF] Apéry | Élimination: le cas d'une variable. Collection Méthodes[END_REF]Proposition 18] it is shown that if the leading coefficients of f and g generate R, then the cokernels of ψ 0 and ψ m are isomorphic. The following result is a generalization of this fact. In particular, if d = 1 we then have coker(ψ j ) ∼ = coker(ψ k ) for all j, k.

Remark 3. Note that as d = 0, then at least one between a n and b m must be different from zero.

Proof. Fix j ∈ {1, . . . m -1} and consider the following commutative diagram of R-modules:

(14) 0 ↓ R j+1 ⊕ R[t] ≤m-j-2 ⊕ R[t] ≤n-j-2 ψj+1 ---→ R[t] ≤m+n-j-2 ↓ α ↓ i R j ⊕ R[t] ≤m-j-1 ⊕ R[t] ≤n-j-1 ψj -→ R[t] ≤m+n-j-1 ↓ ↓ coker(α) β -→ coker(i) ↓ ↓ 0 0
where β is the induced morphism of cokernels, i the canonical injection, and α is defined as [START_REF] Song | Axial moving lines and singularities of rational planar curves[END_REF] α(0, a(t), b(t)) = (0, a(t), b(t)) α(e 1 , 0, 0) = (0, g m-j-1 (t), -f m-j-1 (t)) α(e i+1 , 0, 0)

= (e i , 0, 0) for i > 1.

Clearly, we have coker(i) ∼ = t m+n-j-1 R. On the other hand, it is easy to see that

(16) im(α) ∼ = R j ⊕ R[t] ≤m-j-2 ⊕ R[t] ≤n-j-2 ⊕ (b m t m-j-1 , -a n t n-j-1 )R.
Let u, v, w, z ∈ R such that ua n + vb m = d, wd = a n , zd = b m . As d is not a zero divisor in R, then we have uw + vz = 1, and hence we have an isomorphism (t m-j-1 , 0)R ⊕ (0, t n-j-1 )R ∼ = (ut m-j-1 , vt n-j-1 )R ⊕ (zt m-j-1 , -wt n-j-1 )R, and from here, using ( 16), we then get

coker(α) ∼ = (ut m-j-1 , vt n-j-1 )R ⊕ zt m-j-1 , -wt n-j-1 R/ d .
With these identifications, it is straightforward to compute β explicitly:

β r 1 (ut m-j-1 , vt n-j-1 ) + [r 2 ] zt m-j-1 , -wt n-j-1 = dr 1 t m+n-j-1 for r 1 ∈ R, [r 2 ] ∈ R/ d . We deduce, then (17) ker
(β) ∼ = R/ d , coker(β) ∼ = R/ d .
The claim now follows straightforwardly by applying the Snake Lemma to [START_REF] Sendra | Tracing index of rational curve parametrizations[END_REF].

The following lemma will imply that the cokernels of all the hybrid matrices of µ-bases are isomorphic and hence that the Fitting invariants of all type of resultant matrices are the same. Lemma 5.2. Let p φ (s, 1; t), q φ (s, 1; t) ∈ C[s, t] be the specialization in v = 1 of the polynomials defined in (4). If φ(1 : 0) is not a singular point on C, then the leading coefficients of these two polynomials with respect to s are coprime in C[t].

Proof. Note that the leading coefficients of 3 i=1 p i (s, 1)x i and 3 i=1 q i (s, 1)x i are two linear forms, say L p (x 1 , x 2 , x 3 ) and L q (x 1 , x 2 , x 3 ) in C[x 1 , x 2 , x 3 ] that are Clinearly independent, otherwise by making a reversible linear combination of these elements, one could replace the µ-basis (p φ , q φ ) with (p φ , q φ ) with deg(q φ ) < n -µ, a contradiction. Now, it is easy to see that these two linear forms intersect at φ(1 : 0), and as they are linearly independent, this is their only point of intersection in P 2 . From here it follows that L p (a(t, 1), b(t, 1), c(t, 1)) and L q (a(t, 1), b(t, 1), c(t, 1)) are necessarily coprime in C[t], otherwise they will have a common factor h(t) of positive degree, and we would have that φ(t 0 : 1) = a(t 0 , 1) : b(t 0 , 1) : c(t 0 : 1) = φ(1 : 0) for every t 0 such that h(t 0 ) = 0, contradicting the fact that φ(1 : 0) is not a singularity of C.

Corollary 5.3. The singular factors of all the matrices ψ j p φ (s, v; t, u), q φ (s, v; t, u) in C[t, u] are the same for any j = 0, . . . , m, and for any {p, q} µ-basis of φ.

Proof. If φ(1 : 0) is not a singular point on C, then the result follows from Theorem 5.1 and Lemma 5.2. If this is not the case, by applying a linear change of coordinates in P 1 , we may assume that φ(1 : 0) is not a singular point on C and the result then follows from Lemma 3.3 which holds not only for the Sylvester matrix ψ 0 , but also for all the matrices ψ j , j = 0, . . . , m (the same proof works verbatim).

On the invariant factors of the D-resultant matrix

In this section, we will describe the invariant factors of a matrix closely related to S p φ ,q φ (t, u) that was originally studied in [START_REF] Chionh | On the minors of the implicitization Bézout matrix for a rational plane curve[END_REF] in order to compute the singularities of C. As a consequence we obtain a complete factorization of the D-resultant for rational polynomials, introduced in [START_REF] Gutierrez | D-resultant for rational functions[END_REF].

Let B(x 1 , x 2 , x 3 ) ∈ C[x 1 , x 2 , x 3 ] n×n be the Bézout matrix associated to the polynomials a(s, v)x 3 -c(s, v)x 1 and b(s, v)x 2 -c(s, v)x 3 with respect to the homogeneous variables (s, v), and S(x 1 , x 2 , x 3 ) ∈ C[x 1 , x 2 , x 3 ] n×n be the Sylvester matrix associated to p(s, v) = 3 i=1 x i p i (s, v) and q(s, v) = 3 i=1 x i q i (s, 1) with respect to (s, v). Here, as usual, {p, q} is a µ-basis of (a, b, c). Proposition 6.1. There exists an invertible N ∈ C n×n such that [START_REF] Walker | Algebraic Curves[END_REF] B(x 1 , x 2 , x 3 ) = x 3 N S(x 1 , x 2 , x 3 ).

Proof. Set B = B i,j (x 1 , x 2 , x 3 ) 0≤i,j≤n-1 . We then have n-1 i=0 n-1 j=0 B i,j (x 1 , x 2 , x 3 )s i t j = 1 s-t a(s, 1)x 3 -c(s, 1)x 1 b(t, 1)x 3 -c(t, 1)x 2 -a(t, 1)x 3 -c(t, 1)x 1 b(s, 1)x 3 -c(s, 1)x 2 .

By setting x 3 = 0 above, it is easy to see that the right hand side vanishes, and hence we have B i,j (x 1 , x 2 , 0) = 0 for all i, j. This shows that B i,j (x 1 , x 2 , x 3 ) = x 3 A i,j (x 1 , x 2 , x 3 ) i, j = 0, . . . , n -1 with A i,j (x 1 , x 2 , x 3 ) a homogeneous linear form. If now we substitute A i,j (a(s, 1), b(s, 1), c(s, 1))s i   t j = 0. As c(s, 1) = 0, this shows that for all i = 0, . . . , n -1, L i (s, v; x 1 , x 2 , x 3 ) := n-1 j=0 A i,j (x 1 , x 2 , x 3 )s i v n-1-i is a syzygy of (a, b, c) of degree n -1. Moreover, the fact that det(B) = 0 (as we have assumed gcd(a, b, c) = 1) shows then that det(A ij (x 1 , x 2 , x 3 )) = 0 and this implies that the family {L 0 , . . . , L n-1 } is a basis of the C-vector space of syzygies of (a, b, c) of degree n -1.

On the other hand, it is easy to check that the family {v n-µ-1 p, v n-µ-2 sp, . . . , s n-µ-1 p, v µ-1 q, v µ-2 sq, . . . , s µ-1 q} is another basis of the same C-vector space. This is due to the fact that the matrix of coefficients of this family with respect to the monomial basis is actually S(x 1 , x 2 , x 3 ), whose determinant gives the implicit equation. So, as both sets are bases of the same space, we then get that there exists an invertible N ∈ C n×n such that A i,j (x, y, z) = N S.

From here, the proof follows straightforwardly.

As a direct application of Proposition 6.1 we get the explicit description of the invariant factors of the matrix B F,G (t, u) stated in the introduction. Denote with D i (B F,G ) the gcd of the (n -i)-minors of B F,G (t, u). Theorem 6.2. D 0 (B F,G ) = 0 and for i = 1, . . . , n -1, D i (B F,G ) = c(t, u) n-i d n (t, u) n-i d n-1 (t, u) n-i-1 . . . d i+1 (t, u).

Proof. Set x 1 → a(t, u), x 2 → b(t, u), x 3 → c(t, u) in [START_REF] Walker | Algebraic Curves[END_REF] and compute the invariant factors on both sides.

As an immediate consequence, we also get the following Actually, the D-resultant in [START_REF] Gutierrez | D-resultant for rational functions[END_REF] was defined for an affine parameterization of the form A(t) C(t) , B

Figure 1 .

 1 Figure 1. Multiplicity graph of the degree 10 rational plane curve given in Example 2.1

Theorem 3 . 1 .

 31 Let A, B, C be three square matrices with entries in R such that AB = C. If α 1 |α 2 | . . . |α n , β 1 |β 2 | . . . |β n , γ 1 |γ 2 | . . . |γ n are the invariant factors of A, B, and C respectively, then

  d 2 , γ d = 0 Applying Thompson's Theorem (Theorem 3.1), we deduce that, for all 1≤ i ≤ m-1 α 1 . . . α d-m+1 β 1 . . . β d-m β d-m+i | γ 1 . . . γ d-m γ d-m+i , that is to say (t -t 1 ) ν1 dm . . . dm-i+1 | d m . . . d m-i+1It follows that there exist non-negative integers 2 , . . . , m-1 such that, for all i = 1, . . . , m -1, we have val t1 (d m . . . d m-i+1 ) = ν 1 + m-i+1 + val t1 ( dm . . . dm-i+1 )

Theorem 5 . 1 .

 51 Suppose that there exists a nonzero divisor d ∈ R, d = 0 such that a n , b m = d . Then the following sequence is exact (13) R/ d → coker(ψ j+1 ) → coker(ψ j ) → R/ d → 0 ∀j = 0, . . . m -1.

x 1 →

 1 a(s, 1), x 2 → b(s, 1), x 3 → c(s, 1) we again have that the whole Bezoutian polynomial vanishes. So we conclude that c(s, 1)

Theorem 6 . 3 (

 63 Factorization of the D-resultant, case of same denominator).

  u) = c(t, u) n-1 d n (t, u) n-1 d n-1 (t, u) n-2 . . . d 2 (t, u). Proof. Recall that Res (s,v) F (s,v;t,u) su-tv , G(s,v;t,u)su-tv is equal to the first subresultant of the pair F (s, v; t, u), G(s, v; t, u). Set i = 1 in Theorem 6.2 and use Proposition 3.4.

  (t) D(t) with gcd(A, C) = gcd(B, D) = 1. In order to tackle this situation, set n 1 := max{deg(A), deg(C)}, n 2 := max{deg(B), deg(D)}. Let Ã(s, v), C(s, v) (resp. B(s, v), D(s, v)) be the homogenizations of A and C (resp. B and D) to degree n 1 (resp. n 2 ). The D-resultant of the curve given by

  + 74 t 5 + 71 t 4 + 48 t 3 + 21 t 2 + 6 t + 1

					,
	d 2 (t) =	1 43	43 t 6 + 74 t 5 + 71 t 4 + 48 t 3 + 21 t 2 + 6 t + 1 (t + 1)	6
	and reduced singular factors
	d6 (t) = d 6 (t), d5 (t) = d 5 (t) = 1, d4 (t) =	1 4	(2 t + 1)	2 t 2 , d3 (t) = 1,
	d2 (t) =	1 43	43 t 6

  are the singular factors of the parameterization φ • ψ :P 1 → P 2 of C.Proof. It is not hard to check that if {p, q} is a µ-basis of φ then ψ (p), ψ (q) is a µ-basis of φ • ψ. Now, the map ψ gives a C[t, u]-module structure to C[t , u ] so that the Sylvester matrix obtained by the change of coordinates ψ is nothing but S p φ ,q φ (t, u) ⊗ C[t,u] C[t , u ]. Therefore, by the right-exactness of tensor product we deduce that the Fitting ideals of the cokernel of S p φ ,q φ (t, u) ⊗ C[t,u] C[t , u ] are equal to the Fitting ideals of S p φ ,q φ (t, u) tensored with C[t , u ] over C[t, u]. It follows that the same property holds for the codimension one part of these Fitting ideals.

1 . Lemma 3.3. Let d 1 (t, u), d 2 (t, u), . . . , d n (t, u) be the singular factors of the parameterization φ of C and let ψ be a linear change of coordinates in P 1 . Then, the homogeneous polynomials in C[t , u ] ψ (d 1 (t, u)), ψ (d 2 (t, u)), . . . , ψ (d n (t, u))

Both authors were partially supported by the bilateral (French-Spanish) collaboration PAI Picasso HF 2006-0220 . The second author was also partially supported by the research project MTM2007-67493 (Spain).

this parameterization is defined in [START_REF] Gutierrez | D-resultant for rational functions[END_REF] as Denote with C ⊂ P 2 the curve defined by the closure of the image of the parameterization given by A(t0) C(t0) , B(t0) D(t0) , with t 0 ∈ C. We assume that this parameterization is proper, and hence C is birationally parametrized by ν :

. The polynomials ã, b, c have then the same degree n ≥ max{n 1 , n 2 }, and no common factors. Hence, the degree of C is then n and we have c(t, u) = h(t, u) C(t, u) = q(t, u) D(t, u), with h(t, u) and q(t, u) coprimes. We also get ã(t, u) = h(t, u) Ã(t, u) and b(t, u) = q(t, u) B(t, u), and gcd(ã(t, u), b(t, u), c(t, u)) = 1. We will denote with ∆ ν (t, v) the polynomial defined in (7) associated with the parameterization ν. A complete factorization of this polynomial in terms of the singularities of C and its multiplicity graph is given in Corollary 3.5.

Finally, let δ(t, u) := gcd(B(t, u), D(t, u)). Note that we have

Theorem 6.4 (Factorization of the D-resultant, case of different denominators).

If the parameterization defined by

is proper, then with the notation established above, we have

Remark 4. Note that (21) generalizes (19), as in the case of common denominators we have h(t, u) = q(t, u) = 1 and δ(t, u) = c(t, u).

Proof. We apply Theorem 6.3 to the parameterization given by (ã : b : c) and have

where Ƌ, b,c (t, u)

, which actually factorizes as

with λ 0 := Res (s,v) h(s, v), q(s, v) = 0. As B(s,v)h(t,u)δ(t,u)-B(t,u)h(s,v)δ(s,v)

su-tv can be written as

su -tv , and using the fact that D(t, u) = h(t, u)δ(t, v) we get that

Note that ( Ãh Ch , Bq Dq ) is the minimal expression that makes the denominators Ch = Dq, hence h must be coprime with B otherwise the second fraction would simplify. So, we have Res (s,v) (h(s, v), B(s, v)) = λ * = 0, and then

By using the Poisson formula for the resultant, we have that -up to a nonzero constant-

So, we get

The computation of Res (s,v)

, q(s, v) follows the same line: one has that -up to a nonzero constant-C(t, u) = q(t, u)δ(t, u) and then

for λ 2 = 0. Collecting all this information, we get ∆ã, b,c (t, u) = λ c(t, u) n-deg(δ) h(t, u) n-deg(q)-2 q(t, u) n-deg(h)-2 ∆ Ã, C, B, D (t, u)

with λ = 0. And now we use (22) to get that -up to a constanth(t, u) n-deg(q)-2 q(t, u) n-deg(h)-2 ∆ Ã, C, B, D (t, u) = c(t, u) deg(δ)-1 ∆ν (t, u) = h(t, u)q(t, u)δ(t, u) deg(δ)-1 ∆ν (t, u).

From here, we deduce h(t, u) deg(h)-1 q(t, u) deg(q)-1 ∆ Ã, C, B, D (t, u) = δ(t, u) deg(δ)-1 ∆ ν (t, u), which is the claim we wanted to prove.


François Fouquet

Grégory Nain
email: gregory.nain@uni.lu

Brice Morin
email: brice.morin@sintef.no

Erwan Daubert

Olivier Barais

Noël Plouzeau

Jean-Marc Jézéquel

An Eclipse Modelling Framework Alternative to Meet the Models@Runtime Requirements

Keywords: Model@Runtime, EMF, adaptation

Models

Introduction

The emergence of new classes of systems that are complex, inevitably distributed, and that operate in heterogeneous and rapidly changing environments raise new challenges for the Software Engineering community [START_REF] Cheng | Software engineering for self-adaptive systems: A research roadmap[END_REF]. Examples of such applications include those from crisis management, health-care and smart grids. These applications can be deployed on top of a distributed infrastructure that goes from micro-controller to the Cloud. These systems must be adaptable, flexible, reconfigurable and, increasingly, self-managing [START_REF] Kephart | The Vision of Autonomic Computing[END_REF]. Such characteristics make systems more prone to failure when executing and thus the development and study of appropriate mechanisms for continuous design and runtime validation and monitoring are needed. In the Model-Driven Software Development area, research effort has focused primarily on using models at design, implementation, and deployment stages of development. This work has been highly productive with several techniques now entering the commercialization phase. The use of model-driven techniques for validating and monitoring run-time behavior can also yield significant benefits. A key benefit is that models can be used to provide a richer semantic base for runtime decision-making related to system adaptation and other runtime concerns such as verification and monitoring. Then, Models@Runtime [START_REF] Blair | Models@run.time[END_REF] denotes model-driven approaches aiming at taming the complexity of software and system dynamic adaptation. It basically pushes the idea of reflection [START_REF] Morin | Taming Dynamically Adaptive Systems with Models and Aspects[END_REF] one step further by considering the reflection layer as a real model: "something simpler, safer or cheaper than reality to avoid the complexity, danger and irreversibility of reality" [START_REF] Rothenberg | The Nature of Modeling[END_REF], which enables the continuous design of complex, adaptive systems.

A natural approach to Models@Runtime is to use MDE techniques, in particular those based on the Eclipse Modeling Framework (EMF) 4 . For example, Frascati [START_REF] Seinturier | A Component-Based Middleware Platform for Reconfigurable Service-Oriented Architectures[END_REF] (implementing the Service Component Architecture standard) uses EMF for the design and runtime tooling of its architecture description language. However, EMF has primarily been thought to support design-time activities and its use to support Models@Runtime reaches some limitations. This paper elicits specific Models@Runtime requirements, discusses the benefits and limitations of EMF in this context, and presents an alternative modelling framework implementation to meet these requirements.

The outline of this paper is the following. Section 2 briefly presents the Models@Runtime paradigm and its requirements. An overview of EMF benefits and its limitations regarding its use at runtime are given by Section 3. The contribution of this paper, the Kevoree Modeling Framework(KMF), is described in Section 4. Section 4.2 gives an evaluation of our alternative implementation in comparison to EMF. This contribution is discussed w.r.t. related work in Section 5. Section 6 concludes on about this work and presents future work.

Models@Runtime Requirements

The Models@Runtime paradigm promises a new approach to MDE, by fading the boundary between design-time (the typical phase where MDE is employed) and runtime. More precisely, the goal of Models@Runtime is to enable the continuous design, evolution, verification of eternal running software systems [START_REF] Blair | Models@run.time[END_REF]. A typical usage of Models@Runtime is to manage the complexity of dynamic adaptation or verification in complex, distributed and heterogeneous systems, by offering a more abstract and safer abstraction layer on top of the running system than reflection. Heterogeneity and distribution creates specific requirements for Models@Runtime infrastructure. (i) The overhead inevitably induced by this advanced reflection layer should not prevent smaller (i.e. resource constrained) devices to benefit from the advantages of Models@Runtime (e.g. Java Embedded, Android,. . . ). Modeling framework and all its needed dependencies must be compatible with such devices in terms of memory footprint. (ii) The use of models to drive the running configuration of a software system should enable required features of a distributed reflection layer such as efficient (un)-marshalling, efficient model cloning and model thread safety access.

Reduced Memory Footprints

The memory footprint of a Models@Runtime engine basically determines the types of nodes able to run this engine. The more demanding is the Models@Runtime engine in terms of memory, the more difficult it is to deploy it on the smallest devices (e.g. Android phones, gateways with low power CPUs), and the more centralized should the adaptation/verification be. Lazy loading technique can be used to virtually reduce the memory overhead by not loading unused model elements. In this case, only a few large devices would be able to reason and make decisions for all the smaller devices. This would reduce the reliability of the overall adaptation and verification process: if the large devices fail, the overall system cannot safely adapt anymore. Moreover, model exchanges for the synchronization of the system in this strategy would dramatically increase network load.

Dependencies

The number and size of dependencies is also an important criteria. Each device must provision all the dependencies needed by the modeling framework to run a Models@Runtime based distributed application. As these applications are based on a structured data model, this data model should not generate useless dependencies. Heavy dependencies would indeed increase the time needed to initialize a node or update it when new versions of those third parties are available.

Thread Safety

A Models@Runtime is generally used in highly concurrent environment. For instance, different probes integrated in a device update a context model. This model is then used for triggering the adaptation reasoning process. This context model should enable safe and consistent read and write for the reasoners to take accurate decisions. The Models@Runtime infrastructure must ensure that the multiple threads of your application can access and modify the models without worrying about the concurrent access details. In particular, it should be possible to navigate in parallel the collections defined in the model to implement fast, yet safe, validation or reasoning algorithms on multi-core/thread nodes.

Efficient Model (Un)Marshalling and cloning

A device should be able to locally clone its own model for verification or reasoning purposes so that it can reason on a fully independent and safe representation of itself, which can later on be re-synchronized with the current model. Also, devices should be offered efficient means to communicate their Models@Runtime to neighbors so that collective decisions can be made. The Models@Runtime infrastructure must thus provide efficient model cloning and (un)marshalling capabilities.

Connecting Model@Runtime to classical design tools

This requirement is directly bound to the first goal of fading the boundary between design-time and runtime. A Models@Runtime infrastructure must provide a transparent compatibility with design environments. For example, a graphical simulator used for the design of finite state machines (FSM) should be pluggable on an application that keeps FSM at runtime and serve as a debugger or a monitor of the running system [START_REF] Ballagny | Mocas: A state-based component model for self-adaptation[END_REF][START_REF] Georgas | Using architectural models to manage and visualize runtime adaptation[END_REF].

EMF Benefits and Limitations

A natural way to implement a Models@Runtime platform is to rely on tools and techniques well established in the MDE community, and in particular, the de facto EMF standard. This section provides a brief overview of EMF and then discusses the suitability of this modelling framework with respect to the requirements identified in the previous section.

EMF Overview

EMF is an eMOF implementation and code generation facility for building tools and other applications based on a structured data model. From a model specification, EMF provides tools and runtime support to create Domain Specific Language (DSL) on top of the Eclipse platform. Most important, EMF provides the foundation for interoperability with other EMF-based tools and applications using a default serialization strategy based on XMI. Consequently, EMF has been used to implement a large set of tools and thus, evolved into an efficient Java implementation of a core subset of the MOF API.

Advantages.

As a first real benefit, EMF provides a transparent compatibility of the Models@Runtime infrastructure with several design environments. All the tools built with frameworks such as Xtext [START_REF] Merkle | Textual modeling tools: overview and comparison of language workbenches[END_REF][START_REF] Eysholdt | Xtext: implement your language faster than the quick and dirty way[END_REF], EMFText [START_REF] Heidenreich | Derivation and refinement of textual syntax for models[END_REF], GMF [START_REF] Seehusen | An evaluation of the graphical modeling framework (gmf) based on the development of the coras tool[END_REF] or ObeoDesigner 5 can be directly plugged on the Models@Runtime infrastructure to monitor the running system. The generated code is clean and provides an embedded visitor pattern and an observer pattern [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF]. EMF also provides an XMI marshaller and unmarshaller that can be used to easily share models. Finally EMF offers lazy loadings of resources allowing the loading of single model elements on demand and caching them softly in an application.

Limitations.

To highlights the limitations of EMF, we will use the following experiment based on a simple Finite State Machine (FSM) metamodel with four meta-classes (FSM, State, Transition and Action in Fig. 1). A FSM contains the States of the machine and references to initial, current and final states. Each State contains its outgoing Transitions, and Transitions can contain Actions. From this tiny example, we discuss thread safety and dependencies, and we evaluate the memory footprint, as well as model (un)marshaling and cloning. Large dependency set. Figure 2 shows the plugin/bundle dependencies for each new EMF generated code. By analyzing these dependencies one can see that the generated code is tightly coupled to the Eclipse environment and to the Equinox runtime (Equinox is the version of OSGi by the Eclipse foundation). Although this is not problematic when the data model is integrated as an Eclipse plugin (with all dependencies imposed by the Eclipse environment); these dependencies are more difficult to resolve and provision when this metamodel is used outside Eclipse, i.e. in a standalone context.

For the simple FSM metamodel, a standalone JAR executable outside of the Eclipse tool (a Java archive that including all dependencies) has a size of 15 MB for only 55 KB generated files. This footprint is rather difficult to reduce with tools like ProGuard6 , since it contains a large number of reflexive calls, which could potentially and implicitly affect any code in these 15 MB.

The large number and size of dependencies is one of the main limitations of EMF when the model must be embedded at runtime.

Static registries and multi-class loader incompatibility. Many runtime for dynamic architecture (e.g. OSGi, Frascati, or Kevoree) need to use their own class loader to properly manage and improve dynamic class loading. Consequently, the second limitation comes from the use of static registries in EMF, that leads to incompatibilities with runtime using multi-class loaders.

Lack of thread safe access to the models. EMF does not provide thread safe accesses to the models7 . This requirement is important for a Models@Runtime infrastructure, because the support for dynamic and distributed architectures requires concurrent access to models.

Cloning overhead. Another limitation is the large memory footprint of marshaling, unmarshaling and cloning in the EMF implementations. To measure this limitation, we programmatically created a model with 100,000 State instances, with a transition between each state and an action for each Transaction. The results for EMF are the following. On a Dell Precision E6400 with a 2.5 GHz iCore I7 and 16 GB of memory, the model creation lasts 376 ms, its marshaling to a file lasts 7021 ms and uses 104 MB of heap memory. The cloning using EcoreUtil lasts 3588 ms, and loading the model from a file lasts 5868 ms8 .

Synthesis.

Table 1 summarizes the advantages and limitations for the usage of EMF as a foundation for a Models@Runtime infrastructure. For each criterion, we put a ∨ when EMF provides advantages, × when we see limitations of using EMF for building Models@Runtime infrastructure, ∼ when we see possible improvements. Connecting design tools ∨ Table 1. EMF features compared with Models@Runtime requirements 4 Kevoree Modeling Framework KMF, or Kevoree Modeling Framework9 , is our alternative realization of EMF, which was formerly developed as part of our Kevoree Models@Runtime engine. This section presents the design choices we made to support a generic and efficient Models@Runtime infrastructure compatible with EMF. The general idea of KMF is threefold:

1. KMF aims at keeping the compatibility with EMF to guarantee the compatibility with design environment and the marshalling and unmarchalling of models.

2. KMF aims at leveraging the powerful features provided by modern programming languages (here, Scala) [START_REF] Odersky | Programming in Scala: A Comprehensive Step-by-step Guide[END_REF] to provide a proper design to handle models. 3. KMF aims at providing a generic Models@Runtime infrastructure to ease the heterogeneity and the distribution management.

Model handling

Regarding the Table 1, KMF provides the same features than EMF for code generation facilities and models (un)marshalling. All the generated artefacts are written in Scala. Scala is a general purpose programming language designed to express common programming patterns in a concise, elegant, and type-safe way. It smoothly integrates features of object-oriented (Traits) and functional languages, and provides bytecode compatibility with Java [START_REF] Odersky | Programming in Scala: A Comprehensive Step-by-step Guide[END_REF]. Scala uses type inference to combine static safety with the concise syntax of dynamically typed languages. The Scala features particularly relevant for KMF are the following: ByteCode compatibility with Java libraries, concept of traits, concept of Option, XML embedded, immutable List, concept of closure and efficiency. Domain classes are generated as a set of Scala traits to ease the support of multiple inheritance and meta-model extension [START_REF] Fouquet | Building a kermeta compiler using scala: an experience report[END_REF]. Traits are seen from Java Code as a Type. They can only be initialized through the generated Factory (as in EMF). Note that the generated Traits do not inherit from EMF EObject and that all references are initialized. In particular, collections are initialized and references to single objects with a lower bound of 0 rely on Options. These Scala options are a neater way to deal with null pointers 10 . Indeed, Option does not save the developer from ever having null, but that developer can only get null when he wants it. If it is semantically impossible for a value to be null, the type checker enforces it. The getters on collection use immutable lists. The generated code provides helpers to add and remove model elements on collections, and it also provides specific methods to ease mixed Java/Scala development. XML template are directly embedded in the Scala generated code and type checked by the Scala type checker. Fig. 3 shows an excerpt of the Scala traits generated for the domain model meta-classes. It shows the use of immutable list and Option for 0..n reference and 0..1 reference respectively.

Memory footprint

To limit the dependencies, we decided to restrict the inheritance relationships in our generated code only to generated classes and to classes from the Java and the Scala frameworks. In this way dependencies are limited to the Java and Scala frameworks. A standalone JAR for the same metamodel in KMF has a size of 7 MB. After applying ProGuard, we obtain a JAR of 1.7MB. Indeed, the Scala dependencies load many packages that are not used by KMF, such as Scala-Swing, Scala-actors, etc. loaders and serializers for the XMI file format. EMF compatibility is obtained through the XMI file format. A direct API compatibility can be performed when EMF will separate the Ecore interfaces and Ecore implementation in different bundles to avoid useless dependencies. Besides, the memory footprints used to store, load, save or clone a model has decreased compared to the reference EMF implementation. To measure the memory footprints, (un)marshalling and cloning, we do the same experiment. We programmatically create models with 100 000 States with a transition between each state and an action in each Transaction. The results for KMF are the following. On a Dell Precision E6400 with an Intel 2.5GHz iCore I7 CPU and 16GB of RAM, it takes 313ms to create the models, 2630 ms to save it in a file, 61 Mbytes of Heap memory, 398ms to clone and 3000s to load the model from a file 15 . Table 2 highlights the quantitative performance comparison results between EMF and KMF.

Experiment and synthesis

Table 3 3. EMF and KMF regarding models@runtime requirements

Refactoring impact

The first major consequence of removing the runtime dependencies with EMF is that all the methods defined in EObject are now unavailable. This could have a significant impact on the existing code that uses these methods. In order to limit the refactoring impact of this removal, we re-implemented the eContainer mechanism of EMF in our generated code.

Another important design choice we made for KMF was to use Scala as the default language for the generation and use of the code. Java has also been considered as a language since Scala code is fully compatible with Java. However, Scala code is not always friendly to use from a Java program 16 . To ease the use of KMF in a Java environment, we also provide a standard Java API, which in particular exposes Java lists, by duplicating some methods that are suffixed with "4J". That requires all model navigation-related code to be rewrote to use these new methods. The dual strategy could of course have been implemented: generating Java code and exposing in addition a Scala API.

The main rationale behind the choice of Scala was that the Scala standard library provides many facilities that are useful for Models(@runtime). In particular, the systematic introduction of Scala Option for each optional (i.e. having lower bounds equals to 0) attribute or reference implies to explicitly test if the element is defined or not, in a neater way than if (myRef == null) in Java, and in a safer way than a NullPointerException popping at runtime. Here again, this mechanism enforces developers to consider the optional aspect of these elements and avoids lots of null-checks, but requires a deep refactoring.

Limitations

KMF has formerly been developed and tested using the Kevoree metamodel originally designed with EMF tools. This first step allowed for setting up the basis for model, loader and serializer generation. The use of a fairly different metamodel (from Kermeta [START_REF] Muller | Weaving Executability into Object-Oriented Meta-languages[END_REF]) highlighted some missing features in the generation process, and strongly helped in improving KMF. However, KMF still has some limitations. For instance, reverse relations have already be flagged as missing in the generated code.

EMF allows model elements to have some relations with elements from other metamodels (references, attribute types, inheritance, etc). This mechanism has been partially realized on a concrete use case, but it still need improvements and implementation discussions.

Moreover, the generation of loaders and serializers relies on containment relations between model elements, and it requires a root container element. Until now, we considered metamodels that have only one single model element as root of the containment tree, but this is not the general case. Indeed, all model elements must have a container, but not necessarily under a single root for the metamodel. There could be several containment roots (and several containment trees) in a metamodel, with references to each other, but also across different metamodels. Generators of loaders and serializers are not ready to accept such kind of metamodels, but meeting this requirement is already considered as future work.

KMF addresses performances issues of models in memory (heap). Complementary approaches like CDO addresses the management of models in persistence memory (databases). The CDO (Connected Data Objects) Model Repository 17 is a distributed shared model framework for EMF models and metamodels. CDO has a 3-tier architecture supporting EMF-based client applications, featuring a central model repository server and leveraging different types of pluggable data storage back-ends like relational databases, object databases and file systems. The default client/server communication protocol is implemented with the Net4j Signalling Platform. This solution offers tools to easily do collaborative work and history management. However, it uses EMF as a local representation. Consequently it inherits a part of the drawbacks coming from EMF (e.g. dependencies for client side, memory footprints). Moreover the use of external server to manage history is not useful for pervasive systems that may have a sporadic network and even if it can embed server side on client, the overhead of the dependencies is not suitable for lightweight systems.

Conclusion

This position paper has discussed the needs for adapting the de facto standard in the MDE community, i.e. the Eclipse Modelling Framework (EMF), for a more dynamic usage of models in the context of Models@Runtime. After highlighting requirements related to Models@Runtime, this paper has presented an initial adaptation of EMF, named Kevoree Modelling Framework (KMF), implemented in Scala and generating code for this language. Even if KMF only supports XMI serialisation, it provides a significant speedup on model creation, model (un)marshalling and model cloning. It also has a lighter memory footprint than the reference implementation, and its runtime dependencies are limited to the Java and Scala libraries, whereas the EMF generated code has tight dependencies to Eclipse and Equinox. This significantly hinders the reusability of the EMF code outside Eclipse, while KMF code can run Eclipse-free on various Java virtual machines. Finally, and unlike EMF which is not thread-safe, KMF provides a built-in support for in-memory safe concurrent access to models.

Fig. 1 .

 1 Fig. 1. Finite State Machine Metamodel used for Experiments

Fig. 2 .

 2 Fig. 2. Dependencies for each new metamodel generated code

Table 2 .

 2 EMF and KMF efficiency

		EM F	KM F	comparison
	Model creation	376 ms	313 ms	1.2 times faster
	Model clone	3588 ms	398 ms	9 times faster
	Model save	7021 ms	2630 ms	2.66 times faster
	Memory footprint 104MB of heap memory 61MB of heap memory 1.70 times lighter

  provides the qualitative comparison results between EMF and KMF.

		EM F	KM F
	Memory footprints	×(104MB)	∨(61MB)
	Dependencies	×	∨ (Scala standard library)
		(15MB)	(1.7MB)
	Lazy Loading	∨	∨ (Proxy support)
	Thread safety	×	∨ (immutable lists, no registry)
	Efficient model (un)marshalling and cloning	∼	∨ (see Table 2)
	Design tools compatibility	∨	∨ (through XMI compatibility)
	Table

http://www.eclipse.org/emf/

http://www.obeodesigner.com/

ProGuard is a code shrinker (among other features not relevant for this paper) for Java bytecode: http://proguard.sourceforge.net/

http://wiki.eclipse.org/EMF/FAQ#Is EMF thread-safe.3F

This experiment can be downloaded http://goo.gl/CyLLC

https://github.com/dukeboard/kevoree-modeling-framework

http://www.dalvikvm.com/

http://oss.readytalk.com/avian/

http://jamvm.sourceforge.net/

http://www.oracle.com/technetwork/java/embedded/downloads/javase/index.html

This experiment can be download http://goo.gl/9Huwa (for eclipse project) or http://goo.gl/0sWRo (for the maven project)

To give an idea, a Scala list built by concatenating the empty list (Nil) and the element 1 would be written 1::nil in Scala. The construction of the same Scala list in Java would yield $colon$colon$.MODULE$.apply((Integer) 1, nil);

t r a i t T r a n s i t i o n extends FsmSampleContainer { private var i n p u t : j a v a . l a n g . S t r i n g = " "

private var o u t p u t : j a v a . l a n g . S t r i n g = " " Consequently, KMF has successfully been used on top of Dalvik 11 , Avian 12 , JamVM 13 or JavaSE for embedded Oracle Virtual Machine 14 .

Multi-thread access

Model@Runtime serves as a common software reflection layer concurrently exploited by many processes; protection against such accesses may be coarse or fine grain.

At fine grain the model essentially needs to be read concurrently while allowing modifications. The KMF generated code realizes such protection by internally using mutable collections (for performance reasons) but only exposing cloned immutable list to outside via its public API. As a result processes can navigate the cloned list while others perform CRUD operations on it. Each process needs to actively ask a new cloned version to access to the modifications. Moreover, the mutator methods (setter) can be protected behind synchronized blocks.

At coarse grain the model representation is entirely hidden behind a safe model care tracker as in the Memento pattern [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF]. This safe model care tracker systemically clones the model on get operations and keeps a master representation. This structure is particularly useful to keep an history of model representation at runtime. KMF can optionally generate such structure using Scala actors to protect concurrent access (get / put) to model care tracker.

Loader, Serializer and Cloner

When working with models, two tasks are essential and used before and after each action on a model, namely marshalling and unmarchalling. Where EMF offers a generic loader we propose to use the generation phase to also generate a specific loader for each meta-model. The EMF generic loader takes a model to load and its meta-model as parameters and intensively uses reflection mechanisms to perform the loading task. If this kind of mechanism allows creating a single loader, its usage is not efficient. The generated KMF code then provides meta-model specific loader, saver and cloner to improve their efficiency. We use the XML API which is part of the Scala standard library to parse and print XMI representations of object models, with no need for extra dependencies, and because it is efficient. The loading and cloning are performed in two phases. The first phase consists in traversing the models for creating the objects in the order they are found in the XMI file. The last step links the objects together according to the references previously cached. Currently, the Maven plugin we propose is only able to generate KMF is still at an early stage of existence and needs to be improved through usage. Future work on KMF already addresses the limitations and points discussed in section 5. Independently from the improvement of existing features of KMF, we think that additional tools could promote its adoption. Set operations. Model merging or model comparison are common operations implemented by tools that use models as representations of their internal data. Implementing mergers or comparators is often a complex, lengthy and error prone task. As a future work, we plan to offer the possibility to generate metamodel specific set operations such as union, difference or intersection. These operations could decrease the complexity of implementing model mergers. Customizable generation plugin. In its current implementation, the plugin allows for generation of all features (model, cloner, loader and serializer) or only model and cloner. This customization of the plugin behavior will be improved to enable the separate generation of each feature. Moreover, the loader and serializer generators are hard coded in the plugin. It is thus problematic to use other generators to create loaders and serializers that use another serialization format (namely XMI). In the future, we plan to improve the plugin parameterization to allow users to change the generators. This will also enable the seamless integration of other generators (e.g. to create set operations).