Lilianne Denis-Vidal
email: lilianne.denis-vidal@math.univ-lille1.fr

Ghislaine Joly-Blanchard
email: ghislaine.joly-blanchard@utc.fr

Céline Noiret
email: celine.noiret@utc.fr

Michel Petitot
email: michel.petitot@lifl.fr

Two approaches for testing identifiability and corresponding algorithms

Keywords: Nonlinear dynamical systems, Structural identifiability, Symbolic manipulation

This paper considers two different methods in the analysis of nonlinear controlled dynamical system identifiability. The corresponding identifiability definitions are not equivalent. Moreover one is based on the construction of an input-output ideal and the other on the similarity transformation theorem. Our aim is to develop algorithms which give identifiability results from both approaches. Differential algebra theory allows realization of such a project. In order to state these algorithms, new results of differential algebra must be proved. Then the implementation of these algorithms is done in a symbolic computation language.

Introduction

In this paper, two types of models are introduced in order to analyze nonlinear controlled dynamical system identifiability. Firstly, the initial conditions are ignored: Σ θ ẋ(t, θ) = f (x(t, θ), θ) + u(t)g(x(t, θ), θ), y(t, θ) = h(x(t, θ), θ).

Secondly, the initial conditions are known:

Σ θ x0(θ)
ẋ(t, θ) = f (x(t, θ), θ) + u(t)g(x(t, θ), θ), x(0, θ) = x 0 (θ), y(t, θ) = h(x(t, θ), θ).

In both cases, x(t, θ) ∈ IR n , y(t, θ) ∈ IR m , u(t) ∈ IR denote the state variables, the measured outputs and the input respectively. The parameter vector θ is in Ω q , an open subset of IR q . The single-input case is taken into account for notational simplicity; all the results can be generalized readily.

The functions f (x, θ), g(x, θ) and h(x, θ) are real and rational and may depend on a real constant vector denoted by a. In this case the set K corresponds to IR(a) (i.e. the field generated by IR and a), otherwise K corresponds to IR.

In the 90's Diop and Fliess [START_REF] Fliess | Nonlinear observability, identifiability, and persistent trajectories[END_REF], Fliess and Glad [START_REF] Fliess | Essays on control: perpectives in the theory and its application[END_REF], Ljung and Glad [START_REF] Ljung | On global identifiability for arbitrary model parametrizations[END_REF] and Ollivier [START_REF] Ollivier | Identifiabilité des systèmes[END_REF] proposed a new approach of identifiability, based on differential algebra. The initial conditions are ignored as they are in the model Σ θ . Thus, the solutions of model equations may be non-unique and some solutions might be of a degenerate character. Therefore, the concept of non-degenerate solutions x(θ, u) and ȳ(θ, u) has to be considered and the definition introduced in [START_REF] Ljung | On global identifiability for arbitrary model parametrizations[END_REF]] is adopted here: Definition 0.1 The model Σ θ is globally identifiable at θ ∈ Ω q if for any θ ∈ Ω q , θ = θ, there exists a control u such that ȳ(θ, u) = ∅ and ȳ(θ, u) ∩ ȳ( θ, u) = ∅. It is locally identifiable at θ ∈ Ω q if there exists an open neighborhood W of θ such that Σ θ is globally identifiable at θ with Ω q restricted to W . Now, let us introduce some useful notations.

• A differential ring (respectively field) is a ring (respectively field) endowed with a set of derivations which commute pairwise.

• Let V be a set of differential indeterminates and ∆ be a set of derivations which commute pairwise. We denote by Θ the commutative monoid generated by ∆ and by ΘV the set of all the derivatives φv, φ ∈ Θ, v ∈ V . Given a field K, K{V } is the differential ring of the differential polynomials built over the alphabet ΘV with coefficients in K.

• The differential field generated by K and Ṽ is denoted by K < Ṽ >, Ṽ ⊂ V and, by definition, it is equal to K(Θ Ṽ ) (i.e. the smallest field which contains K and Θ Ṽ ).

Since the functions f, g and h are rational functions, the identifiability techniques based on differential algebra are well appropriate. Indeed, the controlled system is considered as a set of variables (indeterminates) {u, x, y, θ} linked by a differential ideal. Ljung and Glad [START_REF] Ljung | On global identifiability for arbitrary model parametrizations[END_REF] and Ollivier [START_REF] Ollivier | Identifiabilité des systèmes[END_REF] exploited the concept of characteristic set. The characteristic set of the differential ideal, defined by dynamical system equations, is a finite set of polynomials which summarizes the whole information contained in the differential ideal. Ljung and Glad perform a characteristic set which leads to the expression of each parameter as a rational function of u, y and their derivatives. Thus, they have shown the following results:

• A system is locally identifiable if and only if any parameter θ i is differentially algebraic over K< u, y>. It is the definition of the algebraic identifiability of Diop and Fliess [START_REF] Fliess | Nonlinear observability, identifiability, and persistent trajectories[END_REF], which is strongly connected to the nonlinear observability.

• A system is globally identifiable if any parameter θ i belongs to the field K< u, y>. It is the definition of the rational identifiability of Diop and Fliess [START_REF] Fliess | Nonlinear observability, identifiability, and persistent trajectories[END_REF].

Ljung and Glad's approach often leads to cumbersome computation.

Ollivier derives the identifiability from the computation of the characteristic set corresponding to the input-output ideal of differential algebraic relations between u, y and θ. The identifiability is obtained after analyzing this characteristic set.

In the first proposed method of this paper, the notion of characteristic presentation is considered instead of characteristic set because it supplies an effective way for testing the equality of some ideals. The resulting algorithm is implemented in Maple, a symbolic computation language, and uses the package Diffalg especially.

On the other hand, it is noticeable that Definition 0.1 is well in line with the usual analytic definition of global (local) identifiability valid only for the system Σ θ x0(θ) (i.e. the initial conditions are known after selecting θ ∈ Ω q ): Definition 0.2 The model Σ θ x0(θ) is globally identifiable at θ ∈ Ω q if for any θ ∈ Ω q , θ = θ there exists a control u, such that Σ θ x0(θ) and Σ θ x0( θ) yield different outputs. It is locally identifiable at θ ∈ Ω q if there exists an open neighborhood W of θ such that Σ θ x0(θ) is globally identifiable at θ with Ω q restricted to W . In most models there exist atypical points in Ω q where the model is unidentifiable. Definitions 0.1 and 0.2 should be generically extended so that Σ θ x0(θ) (or Σ θ ) is said to be globally structurally identifiable if it is globally identifiable at all θ ∈ Ω q except at the points of a subset of zero measure in Ω q . Now, we introduce a second identifiability approach which is a nonlinear counterpart of the similarity transformation approach [START_REF] Walter | Identifiability of state space models[END_REF] and is based on the local state isomorphism theorem [START_REF] Fliess | Local Realization of Linear and Nonlinear Time Varying Systems[END_REF], [START_REF] Tunali | New results for identifiability of nonlinear systems[END_REF]. It leads to the solution of a system of partial differential equations (PDE). This is an efficient method for controlled models.

In theory, one has to solve this partial differential system but an alternative is proposed here. Indeed the originality of our process is to solve the identifiability problem without solving (in the analytic sense) this partial differential system. To do that, a link between the integrability constraints of the partial differential system and the identifiability properties of the original system is established. It leads to an algorithm which is implemented in Maple VII.

The paper is organized as follows. First, Section 1 mentions some results necessary for the development of the first identifiability algorithm. Then Section 2 shows a necessary and sufficient identifiability condition which justifies the second algorithm. Lastly, two examples compare the performances of both algorithms.

1 Input-output ideal approach 1.1 Description

The system Σ θ can be rewritten as a differential polynomial system that will be completed with θi = 0, i = 1, . . . , q. The resulting system Γ can be described by the following polynomial equations and inequations:

Γ        p( ẋ, x, u, θ) = 0, q(x, y, θ) = 0, r(x, y, θ) = 0, θi = 0, i = 1, . . . , q.
(3) Thus, the functions x j , j = 1 . . . n are to be differentially algebraic over K < u, θ >, and so are the functions y i , i = 1 . . . m. The input u is assumed to be differentially transcendent. In this context, a solution of Γ is a quadruplet of functions (x, y, u, θ) satisfying all the model equations.

I is the radical of the differential ideal generated by the polynomials of Γ. From the ranking

[θ] ≺ [y, u] ≺ [x] (4)
that eliminates state variables and from the equations of Γ, characteristic presentations corresponding to I are computed.

The proofs of the two following propositions, given in [START_REF] Noiret | Utilisation du calcul formel pour l'identifiabilité de modèles paramétriques et nouveaux algorithmes en estimation de paramètres[END_REF] are very technical and not constructive relatively to algorithm elaboration. Proposition 1.1 If I,endowed with the ranking (4), admits a characteristic presentation, this presentation has the following form: θ1 , . . . , θq , P 1 (y, u, θ), . . . , P m (y, u, θ), Q 1 (y, u, θ, x), . . . , Q n (y, u, θ, x),

where the leader of the polynomial P k is y k for k = 1, . . . , m , and where the leader of the polynomial Q j is x j for j = 1, . . . , n.

In general, I should be written as the intersection of regular differential ideals, each one admitting a characteristic presentation. However in the following, I, endowed with the ranking (4), is assumed to be a regular ideal presented by a characteristic presentation C. This assumption is not so restrictive. Indeed in the opposite case, the next proposition must be applied to each system corresponding to each component of the decomposition of the ideal. Now let us introduce a few notations:

• L is the set of the leaders of the elements of C, N denotes the other derivatives occurring in C and K[N ] is the polynomial ring built over N with coefficients in K.

• C(θ) is the characteristic presentation C evaluated in the particular value of parameter θ.

• I θ is the radical of the differential ideal generated by Γ for the particular value of parameter θ and C θ is the characteristic presentation associated with the ranking

[y, u] ≺ [x].
To avoid the evaluation of C(θ) at each value of parameters, the following result gives a sufficient condition for the equality C θ = C(θ). Proposition 1.2 Let C = {c 1 , . . . , c m+n , θ1 , . . . , θq } be the characteristic presentation of the differential ideal I endowed with the ranking (4).

If, for every θ ∈ Ω q and for every i = 1, . . . , m + n, the initial of c i (θ) ∈ C(θ) is not equal to zero and none of its factors ( = 1) is a divisor of all the other coefficients of

c i (θ) ∈ K[N ], then C θ = C(θ) for all θ ∈ Ω q .
Now let us introduce I io θ , the ideal obtained after eliminating state variables. Thus the set C io θ = C θ ∩ K(θ){u, y} is a characteristic presentation of the ideal I io θ , called the input-output characteristic presentation. As a consequence of Proposition 1.1, I io θ contains the polynomials P i , i = 1 . . . m. The next proposition is valid under the assumption that there exists some generic solution of Σ θ . A solution is called generic if it does not verify any equation out of the ideal's equations [START_REF] Ollivier | Identifiabilité des systèmes[END_REF] (as a consequence it is also a non-degenerate solution). The genericity assumption is difficult to test but strong accessibility from every initial condition in a dense open subset of IR n implies this property. Moreover, strong accessibility is obtained by the strong accessibility rank criterion (SARC) [START_REF] Van Der Schaft | Nonlinear Dynamical Control Systems[END_REF] at every initial condition of this dense open subset. Proposition 1.3 Let us assume that there exists some generic solution of Σ θ . Then Σ θ is globally identifiable at θ, in the sense of Definition 0.1, if and only if for every θ ∈ Ω q ( θ = θ), the two corresponding input-output characteristic presentations (C io θ and C io θ ) are distinct.

Remark 1.1 The previous proposition can be formulated in the equivalent form: if there exists a generic solution of Σ θ , then Σ θ is globally identifiable at θ, if and only if

∀ θ ∈ Ω q C io θ = C io θ ⇒ θ = θ.
The proof of the previous proposition is like the proof of Theorem 6 in Ollivier [START_REF] Ollivier | Identifiabilité des systèmes[END_REF]. The only difference concerns the characteristic set or presentation.

Algorithm

The polynomials P i , i = 1 . . . m, of C io θ can be seen as polynomials in y and their derivatives with coefficients in K(θ). In the following, those polynomials will be written as

P i (y, u) = m 0 (y, u) + ni k=1 p i k (θ)m i k (y, u).
Now let us present the algorithm that we have implemented in Maple VII. It will be referred to it as Algo1. Let us remark Steps 4 and 7 of Algo1 are based on Rosenfeld-Groebner algorithm which has been realized by F. Boulier in Maple VII [START_REF] Boulier | Computing representations for the radicals of a finitely generated differential ideals[END_REF].. Data: f, g and h.

Step 1 The software rewrites the original system Σ θ as the differential polynomial system Γ defined by (3).

Step 2 The existence of a generic solution is validated by checking the SARC.

Step 3 The field of constants K is given and a standard ranking is implicitly introduced. It is possible to select a most suitable ranking by a careful analysis of the system.

Step 4 Rosenfeld-Grobner algorithm computes all the input-output characteristic presentations (it is possible to compute only the general input-output characteristic presentation). Then an inputoutput characteristic presentation is chosen by the user.

Step 5 The values of θ for which the polynomials P i are not primitive over K[N ] (i.e the assumptions of proposition 1.2 are not satisfied) are computed.

Step 6 This step saves the coefficients p i k (θ) in a list called the "exhaustive summary". It is simplified in order to extract its smallest generator system in terms of degree, number of monomials,...

Step 7

The exhaustive summary is analyzed by Rosenfeld-Grobner algorithm; the following system:

p i k (θ) = p i k ( θ), k = 1, . . . n i , i = 1 . . . , m θi = 0, i = 1, . . . , q (6)
is solved in the differential field K(θ)< θ> with the standard ranking (or a most suitable ranking given by the user):

[ θ1 ] ≺ [ θ2 ] ≺ [. . .] ≺ [ θq ] (7)
In order to simplify the computation, the pure transcendental field extension K(θ) is considered as a field of coefficients; it leads to a structural identifiability. At the end of this step results of identifiability are provided.

Finally, note that if Algo1 does not successfully terminate because the computation of the inputoutput characteristic presentation is too complex or the analysis of the exhaustive summary fails, it can be reapplied by using a different ranking in steps 4 or (and) 7. Algo1 has been implemented in MAPLE VII and runs on any Pentium PC.

Similarity transformation approach

In this section, the following assumptions are assumed: The functions f (., θ) and h(., θ) are real, rational and analytic for every θ ∈ U p on M (a connected open subset of IR n such that x(t, θ) ∈ M for every θ ∈ U p and every t ∈ [0, T ]); f (x 0 (θ), θ) = 0 for every θ ∈ U p ; the input vector u is in U[0, T ], the set of bounded and measurable functions defined on the time interval [0, T ]; the initial state x 0 (θ) is well defined after selecting θ. Finally, the system Σ θ x0(θ) is assumed to be locally reduced at x 0 (θ) for all θ ∈ Ω q .

Description

The parameter identifiability can be obtained by using the local state isomorphism theorem which leads to the following result [START_REF] Vajda | Similarity transformation approach to structural identifiability of nonlinear models[END_REF]:

Theorem 2.1 The model Σ θ x0(θ) is assumed to be locally reduced at x 0 (θ) for all θ ∈ Ω q . Consider the parameter values θ and θ in Ω q , an open neighborhood V of x 0 (θ) in M and any analytical mapping

λ : V → IR n defined in V ⊂ IR n such that (i) Rank ∂λ ∂x (x) = n, ∀x ∈ V (ii) λ(x 0 (θ)) = x 0 ( θ) (iii) (PDE)                  (1) f (λ(x), θ) = ∂λ ∂x (x) f (x, θ) (2) g(λ(x), θ) = ∂λ ∂x (x) g(x, θ) (3) h(λ(x), θ) = h(x, θ)
for all x ∈ V .

Then there exists t 1 , 0 < t 1 < T , such that Σ θ x0(θ) is globally identifiable at θ, in the sense of Definition 0.2 and with u ∈ U[0, t 1 ] , if and only if (i),(ii),(iii) ⇒ θ = θ.

Vajda et al. [START_REF] Vajda | Similarity transformation approach to structural identifiability of nonlinear models[END_REF] treated some examples but did not give a systematic procedure to apply this theorem, which is stated in analytic terms. A new algorithm for analyzing identifiability, based on this theorem and the differential algebra theory, is presented here.

On the other hand, this approach is not valid for uncontrolled nonlinear dynamical systems as it has been proved in [START_REF] Joly-Blanchard | Some remarks about an identifiability result of nonlinear systems[END_REF]. In this case, an efficient approach [START_REF] Denis-Vidal | An easy to check (un)identifiability criterion for uncontrolled systems and its applications[END_REF] gives identifiability results of some particular systems.

Symbolic computation procedure

Considering the derivation ∂ ∂x the system (PDE) can be rewritten as a differential polynomial system that will be completed with ∂ θi ∂x j = 0, i = 1, . . . , q, j = 1, . . . , n.

The resulting system can be described by the following polynomial equations and inequations:

(pde)

                       p(x, x, ∂ x ∂x1 , . . . , ∂ x ∂xn , θ, θ) = 0 q(x, x, θ, θ) = 0, r(x, x, ∂ x ∂x1 , . . . , ∂ x ∂xn , θ, θ) = 0 ∂ θi ∂x j = 0, i = 1, . . . , q, j = 1, . . . , n. (9)
In this sub-section, I will denote the radical of the ideal, generated by the equations of the system [START_REF] Hermann | Nonlinear controllability and observability[END_REF]. It can be considered in the differential ring K(θ){x, x, θ}. Once again, the pure transcendental field extension K(θ) is considered as a field of coefficients, which leads to a structural identifiability.

From the ranking [ θ] ≺ [x], a characteristic presentation of I is computed. Rosenfeld-Groebner algorithm cannot solve, in the analytic sense, system (PDE) stated in theorem (2.1). It computes integrability constraints by giving all the classes of solutions of the system. The relations between integrability constraints and parameter (un)identifiability are given in the propositions below.

Proposition 2.1 If the radical of I, endowed with the ranking [ θ] ≺ [x], admits a characteristic presentation, this characteristic presentation has the following form: P 1,1 ( θ1 ), . . . , P 1,q1 ( θ1 ), P 2,1 ( θ1 , θ2 ), . . . , P 2,q2 ( θ1 , θ2 ), . . . , P q,1 ( θ1 , . . . , θq ), P q,2 ( θ1 , . . . , θq ), . . . , P q,qq ( θ1 , . . . , θq ),

Q 1,1 ( θ, x1 ), . . . , Q 1,n1 ( θ, x1 ), Q 2,1 ( θ, x1 , x2 ) . . . , Q 2,n2 ( θ, x1 , x2 ), . . . , Q n,1 ( θ, x) . . . , Q n,nn ( θ, x), ( 10
)
where q j ≤ n for j = 1, . . . , q, n k ≤ n for k = 1, . . . , n, the leader of the polynomial P i,j is a derivative of θi and the leader of the polynomial Q k,l is a derivative of xk .

Proof -In the characteristic presentation C, the polynomials ∂ θi ∂x j (1 ≤ i ≤ q, 1 ≤ j ≤ n) or lower ranked polynomials are found. Such polynomials admit ∂ θi ∂x j or θi as leader. As C is a differentially triangular set, the leaders of C are different and its elements are reduced pairewise. As a consequence, in the characteristic presentation C, there exists a maximum number of n polynomials whose leading variable is θi for all i = 1, . . . , q.

In the same way, the existence of Q j,nj for j = 1, . . . , n can be shown. 2

Admittedly it is impossible to know a priori the number of polynomials of the characteristic presentation.

Proposition 2.2 The system Σ θ x0(θ) is assumed to be locally reduced at x 0 (θ) for all θ ∈ Ω q . The model is globally structurally identifiable in the sense of Definition 0.2 if I endowed with the ranking [ θ] ≺ [x], admits a unique characteristic presentation which, moreover, has the following form

x1 -x 1 , . . . , xn -x n , θ1 -θ 1 , . . . , θq -θ q . ( 11
)
Proof -The assumption about the local reduction of Σ θ x0(θ) and the solution of the system (PDE) allow the application of Theorem 2.1. 2 Theorem 2.1 considers the analytic definition of identifiability, given in Definition 0.2. Thus, when the identifiability is not obtained directly (i.e. by ignoring initial conditions), a last calculation remains to be done: the evaluation of the equations of the characteristic presentation in x 0 ( θ). It selects the characteristic presentation valid for the particular initial conditions x 0 (θ) and it examines if those initial conditions imply the unicity of the characteristic presentation.

Proposition 2. [START_REF] Boulier | Computing canonical representatives of regular differential ideals[END_REF] The system Σ θ x0(θ) is assumed to be locally reduced at x 0 (θ) for all θ ∈ Ω q . The model is globally structurally identifiable in the sense of the definition 0.2 if and only if I endowed with the ranking [ θ] ≺ [x], admits a unique characteristic presentation C such that C = 0, complete with λ(x 0 (θ)) = x 0 ( θ), implies {x = x, θ = θ}.

Proof -Rosenfeld-Groebner algorithm returns k characteristic presentations C 1 , . . . , C k of regular differential ideals I 1 , . . . , I k . These ideals correspond to different solution classes of the system [START_REF] Hermann | Nonlinear controllability and observability[END_REF]. Now, since the model is globally identifiable, system (9) complete with λ(x 0 (θ)) = x 0 ( θ) (θ ∈ Ω q , θ ∈ Ω q ) has a unique solution {x = x, θ = θ}. Therefore, one and only one characteristic presentation C among {C 1 , . . . , C k } is compatible with λ(x 0 (θ)) = x 0 ( θ) (θ ∈ Ω q , θ ∈ Ω q ). Thus, the system C = 0 complete with λ(x 0 (θ)) = x 0 ( θ) will give the same solution as system (PDE) complete with λ(x 0 (θ)) = x 0 ( θ), i.e. {x = x, θ = θ}. The reciprocal is obvious. 2

Algorithm

The ensuing algorithm (denoted by Algo2) requires only the data of the functions f , g, h and x 0 (θ). It is implemented in Maple VII. It is decomposed in three steps.

Step 1 This step tests the local reduction of the model Σ θ x0(θ) at x 0 (θ) for all θ ∈ Ω q by using the observability rank criterion (ORC) and the controllability rank criterion (CRC) [16][9].

Step 2 This step corresponds to the differential algebraic treatment of system (PDE).

Firstly, it rewrites the system (PDE) as the system [START_REF] Hermann | Nonlinear controllability and observability[END_REF]. Secondly, the field of constants K(θ) and the ranking: [ θ] ≺ [x] are implicitly introduced. Thirdly, integrability constraints are computed: Rosenfeld-Grobner algorithm computes the inputoutput characteristic presentations. If the software returns a unique characteristic presentation which, has the following form: {x -x, θ -θ}, then the model is structurally globally identifiable and the algorithm stops. Else the step 3 is considered.

Step 3 The equations of each characteristic presentation are evaluated in x 0 ( θ) . It selects characteristic presentations valid for the particular initial conditions x 0 (θ) and it examines if those initial conditions imply θ = θ . Consequently identifiability results are given.

Examples

In this section, two examples are presented in order to illustrate both algorithms described above. The first one is academic and shows the importance of initial conditions in some controlled systems. The second one is a pharmacokinetic model for which identifiability does not require the knowledge of initial conditions. In this case, the first algorithm gives an exhaustive description of all the possible cases.

An academic example

The following academic example was treated without control in [START_REF] Denis-Vidal | An easy to check (un)identifiability criterion for uncontrolled systems and its applications[END_REF]:

   ẋ1 = θ 1 x 2 1 + θ 2 x 1 x 2 + u ẋ2 = θ 3 x 2 1 + θ 4 x 1 x 2 y = x 1 (12)
Here are the different steps of Algo1:

• Step 1: The software rewrites the system as :

       ẋ1 = θ 1 x 2 1 + θ 2 x 1 x 2 + u ẋ2 = θ 3 x 2 1 + θ 4 x 1 x 2 y = x 1 θ = 0 (13) • Step 2: The SARC is satisfied if θ 3 θ 4 = 0 • Step 3:
The field of constants IR is chosen and the standard ranking is implicitly introduced.

• Step 4: Algo1 returns three cases:

i) The general case Ω q = {(θ 1 , θ 2 , θ 3 , θ 4 ) ∈ IR 4 , θ 1 θ 2 θ 4 = 0} is given by the input-output characteristic presentation:

y ÿ -y u + y 2 θ 1 ẏ + y 4 θ 2 θ 3 -u ẏ -uy 2 θ 4 + ÿy 2 -y 4 θ 1 θ 4 , θ1 , θ2 , θ3 , θ4 . (14)
ii) θ 2 = 0 is a particular case (Ω q = {(θ 1 , θ 2 , θ 3 , θ 4 ) ∈ IR 4 , θ 2 = 0, θ 1 θ 4 = 0}) corresponding to the input-output characteristic presentation:

{-u + ẏ -y 2 θ 1 , θ1 , θ3 , θ4 , θ 2 }. (15)
iii) y = 0 .

The general characteristic presentation i) is chosen.

• Step 5: the hypothesis of Proposition 1.2 is checked to be valid for all θ ∈ Ω q .

• Step 6: The exhaustive summary given by the software is ( θ 1 , θ 4 , θ 1 θ 4 -θ 2 θ 3 ).

• Step 7: The analysis of this exhaustive summary leads to

θ1 -θ 1 , θ2 θ3 -θ 2 θ 3 , θ3 , θ4 -θ 4 . (16)
which proves that the model is not globally identifiable at θ ∈ Ω q .

Now the particular characteristic presentation ii) is chosen.

• Step 5: the hypothesis of Proposition 1.2 is checked to be valid for all θ ∈ Ω q .

• Step 6-7: The exhaustive summary is: (θ 1 ) and its analysis leads to θ1 -θ 1 , θ4 , θ3 , θ4 .

The model is not globally identifiable at θ ∈ Ω q .

Finally the characteristic presentation iii) corresponds to a non generic solution

Algo2 is applied to the same example with the initial conditions x 1 (0) = x 2 (0) = 0.

• Step 1: the model is locally reduced at (0, 0) for every θ ∈ {θ ∈ IR 4 , θ 2 θ 3 = 0}.

• Step 2: It sets up the (PDE) system in the following form: [START_REF] Van Der Schaft | Nonlinear Dynamical Control Systems[END_REF] where x = λ(x) and λ i j = ∂λ i ∂x j .

           θ1 x1 2 + θ2 x1 x2 = λ 1 1 (θ 1 x 2 1 + θ 2 x 1 x 2 ) + λ 1 2 (θ 3 x 2 1 + θ 4 x 1 x 2 ) θ3 x1 2 + θ4 x1 x2 = λ 2 1 (θ 1 x 2 1 + θ 2 x 1 x 2 ) + λ 2 2 (θ 3 x 2 1 + θ 4 x 1 x 2 ) 1 = λ 1 1 0 = λ 2 1 x1 = x 1
• Step 3: It returns only one characteristic presentation:

C = x1 -x 1 , θ 3 x2 -x 2 θ3 , ∂ θ3 ∂x 1 , ∂ θ3 ∂x 2 , θ 1 -θ1 , θ 2 θ 3 -θ2 θ3 , θ 4 -θ4 . ( 19
)

Conclusion

In this paper, we have shown how to analyze algorithmically the identifiability of nonlinear controlled dynamical models from two different approaches. The input-output approach does not make use of initial conditions but can be applied also to systems given in implicit form or to uncontrolled models. The concept of characteristic presentations of the input-output ideal permits the elaboration of an algorithm such that all the steps are computed by software.Moreover, the computation of characteristic presentations point out particular cases whose exhaustive analysis is done by the algorithm.

The similarity transformation approach considers initial conditions which are well defined after selecting parameter values. It requires the local reduction at initial conditions; it is tested easily by the first step of the algorithm. This approach leads to the solution of a PDE system. Some results concerning the characteristic presentation of the ideal, generated by this PDE system, permit the elaboration of the steps concerning identifiability analysis. However, it is not possible to obtain identifiability properties for the parameter values corresponding to loss of reduction.

In conclusion, both of them have been applied successfully to different models. But, although tested efficiently on some significant models, there is still much room for algorithmic improvements.

The characteristic presentation is not enough to decide on the identifiability. The initial conditions have to be taken into account. Thus, according to Proposition 2.3, the equality λ(0, 0) = (0, 0) is added to C = 0. No extra information is deduced; consequently the model is not structurally globally identifiable.

Then Algo2 is applied to the same example with the initial conditions x 1 (0) = 0, x 2 (0) = 1.

• Step 1: the model is locally reduced at (0, 1) for every θ ∈ {θ ∈ IR 4 , θ 2 θ 4 = 0}.

• Step 2: It is unchanged.

• Step 3: Equations C = 0 complete with λ(0, 1) = (0, 1), lead to

Therefore the model is structurally globally identifiable.

In this case, the structural global identifiability of the model is due to the initial conditions. This is a particular interest of Algo2: it takes the initial conditions into account easily while Algo1 does not do it. Moreover it is possible to complete Algo1 if initial conditions are known by evaluating the equations of the characteristic presentation at t = 0 and examining if they imply the unicity of parameters. It is the method chosen in [START_REF] Audoly | Global Identifiability of Non Linear Models of Biological Systems[END_REF] with characteristic presentation replaced by characteristic set. In the case x 0 = (0, 1) the evaluation of the characteristic presentation, given by Algo1 in x 0 , does not give any answers. Therefore Algo2 is more efficient for this particular case.

A real pharmacokinetic model

Now a real pharmacokinetic model [START_REF] Demignot | Effect of prosthetic sugar groups on the pharmacokinetics of glucoseoxidase[END_REF] is considered. It was solved by pen and paper in [START_REF] Joly-Blanchard | Some remarks about identifiability of uncontrolled nonlinear systems[END_REF]:

The unknown vector parameter is

Here are the different steps of Algo1:

• Step 1: The software rewrites the system as the following polynomial differential system:

The SARC is satisfied if α 2 = 0.

• Step 3: The field of constants IR is chosen and the standard ranking is implicitly introduced.

• Step 4: Algo1 returns two cases:

i) The general case Ω q = {θ ∈ IR 4 , α 1 = 0} is given by the input-output characteristic presentation:

ii) α 1 = 0 is a particular case (Ω q = {θ ∈ IR 4 , α 1 = 0}) presented by the input-output characteristic presentation:

The general characteristic presentation is chosen.

• Step 5: The hypothesis of Proposition 1.2 is not valid if V m k c = 0. Indeed, the set L is reduced to L = {ÿ} and the input-output characteristic presentation can be rewritten as

where (y + k c ) 2 and T belong to IR [N ]. If V m = 0, (y + k c ) 2 is a divisor of T and if k c =0, y 2 is a divisor of T . Consequently, the set Ω q becomes Ω q = {θ ∈ IR 4 , α 1 = 0, V m k c = 0}.

• Step 6: The exhaustive summary, given by the software, is :

• Step 7: The analysis of this exhaustive summary leads to :

which proves that the model is structurally globally identifiable.

Now the particular characteristic presentation ii) is chosen.

• Step 6-7: The exhaustive summary is: (V m , k c , -k c ) and its analysis leads to

The model is not globally identifiable at θ ∈ Ω q .

Algo2 is applied to the same example with initial conditions x 1 (0) = 0, x 2 (0) = 0.

• Step 1: The algorithm shows that the model is not locally reduced at (0, 0) if α 1 α 2 = 0.

• Step 2: After writing the (PDE) system, the algorithm gives a unique characteristic presentation containing:

Therefore the model is structurally globally identifiable. The algoritm stops: step 3 is useless.

The cases V m = 0 and k c = 0 do not appear explicitly since the pure transcendental field extension K(θ) is considered as the field of coefficients in all the algorithm.

Therefore, results of Algo2 agree with results of Algo1 but the analysis is less exhaustive.

Comparison of algorithms

Algo1 is well adapted for an exhaustive analysis of the global identifiability of a model independently on initial conditions. On the other hand, as shown in the case of the academic example, Algo2 is efficient if initial conditions are a significant part of the model. It is possible to compare algorithm efficiency relatively to the computation time on a pentium 4 with 2.2 MHz.

• example (12) -1s (Algo1), 1.2s (Algo2),

• example (20) -1.1s (Algo1), 1.3s (Algo2) Then Algo1 is slightly faster than Algo2. Moreover some examples, not given here, show that Algo2 may fail more easily when the dimension of the model is too large. The authors put the software at the disposal of anyone concerned by this kind of problem.


Lilianne Denis-Vidal
email: lilianne.denis-vidal@math.univ-lille1.fr

Ghislaine Joly-Blanchard
email: ghislaine.joly-blanchard@utc.fr

Céline Noiret
email: celine.noiret@u-paris10.fr

An efficient algorithm for testing nonlinear dynamical model identifiability

This paper is concerned by the analysis of nonlinear controlled or uncontrolled dynamical model identifiability. The proposed approach is based on the construction of an input-output ideal. The aim is to develop an algorithm which gives identifiability results from this approach. Differential algebra theory allows realization of such a project. In order to state the algorithm, new results of differential algebra must be proved. Then the implementation is done in a symbolic computing language.

Introduction

In this paper, the following model is introduced in order to analyze nonlinear controlled or uncontrolled dynamical model identifiability. The initial conditions are ignored: Σ θ ẋ(t, θ) = f (x(t, θ), θ) + u(t)g(x(t, θ), θ), y(t, θ) = h(x(t, θ), θ).

In this model, x(t, θ) ∈ IR n , y(t, θ) ∈ IR m , u(t) ∈ IR denote the state variables, the measured outputs, and the input respectively. The parameter vector θ is in Ω q , a subset of IR q (or C q ). The single-input case is taken into account for notational simplicity; all the results can be generalized readily. What follows is developed in the case of controlled models and can be applied easily if models are uncontrolled (u = 0). The functions f (x, θ), g(x, θ) and h(x, θ) are rational and may depend on a known constant vector denoted by a.

In the 90's Diop and Fliess [START_REF] Fliess | Nonlinear observability, identifiability, and persistent trajectories[END_REF], Fliess and Glad [START_REF] Fliess | Essays on control: perpectives in the theory and its application[END_REF], Ljung and Glad [START_REF] Ljung | On global identifiability for arbitrary model parametrizations[END_REF] and Ollivier [START_REF] Ollivier | Identifiabilité des systèmes[END_REF] proposed a new approach for identifiability, based on differential algebra. Following this idea, we have elaborated an algorithm for analyzing identifiability, which requires some knowledge of differential algebra theory.

Now, let us introduce some useful notations (see also Appendix B).

• A differential ring (respectively field) is a ring (respectively field) endowed with a set of derivations which commute pairwise.

• Let V be a set of differential indeterminates and ∆ be a set of derivations which commute pairwise. We denote by Θ the commutative monoid generated by ∆ and by ΘV the set of all the derivatives φv, φ ∈ Θ, v ∈ V . Given a differential field K, K{V } is the differential ring of the differential polynomials built over the alphabet ΘV with coefficients in K.

• The differential field generated by K and Ṽ is denoted by K < Ṽ >, Ṽ ⊂ V and, by definition, it is equal to K(Θ Ṽ ) (i.e. the smallest field which contains K and Θ Ṽ ).

Here, the field of constants is IR(a) (i.e. the field generated by IR and a) if the functions f (x, θ), g(x, θ) and h(x, θ) depend on a, otherwise it is IR. Then the differential field K is defined as the field of constants equipped with the derivation d dt .

Indeed, the model Σ θ is considered as a set of variables {u, x, y, θ} linked by a differential ideal. More precisely it can be rewritten as a differential polynomial model completed with θi = 0, i = 1, . . . , q. The resulting system Γ can be described by the following polynomial equations and inequations.

Γ

      
p( ẋ, x, u, θ) = 0, q(x, y, θ) = 0, θi = 0, i = 1, . . . , q r(x, y, θ) = 0.

(2)

Thus, the functions x j , j = 1 . . . n are differentially algebraic over K < u, θ >, and so are the functions y i , i = 1 . . . m. The input u is assumed differentially transcendent. In this context, a solution of Γ is a quadruplet of functions (x, y, u, θ) satisfying the system.

These models are very general. Thus, the solutions of the system may be non-unique and some solutions might be of a degenerate character. Therefore, the concept of non-degenerate solutions [START_REF] Ljung | On global identifiability for arbitrary model parametrizations[END_REF] have to be considered. In the following the definitions introduced in [7] are adopted: This definition is strongly connected to the nonlinear observability.

Definition 0.

Definition 0.2

A model is rationally identifiable if and only if any parameter θ i belongs to the field K< u, y>.

Ljung and Glad [START_REF] Ljung | On global identifiability for arbitrary model parametrizations[END_REF] and Ollivier [START_REF] Ollivier | Identifiabilité des systèmes[END_REF] exploited the concept of characteristic set. The characteristic set of the differential ideal, defined by dynamical model equations, is a finite set of polynomials which summarises the whole information contained in the differential ideal (see Appendix C). Ljung and Glad perform a characteristic set which leads to the expression of each parameter as a rational function of u, y and their derivatives. Ljung and Glad's approach often leads to cumbersome computation.

Ollivier derives the identifiability from the computation of the characteristic set corresponding to the input-output ideal of differential algebraic relations between u, y and θ. The identifiability is obtained by analyzing the characteristic set. This last analysis is done by Audoly et al ( [START_REF] Audoly | Global Identifiability of Non Linear Models of Biological Systems[END_REF]) by using Groebner basis calculation. They have chosen numerical random points rather than symbolic points to enlarge the class of models testable by their algorithm.

In the proposed method of this paper, the notion of characteristic presentation is considered instead of characteristic set because it supplies an effective way for testing the equality of some ideals (see Appendix C for more details) The identifiability is obtained after analyzing the characteristic presentation using symbolic points rather than numerical random points and the suggested method allows the analysis of a class of models that is as large as in [START_REF] Audoly | Global Identifiability of Non Linear Models of Biological Systems[END_REF]. The resulting algorithm is only based on differential algebra. It is implemented in Maple, a symbolic computation language, and uses the package Diffalg especially.

The paper is organized as follows. First, section 1 proves some results necessary to the development of the identifiability algorithm. Section 2 gives results of identifiability in the most general framework. Section 3 considers K(θ) instead of K, which allows a significant simplification of the algorithm while giving general identifiability results. Then section 4 describes the algorithm and its features. Finally, the algorithm is used for analyzing identifiability of some nonlinear academic, pharmacokinetic and physiological models and its efficiency is pointed out. In our approach, differential algebra allows the validation of the proposed algorithm. If the reader is unfamiliar with such notions [START_REF] Kolchin | Differential algebra and algebraic groups[END_REF], some useful definitions and propositions can be found in Appendices A, B and C.

Characteristic presentation

The differential ideal generated by the equations of Γ is considered in the differential field K< x,y,u, θ>. Its radical is denoted by I. From the ranking:

[θ] ≺ [y, u] ≺ [x] (3)
that eliminates state variables and from the equations of Γ, the characteristic presentations associated to I are computed.

Proposition 1.1 If I, endowed with the ranking (3), admits a characteristic presentation, this presentation has the following form: { θ1 , . . . , θq , P 1 (y, u, θ), . . . , P m (y, u, θ), Q 1 (y, u, θ, x), . . . , Q n (y, u, θ, x)} (4)

where the leader of the polynomial P k is y k for k = 1, . . . , m, and where the leader of the polynomial Q j is x j for j = 1, . . . , n.

Proof -We propose to the reader unfamiliar with differential algebra to consult Appendices B and C, necessary to the proof understanding.

Let C be a characteristic presentation of I.

• In a first time, we prove that the differential polynomials θi , i = 1, . . . , q are in C:

θ i has a
θ] ≺ [u] ≺ [x] ≺ [y]
is considered, the set of the polynomials involved in Γ consists in the characteristic presentation of I (only implicit models are considered). However, no polynomial of Γ admits θ i as leader. Therefore, if W = 0, the rewritting rules cannot rewrite as zero the differential polynomial θ i + W . Finally, θ i + W does not lie in I. Therefore, for i = 1, . . . , q, θi ∈ C.

• In the same way, one can prove that C does not contain any polynomial of the form F (u, θ).

• Now we show that there exists a unique polynomial, in C, of the form P i (y, u, θ) whose y i is the leading variable, for all i = 1, . . . , m:

Since y i is differentially algebraic over K< u, θ>, for all i = 1, ..., m, there exist some polynomials of the form P i (y, u, θ) in I. Let us suppose that y i is not the leading variable of any element of C and let us consider the polynomials of C which have a leader lower than P i (y, u, θ). B is the set containing such elements. As it is a subset of a differentially triangular set, B is also a differentially triangular set. A differentially triangular set lower than B is created by placing P i (y, u, θ), or its partial remainder w.r.t the polynomials P k (y, u, θ)(1 ≤ k < i), as the last polynomial in B. The other elements of C are partially reduced w.r.t this added polynomial in order to obtain a differentially triangular set lower than C. But C is minimal by hypothesis. This contradiction implies that y i is the leading variable of a polynomial of C for all i = 1, .., m. As in ordinary differential algebra, the polynomials of a triangular set have different principal variables, so there exists exactly the quantity m of such polynomials.

• In the same way, the existence of exactly n polynomials of the form Q(y, u, θ, x) can be proved.2

In general, I should be written as the intersection of regular differential ideals, each one admitting a characteristic presentation (see (34) in Appendix D). However in the following, I, endowed with the ranking (3), is assumed to be a regular ideal presented by a characteristic presentation C. This assumption is not so restrictive. Indeed in the opposite case, the next proposition must be applied to each system corresponding to each component of the decomposition of the ideal.

Now let us introduce a few notations:

• C(θ) is the characteristic presentation C evaluated in the particular value of parameter θ.

• I θ is the radical of the differential ideal generated by Γ for the particular value of parameter θ and C θ is the characteristic presentation associated with the ranking

[y, u] ≺ [x].
In order to avoid the evaluation of C(θ) at each value of parameters, the following result gives a sufficient condition for the equality C θ = C(θ).

Proposition 1.2 Let C = {c 1 , . . . , c m+n , θ1 , . . . , θq } be the characteristic presentation of the differential ideal I endowed with the ranking (3). If, for every θ ∈ Ω q and for every i = 1, . . . , m + n, the initial of c i (θ) ∈ C(θ) is not equal to zero and none of its factors ( = 1) is a divisor of all the other coefficients of

c i (θ) in K[N ], then C θ = C(θ) for all θ ∈ Ω q .
Proof -In this proposition the set of the leaders L of the elements of C is considered, N denotes the other derivatives occuring in C and K[N ] is the polynomial ring built over N with coefficients in K. This proof uses the results and the notations of Appendix C. Let us notice that C is strongly normalized. Thus, each initial of C is in K[N ], and θ i cannot be the leader of any polynomial in C (see [START_REF] Noiret | Utilisation du calcul formel pour l'identifiabilité de modèles paramétriques et nouveaux algorithmes en estimation de paramètres[END_REF]). C(θ) is a characteristic set since it satisfies the two following points:

• C(θ) is an autoreduced set since the evaluation of the polynomials c i remains the leader (θ has been assumed not to cancel initials). Moreover, such an evaluation does not change the degree of elements of L appearing in the polynomials c i .

• Suppose that there exists a polynomial p reduced w.r.t C(θ). Such a polynomial is reduced w.r.t C and, since C is a characteristic set of I, p = 0.

Next, the evaluation in θ does not change the leaders of any polynomial of C. Since C is strongly normalized, C(θ) is also strongly normalized. The elements of C(θ) are primitive on K[N ] because, by assumption, the evaluated coefficients have no common factor. In this way, C(θ) is a characteristic presentation of I θ . Therefore the uniqueness of the characteristic presentation of an ideal, endowed with a ranking, implies

C θ = C(θ). 2
2 Input-output ideal and identifiability results

Now let us introduce I io θ , the ideal obtained after eliminating state variables. Thus the set C io θ = C θ ∩ K(θ){u, y} is a characteristic presentation of the ideal I io θ , called the input-output characteristic presentation. As a consequence of Proposition 1.1, I io θ contains the polynomials P i , i = 1 . . . m. The polynomials P i , i = 1 . . . m, of C io θ can be seen as polynomials in y, u and their derivatives with coefficients in K(θ). In the following, those polynomials will be written as

P i (y, u, θ) = m i 0 (y, u) + ni k=1 p i k (θ)m i k (y, u)
where m i 0 is not equal to zero. Let us denote by d i for i = 1 . . . m, the Wronskians of functions m i k (y, u), k = 1 . . . n i . The non-degenerate solution, evocated in the introduction, is defined by: Definition 2.1 A non-degenerate solution (x, y, u, θ) of Γ is a solution such that (i) no separant or initial of

P i (i = 1 . . . m) and Q j (j = 1 . . . n) in (4) is zero, (ii) no Wronskian d i (i = 1 . . . m) is zero.

Rational identifiability and input-output characteristic presentation

In this section, we assume C θ = C(θ) for all θ.

Proposition 2.1 Let θ and θ two parameter vectors and C io θ and C io θ the corresponding input-output characteristic presentations. The corresponding solutions of Γ are assumed to be respectively (x, y, u, θ) and (x, y, u, θ) and non-degenerate solutions. Then

∀ θ ∈ Ω q C io θ = C io θ ⇒ (p i k (θ) = p i k ( θ), k = 1 . . . n i , i = 1 . . . m).
Proof -It is clear that C io θ = C io θ is equivalent to P i (y, u, θ) = P i (y, u, θ), i = 1 . . . m for all y and u (the set of polynomials P i (y, u, θ) is a triangular set). Since (y, u) satisfy (ii) (definition 2.1), the previous equalities imply the equalities of the coefficients of the functions m i k (y, u), k = 1 . . . n i ,. 2

Remark 2.1 Moreover, under the assumptions of the previous proposition, it is easy to prove that p i k (θ) for k = 1 . . . n i , i = 1 . . . m are in the field K < u, y >. Therefore, they will be rewritten as:

p i k (θ) = g i k (y, u) (k = 1 . . . n i , i = 1 . . . m).

Exhaustive summary and identifiability results

The exhaustive summary [START_REF] Walter | Identifiability of state space models[END_REF] of Γ is given by the vector of coefficients in θ:

{p i k (θ), k = 1 . . . n i , i = 1 . . . m}.
In order to deduce identifiability results from the exhaustive summary, the following system is considered:

p i k (θ) = p i k ( θ) , k = 1, . . . , n i , i = 1, . . . , m . (5)
It can be rewritten as a differential polynomial system:

S u    p(θ, θ) = 0, θi = 0, i = 1, . . . , q, θi = 0, i = 1, . . . , q. (6)
Let us denote by S, the radical of the differential ideal generated S u , which is considered in K < θ, θ> such that all particular cases are obtained.

Proposition 2.2 If S, endowed with the ranking [θ] ≺ [ θ], admits a characteristic presentation C, C has the following form:

A 1 (θ 1 ), A 1 (θ 1 , θ 2 ), . . . , A q (θ 1 , . . . , θ q ), B 1 (θ, θ1 ), B 2 (θ, θ1 , θ2 ), . . . , B q (θ, θ1 , . . . , θq ) (7)
where the leader of the polynomial A k is θ k or θk for k = 1, . . . , q , and where the leader of the polynomial B j is θj or θj for j = 1, . . . , q.

Proof -The functions θi are in S and θ i has a minimal ranking in (3) so differential polynomials which have θi , or a lower ranked variable as leader, are in C. As C is a differentially triangular set, the leaders of C are different and its elements are reduced pairwise. As a consequence, in the characteristic presentation C, there exists a number of q polynomials whose leading variable is θ i for all i = 1, . . . , q. In the same way, the existence of B j (j = 1, . . . , q ) can be shown. 2

In general, S should be written as the intersection of regular differential ideals which admit a characteristic presentation (see (34) in Appendix D): a general component and particular components of the decomposition of the ideal. The particular components correspond to particular values of (θ, θ) which are such that some separants or initials of (7) of the general component are equal to zero.

Proposition 2.3 Let us assume that all separants and initials of polynomials in C are non-zero. Then three different situations can arise in ( 7):

(i) All B i are of order 0 and degree 1 in θi , and moreover B i = θi -θ i .

(ii) All B i are of order 0 in θi , and some B j is of degree > 1 in θj .

(iii) For some i one has B i = θi .

Proof -This proposition is obvious. Let us only prove that B i = θi -θ i in the case (i). If each B i is of degree one in θi , then it must be independant of the other θj for (7) to be autoreduced (see appendices B and C). Thus each B i can be rewritten as P i (θ) θi -Q i (θ), where P i and Q i are polynomials. .Then, the assumption of the proposition implies (6) to have one and oonly one solution. On the other hand theta = θ is a solution of (6) and the polynomials B i are primitive over K[θ] (see appendix C and [START_REF] Boulier | Computing canonical representatives of regular differential ideals[END_REF]), which leads to

B i = θi -θ i . 2
It leads to the following identifiability theorem.

Theorem 2.1 Let us assume that all separants and initials of polynomials in C are non-zero and that there exists a non-degenerate solution of Γ. If the characteristic presentation [START_REF] Fliess | Nonlinear observability, identifiability, and persistent trajectories[END_REF] has the form of -case (i) above, then the model is rationally identifiable.

-case (ii) above, then the model is algebraically identifiable.

-case (iii) above, then the model is not algebraically identifiable.

Proof -As seen in Remark 2.1, the elements of the exhaustive summary can be rewritten as:

p i k (θ) = g i k (y, u) , k = 1 . . . n i , i = 1 . . . m . Moreover g i k (y, u
) is a differential rational function in y and u which is constant for k = 1 . . . n i , i = 1 . . . m, and will be only denoted by g i k for k = 1 . . . n i , i = 1 . . . m. Thus the system (5) can be rewritten:

     n i k ( θ) = d i k ( θ)g i k , k = 1, . . . n i , i = 1 . . . , m, θi = 0, i = 1, . . . , q, ġi k = 0, k = 1, . . . n i , i = 1, . . . , m, (8)
where n i k ( θ) and d i k ( θ) are polynomials in θ. Then, it is easy to prove as previously that the differential ideal generated by [START_REF] Fliess | Local Realization of Linear and Nonlinear Time Varying Systems[END_REF] with the ranking

[g] ≺ [ θ], (g = {g i k , k = 1 . . . n i , i = 1 . . . m}) (9)
admits a general characteristic presentation which contains the polynomials:

{S 1 (g, θ1 ), S 2 (g, θ1 , θ2 ), . . . , S q (g, θ1 , . . . , θq )}. [START_REF] Hermann | Nonlinear controllability and observability[END_REF] The system (8) admits the same number of solutions as the system (6). Thus the polynomials S i will be in the same situation as the polynomials B i with regard to the order and the degree in θi . Since the (g i k , k = 1 . . . n i , i = 1 . . . m) are differential rational functions in y and u the results of the theorem 2.1 are deduced.2

In the previous theorem, the most general results are obtained in taking the characteristic presentation of the general component. But all particular components can be analyzed by the same way, which leads to identifiability results of models corresponding to particular parameter values.

A simplified analysis with K(θ)

When the particular cases are not interesting for the user, the components of θ can be assumed transcendent on K. The system Σ θ can be rewritten:

Γ θ    p( ẋ, x, u, θ) = 0, q(x
, y, θ) = 0, r(x, y, θ) = 0, [START_REF] Joly-Blanchard | Some remarks about identifiability of uncontrolled nonlinear systems[END_REF] and the differential ideal generated by the equations of Γ θ can be considered in the differential field K(θ) < x,y,u >, where K(θ) corresponds to the field of constants IR(a, θ) or IR(θ). In this context, a solution of Γ θ is a triplet of functions (x, y, u) satisfying all the model equations. The advantage of the choice of K(θ) is relative to the number and complexity of reductions which are consequently simplified, even if some particular cases are lost. In this case J denotes the radical of the differential ideal generated by the equations of Γ θ with the ranking [y, u] ≺ [x]. In the same way as in Proposition 1.1 if J admits a characteristic presentation, it can be shown that this presentation has the following form: {P 1 (y, u, θ), . . . , P m (y, u, θ), Q 1 (y, u, θ, x), . . . , Q n (y, u, θ, x)} [START_REF] Joly-Blanchard | Some remarks about an identifiability result of nonlinear systems[END_REF] where the leader of the polynomial P k is y k for k = 1, . . . , m, and where the leader of the polynomial Q j is x j for j = 1, . . . , n. In the following J , endowed with the above ranking, is assumed to be a regular ideal presented by a characteristic presentation. In the opposite case, only the most general component will be considered. The input-output ideal and its characteristic presentation are defined the way it is done in the first section.

Definition 3.1 A non-degenerate solution (x, y, u) of Γ θ is a solution such that (i) no separant or initial of P i (i = 1 . . . m) and Q j (j = 1 . . . n) in ( 12) is equal to zero, (ii) no Wronskian d i (i = 1 . . . m) is zero.

Furthermore, the ideals I (defined in section 1) and J admit characteristic presentations which contain the same polynomials {P 1 (y, u, θ), . . . , P m (y, u, θ), Q 1 (y, u, θ, x), . . . , Q n (y, u, θ, x)}.

Therefore Proposition 2.1 is also true.

The analysis of the exhaustive summary can be also simplified because each component θ i is assumed to be transcendent on IR. The following differential polynomial system is considered:

S θ p(θ, θ) = 0, θi = 0, i = 1, . . . , q. (14)
The differential ideal generated by S θ can be considered in the differential field K(θ)< θ> to reduce the number and complexity of reductions. Let us denote S t the radical of the differential ideal generated by the equations of the system S θ . With the ranking

[ θ1 ] ≺ [ θ2 ] ≺ [. . .] ≺ [ θq ] (15)
a characteristic presentation of S t is computed and it is easy to prove that this presentation has the following form:

{B 1 (θ, θ1 ), B 2 (θ, θ1 , θ2 ), . . . , B q (θ, θ1 , . . . , θq )} (16)
where the leader of the polynomial B j is θj or θj for j = 1, . . . , q.

Here the general components of S and S t contain the same polynomials [START_REF] Ollivier | Identifiabilité des systèmes[END_REF].

Finally by this way Proposition 2.3 and Theorem 2.1 are also true if K(θ) is considered instead of K.

Algorithm

Now let us present the algorithm. It will be referred to it as Algo. Let us remark steps 3 and 7 of Algo1 are based on Rosenfeld-Groebner algorithm which has been realized by F. Boulier in Maple VII [START_REF] Boulier | Computing representations for the radicals of a finitely generated differential ideals[END_REF]. The algorithm is implemented in Maple VII and runs on any Pentium PC. Data: f, g and h.

Step 1 The software rewrites the original system Σ θ as the system Γ θ defined by (2).

Step 2 The differential field K (or K(θ)) is given and a standard ranking is implicitly introduced. It is possible to select a most suitable ranking by a careful analysis of the system.

Step 3 Rosenfeld-Grobner algorithm computes input-output characteristic presentations. If the differential field is K(θ) the general input-output characteristic presentation is only computed and the algorithm goes to step 5, otherwise an input-output characteristic presentation is chosen by the user.

Step 4 The values of θ for which the polynomials P i are not primitive over K[N ] (i.e the assumptions of proposition 1.2 are not satisfied) are computed.

Step 5 It verifies that the Wronskians d i are not in the differential ideal generated by the equations of Γ (or Γ θ ).

Step 6 It saves the coefficients p i k (θ) in a list called the "exhaustive summary". This summary is simplified in order to extract its smallest generator system in terms of degree, number of monomials,...

Step 7

The exhaustive summary is analyzed by Rosenfeld-Grobner algorithm: it is a purely differential and algebraic step. Then the results of identifiability are provided. In this step the considered equations are symmetrical in θ and θ, which leads to a simplified reduction procedure. A priori, the analysis of the exhaustive summary leads to equations of the following type:

p i k (θ) = g i k for k = 1 . . . n i , i = 1 . . . m, (17)
which corresponds to q + n 1 + ... + n m indeterminates and K is the differential field necessarily. Our strategy consists in rewriting the system such that it is symmetrical in θ and θ. In this case there are 2q indeterminates (often 2q ≤ q + n 1 + ... + n m ). Moreover it is possible to chose K(θ) as differential field as in [START_REF] Ljung | On global identifiability for arbitrary model parametrizations[END_REF], which gives q indeterminates only. Consequently the number of indeterminates is significantly reduced.

Finally, let us note that if the algorithm does not successfully terminate because the computation of the input-output characteristic presentation is too complex or the analysis of the exhaustive summary fails, the algorithm can be reapplied by using a different ranking between the variables in steps 2 or (and) 7.

Examples

In this section, two examples are presented in order to illustrate the algorithm described above. The second one is a pharmaco-kinetic model . In each case, the algorithm gives an exhaustive description of all the possible cases.

An academic example

The following academic example was treated without control in [START_REF] Denis-Vidal | An easy to check (un)identifiability criterion for uncontrolled systems and its applications[END_REF]:

   ẋ1 = θ 1 x 2 1 + θ 2 x 1 x 2 + u ẋ2 = θ 3 x 2 1 + θ 4 x 1 x 2 y = x 1 (18)
Here are the different steps of Algo:

• Step 1: The software rewrites the system as :

       ẋ1 = θ 1 x 2 1 + θ 2 x 1 x 2 + u ẋ2 = θ 3 x 2 1 + θ 4 x 1 x 2 y = x 1 θ = 0 (19)
• Step 2: The field of constants IR is chosen and the standard ranking is implicitly given.

• Step 3: Algo returns three cases:

i) The general case (Ω q = {(θ 1 , θ 2 , θ 3 , θ 4 ) ∈ IR 4 , θ 2 = 0}) is given by the following characteristic presentation:

{x 1 -y, x 2 θ 2 y 2 + y(-ẏ + y 2 θ 1 + u), y ÿ + uy -y u -ẏ2 + uy 2 θ 4 -(θ 1 + θ 4 ) ẏy 2 -(θ 2 θ 3 -θ 1 θ 4 )y 4 , θ1 , θ2 , θ3 , θ4 } (20)
ii) θ 2 = 0 (then Ω q = {(θ 1 , θ 3 , θ 4 ) ∈ IR 3 }) is a particular case corresponding to the characteristic presentation:

ẋ2 -θ 3 y 2 -θ 4 yx 2 , x 1 -y, -u + ẏ -y 2 θ 1 , θ1 , θ3 , θ4 , θ 2 . (21)
iii) y = 0 .

The characteristic presentation 20 corresponding to the case i) is chosen.

• Step 4: It verifies that the hypothesis of Proposition 1.2 is valid for all θ ∈ Ω q .

• Step 5: It verifies that the Wronskian of {y 2 ẏ, y 4 , -uy 2 } is not equal to zero.

• Step 6: The exhaustive summary given by the software is {θ 1 , θ 4 , θ 1 θ 4 -θ 2 θ 3 }.

•

Step 7: The analysis of this exhaustive summary leads to

θ1 -θ 1 , θ2 θ3 -θ 2 θ 3 , θ3 , θ4 -θ 4 . (22)
Thus θ 1 , θ 4 and θ 2 θ 3 are in the field K< u,y>. But the analysis of this exhaustive summary proves that the model is not algebraically identifiable.

Now the characteristic presentation 21 corresponding to the case ii) is chosen.

• Step 4: It verifies that the hypothesis of Proposition 1.2 is valid for all θ ∈ Ω q .

• Step 5: It gives y 2 for the Wronskian which is not equal to zero.

• Step 6-7: The exhaustive summary is {θ 1 }. Its analysis leads to θ1 -θ 1 , θ4 , θ3 , θ4 .

and the model is not algebraically identifiable.

Finally the characteristic presentation iii) corresponds to a degenerate and unrealistic solution.

The computation time of all these steps on a Pentium 4 with 2.2MHz is 1s.

A real pharmacokinetic model

Now a real pharmacokinetic model [START_REF] Demignot | Effect of prosthetic sugar groups on the pharmacokinetics of glucoseoxidase[END_REF] is considered. It is an uncontrolled model and it was solved by pen and paper in [START_REF] Joly-Blanchard | Some remarks about identifiability of uncontrolled nonlinear systems[END_REF]:

     ẋ1 = α 1 (x 2 -x 1 ) - V m x 1 k c + x 1 ẋ2 = α 2 (x 1 -x 2 ) y = x 1 (24)
The unknown vector parameter is θ = {α 1 , α 2 , k c , V m }.

Here are the different steps of Algo:

• Step 1: The software rewrites the system as the following polynomial differential system:

       ẋ1 (k c + x 1 ) = α 1 (x 2 -x 1 )(k c + x 1 ) -(V m x 1 ) ẋ2 = α 2 (x 1 -x 2 ) y = x 1 k c + x 1 = 0 (25)
• Step 2: The field of constants IR is chosen and the standard ranking is implicitly introduced.

• Step 3: Algo returns two cases:

i) The general case Ω q = {θ ∈ IR 4 , α 1 = 0} is given by the following characteristic presentation:

           x 1 -y, -α 1 k c x 2 -α 1 x 2 y + yk c + α 1 y + V m y, 2k c ÿy + k 2 c ÿ + (α 1 + α 2 ) ẏy 2 + 2k c (α 1 + α 2 ) ẏy + ((α 1 + α 2 )k c + V m )k c ẏ +α 2 V m y 2 + α 2 V m k c y -ÿy 2 , α1 , α2 , Vm , kc . (26)
chosen as field of constants in [START_REF] Audoly | Global Identifiability of Non Linear Models of Biological Systems[END_REF] as in Algo in order to compute the characteristic set and presentation. In [START_REF] Audoly | Global Identifiability of Non Linear Models of Biological Systems[END_REF] the existence of a non degenerate solution is assumed (which corresponds to the non-running of step 5 of Algo). Algo leads to rational identifiability of the model and in [START_REF] Audoly | Global Identifiability of Non Linear Models of Biological Systems[END_REF] a similar result is obtained. But in [START_REF] Audoly | Global Identifiability of Non Linear Models of Biological Systems[END_REF] a numerical random point θ = {4, 6, 7, 3, 4, 6, 1, 13, 8, 12, 18, 4} is chosen for constructing and analyzing the exhaustive summary, and the Groebner basis is calculated by using the Buchberger algorithm ( [START_REF] Buchberger | An algorithmical criterion for the solvability of algebraic system equation[END_REF]). Algo has been implemented on a Pentium 3 with 1Mhz and on a Pentium 4 with 2.2Mhz. The computation time for this model is 25.1s (Pentium 3) and 3s (Pentium 4). In [START_REF] Audoly | Global Identifiability of Non Linear Models of Biological Systems[END_REF] the algorithm has been implemented on a Pentium 3 with 0.55Mhz and the computation time was 509.48s. The discrimination between computation times on Pentium 3 is specially due to the analysis of the exhaustive summary which is more efficient with Algo (see step7).

Conclusion

In this paper, we have shown how to analyze algorithmically the algebraic and rational identifiability of nonlinear controlled or uncontrolled dynamical models from an approach based on differential algebra. The input-output approach does not make use of initial conditions but can be applied also to systems given in implicit form systems. The recent notion of characteristic presentation of a differential polynomial model is used. It summarizes all the information contained in the differential ideal into a finite number of polynomials and it supplies an effective way for testing the equality of some differential ideals. In order to apply this notion we have proved some interesting and necessary theoretical results. Characteristic presentations of input-output and exhaustive summary ideals allow the elaboration of Algo such that all the steps of the identifiability analysis are computed by software. Moreover, Algo may do an exhaustive analysis of particular cases and has been compared to an another algorithm. Lastly, the authors put the software at the disposal of anyone concerned by this kind of problem. Theorem 6.1 [START_REF] Boulier | Computing representations for the radicals of a finitely generated differential ideals[END_REF] Let Σ be a system of differential polynomials over K{V } where K is a differential field of characteristic zero and I the differential ideal generated by Σ. A differential polynomial q vanishes on every solution of Σ, in every differential field extension of K, if and only if q lies in √ I.

This gives an easy way to test if a differential polynomial q lies in a differential ideal. Indeed, if √ I admits a characteristic presentation denoted by C, q ∈ √ I if and only if q is reduced w.r.t C. Moreover, an algorithm implemented within a package in symbolic computation permits the treatment of this question [START_REF] Boulier | Computing representations for the radicals of a finitely generated differential ideals[END_REF]. Technically, from a finite set of differential polynomials and a given ranking, Rosenfeld-Groebner algorithm computes a list (understand "intersection") of characteristic presentations C 1 , . . . , C j of regular differential ideals I 1 , . . . , I j (I k = [C k ] : H ∞ C k , k = 1, . . . , j) so that √ I = I 1 ∩ I 2 ∩ . . . ∩ I j .

Informally, the different ideals I k correspond to different classes of solutions. In particular, the algorithm separates the solutions of Σ which do not depend on the same number of arbitrary constants.

  1 A model is algebraically identifiable if and only if any parameter θ i is algebraic over K< u, y>.

  minimal ranking in (3) so only differential polynomials which have θi , or a lower ranked variable as leader, are in C. Such a polynomial is written θ i +W , with W ∈ K< θ 1 , ...., θ i-1 >. If such a polynomial exists, it lies in the ideal I and, by definition, it will be rewritten as zero modulo the rewriting rules of every characteristic presentation of this ideal, corresponding to different rankings. If the ranking [

ii) α 1 = 0 is a particular case (Ω q = {θ ∈ IR 4 , α 1 = 0}) given by the following characteristic presentation: { ẋ2 -α 2 y + α 2 x 2 , x 1 -y, ẏ(k c + y) + V m y, α 1 , α2 , Vm , kc }.

The characteristic presentation (26) corresponding to the case i) is chosen.

• Step 4: The hypothesis of Proposition 1.2 is not valid if V m k c = 0. Indeed, with notations of Appendix C, the set L is reduced to L = {ÿ} and the input-output characteristic presentation can be rewritten as {(y + k c ) 2 ÿ + T, α1 , α2 , Vm , kc } where (y + k c ) 2 and T belong to IR[θ, y, ẏ]. If V m = 0, (y + k c ) 2 is a divisor of T and if k c =0, y 2 is a divisor of T . Consequently, the set Ω q becomes Ω q = {θ ∈ IR 4 , α 1 = 0, V m k c = 0}.

• Step 5: It verifies that the Wronskian of ÿy, ÿ, ẏy 2 , ẏy, ẏ, y 2 , y

is not in the differential ideal generated by (25).

• Step 6: The exhaustive summary, given by the software, is:

•

Step 7: The analysis of this exhaustive summary leads to:

which proves that the model is rationally identifiable.

Now the characteristic presentation 27 corresponding to the case ii) is chosen.

• Step 4: The hypothesis of Proposition 1.2 is also not valid if V m k c = 0.

• Step 5: It verifies that the Wronskian of { ẏ, y} is not in the differential ideal generated by (25).

•

Step 6-7: The exhaustive summary is {V m , k c } and its analysis leads to

The model is not algebraically identifiable.

The computation time of all these steps (except step 5) on a Pentium 4 with 2.2MHz is 1.1s.

Comparison

The following example discussed in [START_REF] Walter | Identifiability of state space models[END_REF] and [START_REF] Audoly | Global Identifiability of Non Linear Models of Biological Systems[END_REF] is considered in order to compare the efficiency of Algo with another similar algorithm proposed in [START_REF] Audoly | Global Identifiability of Non Linear Models of Biological Systems[END_REF]. The model equations are:

The unknown parameters are:

Algo returns the characteristic presentation corresponding to the general case and an exhaustive summary of 39 equations. The analysis of this summary is purely differential and algebraic. The set IR(θ) is

Appendix A. Commutative algebra

Let K be a field, X be an ordered alphabet and K[X] be a polynomial ring. Let p be a non constant polynomial in K[X]. The leader of p is the greatest indeterminate x of X which occurs in p. We denote by d the highest power of this variable in p. The separant s p of p is the partial derivative of p with respect to the leader x while the initial i p is the coefficient of x d .

Given A ⊂ K[X]\K, H A denotes the set of initials and separants of its elements. A is said to be triangular if its elements have distinct leaders. A polynomial p is said to be strongly normalized with respect to (w.r.t) A if no leader of A occurs in the initial of p. The set A is said to be strongly normalized if every p in A is strongly normalized w.r.t A\{p}.

Let p and q be two polynomials over k[X]\K. p is lower than q or that p is lower ranked than q:

• if the leader of p is lower than the leader of q,

• or if, p and q have the same leader u and the degree d of u in p is lower than the degree of u in q.

The notation p q means that two polynomials have the same leader and the same degree in this variable.

If R is a unique factorization domain and p ∈ R[X] then p can be rewritten as p = a 0 t 0 + . . . + a k t k , where each t i is a power product of elements of X and each a i is in R. The content of p over R is the highest common factor of its coefficients, i.e. cont(p) = gcd(a 0 , . . . , a k ). The primitive part of p over R is the polynomial pp(p) = p cont(p)

. A polynomial is said to be primitive if it is equal to its primitive part.

Let I be an ideal over K[X]. If S = {s 1 , . . . , s t } is a finite family of elements of K[X] then the saturation of I by S, noted I : S ∞ , is the ideal:

Appendix B. Differential algebra: reduction

With the notations of the introduction, a ranking R is a well-ordering over the indeterminates and their derivatives with the following properties for every u, v ∈ ΘV and δ ∈ ∆:

Rankings such as {u ≺ v ⇒ δu ≺ φv} (for every δ ∈ ∆ and φ ∈ ∆, and every v, u ∈ ΘV ) are said to be elimination rankings and are written

With a given ranking, the alphabet ΘV is ordered and the leader, the separant, the initial... well defined.

Let v be the leader of p and d be the degree of p in this variable. A differential polynomial q is said to be partially reduced w.r.t p if no proper derivative of v occurs in q. It is said to be reduced w.r.t p if it is partially reduced w.r.t p and deg(q, v) ≤ d.

Let a set A ⊂ K{V }\K. A is said differentially triangular if it is a triangular set and if its elements are pairwise partially reduced. Moreover, A is said to be autoreduced if its elements are pairwise reduced. Let us notice that every autoreduced set is differentially triangular.

Let

. . , B s be two autoreduced sets, A is lower than B if one of the two following properties is true:

Appendix C. Differential algebra: characteristic presentation

A differential ideal of K{V } is an ideal of K{V } which is stable under derivation. Let J be a differential ideal of K{V } and R be a ranking. A set D ⊂ J is a characteristic set if D is autoreduced and J contains no nonzero polynomial reduced w.r.t D.

Given a set C ⊂ J , we now introduce the following notations:

• L denotes the set of the leaders of the elements of C,

• N denotes the other derivatives occuring in C,

• [C] is the differential ideal generated by the elements of C.

and C is a strongly normalized autoreduced set of K[L, N ] such that the elements of C are primitive over K[N ] (see [START_REF] Boulier | Computing canonical representatives of regular differential ideals[END_REF]).

This notion supplies an effective way for testing the equality of two regular ideals: such ideals are equal if and only if, once endowed with the same ranking, their characteristic presentation contains the same polynomials (the characteristic presentations are said equal).

Appendix D. Symbolic Computation: Rosenfeld-Groebner algorithm [START_REF] Boulier | Computing representations for the radicals of a finitely generated differential ideals[END_REF] Differential algebra gives some algorithmic methods to solve questions appearing in the analysis of partial or ordinary differential equations: how can some variables be eliminated? do some solutions exist? Given a differential system Σ written as polynomial equations (p k = 0, k = 1, . . . , N ) in the differential indeterminates V , these differential polynomials generate a differential ideal (denoted by I), i.e. a set closed under sum, product and derivation. Moreover, the radical (denoted by √ I) of I is the ideal of all the differential polynomials, one power of which lies in I. The existence of system Σ solutions is given by the following theorem: