Alexandre Seuret
email: alexandre.seuret@gipsa-lab.genoble-inp.fr

Matthew M Peet
email: mpeet@iit.edu

SOS for sampled-data systems

Keywords: Sampled-Data systems, Lyapunov function, Sum of squares

published or not. The documents may come

INTRODUCTION

In recent years, much attention has been paid to Networked Control Systems (NCS) (see [START_REF] Hespanha | A survey of recent results in networked control systems[END_REF], [START_REF] Zampieri | A survey of recent results in Networked Control Systems[END_REF]). These systems contain several distributed plants which are connected through a communication network. In such applications, a heavy temporary load of computation on a processor can corrupt the sampling period of a controller. On the other side, the sampling period can be included in the design in order to avoid this load. In both cases, the variations of the sampling period will affect the stability properties of the system. Another phenomenon, which has been widely investigated concerns stability under packet losses. In wireless networks, a transmission of data packets is not always guaranteed. The objective is to guarantee stability even if some packets are lost in the communication. It is thus an important issue to develop robust stability conditions with respect to the variations of sampling period.

Sampled-data systems have extensively been studied in the literature [START_REF] Chen | Optimal sampled-data control systems[END_REF], [START_REF] Fridman | Robust sampleddata stabilization of linear systems: An input delay approach[END_REF], [START_REF] Fujioka | Stability analysis of systems with aperiodic sampleand-hold devices[END_REF], Zhang and Branicky [2001], Zhang et al. [2001] and the references therein. It is now reasonable to design controllers which guarantee the robustness of the solutions of the closedloop system under periodic samplings. However in the case of asynchronous sampling, there are still several open problems. For example, the practical situation where the difference between two successive sampling instants is not constant but timevarying. Recently, several articles have addressed the problem of time-varying periods based on a discrete-time approach, [START_REF] Suh | Stability and stabilization of nonuniform sampling systems[END_REF], [START_REF] Oishi | Stability and stabilization of aperiodic sampled-data control systems: An approach using robust linear matrix inequalities[END_REF], [START_REF] Hetel | Stabilization of arbitrary switched linear systems with unknown time-varying delays[END_REF]. Recent papers have considered the modeling of continuous-time systems with sampled-data control in the form of continuous-time systems with delayed control input. In [START_REF] Fridman | Robust sampleddata stabilization of linear systems: An input delay approach[END_REF], a Lyapunov-Krasovskii approach was introduced. Improvements were provided in [START_REF] Fujioka | Stability analysis of systems with aperiodic sampleand-hold devices[END_REF], [START_REF] Mirkin | Some remarks on the use of time-varying delay to model sample-and-hold circuits[END_REF], using the small gain theorem, and in [START_REF] Naghshtabrizi | Exponential stability of impulsive systems with application to uncertain sampled-data systems[END_REF], based on the analysis of impulsive systems. These approaches dealt with time-varying sampling periods as well as with uncertain systems (see [START_REF] Fridman | Robust sampleddata stabilization of linear systems: An input delay approach[END_REF] and [START_REF] Naghshtabrizi | Exponential stability of impulsive systems with application to uncertain sampled-data systems[END_REF]). Nevertheless, these sufficient conditions are still conservative. This means that the sufficient conditions obtained by continuous time approaches are not able to guarantee asymptotic stability whereas the system is stable. Recently several authors [START_REF] Fridman | A refined input delay approach to sampled-data control[END_REF], [START_REF] Liu | Discontinuous Lyapunov functionals for linear systems with sawtooth delays[END_REF], [START_REF] Seuret | Stability analysis for sampled-data systems with a time-varying period[END_REF] refined those approaches and obtained tighter conditions.

The key insight of this paper is that once we have developed the discrete-continuous Lyapunov conditions sufficient for stability, then these conditions can be verified computationally using recently developed algorithms for the optimization of polynomial functions. In particular, we use the machinery developed in [START_REF] Peet | Positive forms and stability of linear time-delay systems[END_REF] to reformulate the stability question as a convex optimization problem with polynomial variables. We then use the software package SOSTOOLS [START_REF] Prajna | Introducing SOSTOOLS: a general purpose sum of squares programming solver[END_REF] to solve the optimization problem. As can be seen in the numerical examples, the result is a sequence of stability tests of increasing accuracy. Furthermore, in the numerical examples, the accuracy of the stability test approaches the analytical limit exponentially fast as a complexity of the algorithm increases. This article is based on a Lyapunov approach introduced in [START_REF] Seuret | A novel stability analysis of linear systems under asynchronous samplings[END_REF]. This result is based on the discrete-time Lyapunov theorem and expressed with the continuous-time model of sampled-data systems. More precisely, this article analyzes the link between the discrete-time Lyapunov theorem employed, for instance in [START_REF] Suh | Stability and stabilization of nonuniform sampling systems[END_REF], [START_REF] Oishi | Stability and stabilization of aperiodic sampled-data control systems: An approach using robust linear matrix inequalities[END_REF], [START_REF] Hetel | Stabilization of arbitrary switched linear systems with unknown time-varying delays[END_REF], and the continuous-time approach proposed in [START_REF] Fridman | Robust sampleddata stabilization of linear systems: An input delay approach[END_REF], [START_REF] Naghshtabrizi | Exponential stability of impulsive systems with application to uncertain sampled-data systems[END_REF], [START_REF] Fridman | A refined input delay approach to sampled-data control[END_REF], [START_REF] Seuret | Stability analysis for sampled-data systems with a time-varying period[END_REF]. Asymptotic stability criteria are provided for both synchronous and asynchronous samplings. Those criteria were expressed in terms of linear matrix inequalities. The main contribution of this paper is the use of sum of squares tools to provide larger upper-bounds of the maximum allowable sampling period than the existing ones (based on the continuous-time modeling). This article is organized as follows. The next section formulates the problem. Section 3 presents a result on asymptotic stability of sampled-data systems. Section 4 presents several theorems on asymptotic stability of sampled-data systems expressed in terms of sum of squares. Some examples and simulations are provided in Section 6 and show the efficiency of the method.

Notation : Throughout the article, the sets N, R + , R n , R n×n and S n denote respectively the set of positive integers, positive scalars, the set of n-dimensional vectors, the set of n × n matrices and the set of symmetric matrices of R n×n . The superscript 'T ' stands for the matrix transposition. The notation P > 0 for P ∈ S n means that P is positive definite. The symbols I and 0 represent the identity and the zero matrices of appropriate dimension.

PROBLEM FORMULATION

Consider the linear system with a sampled-data input ẋ(t) = Ax(t) + Bu(t), (1) where x ∈ R n and u ∈ R m represent the state variable and the input vector. The matrices A and B are of appropriate dimension. They are assumed to be constant and known. The proposed control law for this system is a piecewise-constant state feedback of the form u(t) = u d (t k ), t k ≤ t < t k+1 , where u d is a discrete-time control signal and 0 = t 0 < t 1 < ... < t k < ... are the sampling instants. Note that t k tends to infinity as k tends to infinity. The objective is to ensure the stability of the system together with a state-feedback controller of the form u(t) = Kx(t k ), t k ≤ t < t k+1 .

(2) where the gain K in R n×m is given. Assume that there exists a positive scalar T such that the difference between two successive sampling instants T k = t k+1 -t k satisfies ∀k ≥ 0, 0 < T k ≤ T.

(3) Several authors investigated stability analysis of such systems. In [START_REF] Fridman | Robust sampleddata stabilization of linear systems: An input delay approach[END_REF], a continuous-time approach to modeling sampled-data systems was developed. This paper accounts for sampling effects by using a time-varying delay of the form τ

(t) = t -t k , for t ∈ [t k ,t k+1 ], k = 1, . . .. From (3), it follows that τ(t) ≤ T since τ(t) ≤ t k+1 -t k .
In this approach, the differential equation (1) with the control law (2) is integrated over a sampling period. Then for t ∈ [t k , t k+1 ], we have the following discrete-time system

x k+1 = Γ(T k )x k , ( 4
) where we define the function

Γ(s) = e As + s 0 e A(s-θ ) dθ BK .
The continuous solution between sampling points is given by

x(t) = Γ(t -t k )x k for t ∈ [t k ,t k+1 ]
. Notation: Taking a cue from time-delay systems theory, we denote the segment of solution on t

∈ [t k ,t k+1 ] by x T k , so that x T k (s) = Γ(s)x(t k ) for s ∈ [0, T k ].
We use K n to denote the space of continuous maps from [0, T ] → R n , where recall T is the upper-bound of the T k 's.

If the matrices A and BK and sampling period are constant, the discrete dynamics become x k+1 = Γ(T )x k , where T is the sampling period. A simple method to check the stability of the system is to ensure that Γ(T ) has all eigenvalues inside the unit circle. If the sampling period is time-varying, then we must verify that Γ(T k ) has eigenvalues inside the unit circle for all T k ∈ [0 T ] which corresponds to an infinite dimensional problem. This is obviously complicated and even more so when the system is uncertain or nonlinear. Several authors have investigated this approach [START_REF] Hetel | Robust stability and control of switched linear systems[END_REF], [START_REF] Oishi | Stability and stabilization of aperiodic sampled-data control systems: An approach using robust linear matrix inequalities[END_REF], [START_REF] Suh | Stability and stabilization of nonuniform sampling systems[END_REF].

Based on the fact that sampled-data systems with uncertain sampling period can be seen as an infinite dimensional system, a time-delay approach to represent the sampled-data systems appears to be well-suited. Sufficient conditions for stability of sampled-data systems based were indeed designed in [START_REF] Fridman | Robust sampleddata stabilization of linear systems: An input delay approach[END_REF] by analyzing stability of a class of systems with time-varying delay. However, these results were somewhat conservative in that they did not account for the unique structure of the delay in a sampled-data system. In [START_REF] Naghshtabrizi | Exponential stability of impulsive systems with application to uncertain sampled-data systems[END_REF], the authors introduce a new type of Lyapunov-Krasovskii functional which depends more explicitly on the delay function. In particular, they use the fact the τ = 1 in their formulation. This led to improvement in the accuracy of the stability conditions. In the present article , we take a different approach which does not model the hold as a delay, but rather uses a new type of sampled-data Lyapunov Theorem introduced in [START_REF] Seuret | A novel stability analysis of linear systems under asynchronous samplings[END_REF] and inspired by [START_REF] Peet | Positive forms and stability of linear time-delay systems[END_REF]. The conditions are enforced using sum-of-squares optimization.

ASYMPTOTIC STABILITY OF SAMPLED-DATA SYSTEMS

Main theorem

In this section we introduce a new Lyapunov theorem which applies to general nonlinear sampled-data systems. This theorem accounts for the interaction between continuous and discrete element of a sampled-data system. A version of this result was introduced in [START_REF] Seuret | A novel stability analysis of linear systems under asynchronous samplings[END_REF] and was partially inspired by the concept of spacing functions introduced in Peet et al. [2009].

Essentially, the theorem says that if there exists a Lyapunov function which has a net decrease over every sampling interval, then there exists a storage function which is continuously decreasing for all time. Consider the following system.

ẋ(t) = f (x(t), x(t k )), t ∈ [t k ,t k+1 ], k = 1, . . . , ∞.
(5) We assume global existence and continuity of solutions. Theorem 1. [START_REF] Seuret | A novel stability analysis of linear systems under asynchronous samplings[END_REF] Suppose V : R n → R + satisfies the following for µ 1 > µ 2 > 0 and p > 0

µ 1 |x| p ≤ V (x) ≤ µ 2 |x| p , for all x ∈ R n .
(6) The two following statements are equivalent.

(i) If x is a solution of Equation (5), then V (x(t k+1 )) -V (x(t k )) < 0, for all k ≥ 0. (ii) There exist continuous functions Q k : R × K → R, differ- entiable over [t k t k+1 [ which satisfy the following Q k (T k , z) = Q k (0, z),
for all k ≥ 0 and z ∈ K , (7) and such that if x is a solution of Equation ( 5), then

d dt [V (x(t)) + Q k (t -t k , x T k )] < 0, for all t ∈ [t k ,t k+1 ]. (8)
Moreover, if either of these statements is satisfied, then solutions of system ( 5) are asymptotically stable.

Proof.

Assume (ii) is satisfied. Define the storage function

W (t) = [V (x(t)) + Q k (t -t k , x T k )] . Then d dt W (t) < 0 for t ∈ [t k ,t k+1 ] and V (x(t k+1 )) -V (x(t k )) = t k+1 t k d ds V (x(s))ds = t k+1 t k d ds V (x(s))ds + Q k (T k , x T k ) -Q k (0, x T k ) = t k+1 t k d ds V (x(s))ds + t k+1 t k d ds Q k (s -t k , x T k )ds = t k+1 t k d ds (V (x(s)) + Q k (s -t k , x T k )) ds = t k+1 t k d ds W (s)ds < 0.
Hence (i) is satisfied.

Now assume (i) is satisfied. Define, for all functions z ∈ K ,

Q k (s, z) := -V (z(s)) + s T k (V (z(T k )) -V (z(0))) . Then Q k (0, z) = -V (z(0)), Q k (T k , z) = -V (z(T k )) + (V (z(T k )) -V (z(0))) = -V (z(0)). Consequently, this leads to Q k (T k , z) = Q k (0, z) which ensures that condition (7) is satisfied. Furthermore, by considering s = t -t k and z = x T k , d dt [V (x(t)) + Q k (t -t k , x T k )] = d dt V (x(t)) -V (x T k (t -t k )) + t -t k T k (V (x T k (T k )) -V (x T k (0))) = d dt V (x(t)) -V (x(t)) + t -t k T k (V (x(t k+1 )) -V (x(t k ))) = d dt t -t k T k (V (x(t k+1 )) -V (x(t k ))) = 1 T k (V (x(t k+1 )) -V (x(t k ))) < 0.
This proves the equivalence between (i) and (ii).

Now, from the discrete-time Lyapunov theorem, we have lim k→∞ x(t k ) = 0. To show lim t→∞ x(t), we note that by assumption of the existence and continuity of solutions, the solution map is continuous and thus bounded on the interval [0, T ]. Thus lim k→∞ x T k ∞ → 0 where • ∞ is the supremum norm. We conclude that lim t→∞ x(t).

A graphical depiction of the proof of Theorem 1 is shown in Figure 1. The main contribution of the theorem is the introduction of a new kind of Lyapunov functional for sampled-data systems.

There are several articles in the literature which use related approaches (see for instance [START_REF] Naghshtabrizi | Exponential stability of impulsive systems with application to uncertain sampled-data systems[END_REF], [START_REF] Fridman | A refined input delay approach to sampled-data control[END_REF]). Typically, however, these results are expressed as positivity of a Lyapunov-Krasovskii functional which is positive definite. In the above result, positivity is relaxed through the use of the spacing function Q. The following sections show how the conditions of Theorem 1 can be enforced using sum-of-squares optimization in both the synchronous and asynchronous case. This is similar to the approach taken in [START_REF] Peet | Positive forms and stability of linear time-delay systems[END_REF].

Stability under synchronous sampling

Recall the sampled-data system. ẋ

(t) = Ax(t) + BKx(t k ), for t ∈ [t k ,t k + T k ], k ≥ 0. (9)
The following theorem gives conditions for stability. The conditions of the theorem can be enforced using sum-of-squares, as will be described shortly. Theorem 2. Consider system (9) with T k = T for some given T > 0. If there exist P ∈ S n , positive definite and a polynomial matrix, of degree N, M : [0, T ] → S 2n such that P > 0, (10)

I n I n T M(0) I n I n = 0, (11)
M(T ) = 0, (12) and such that for all τ ∈ [0, T ], the following inequality holds

Ψ(τ) = 0 I n P [BK A] + K T B T A T P [0 I n ] + Ṁ(τ) + M(τ) 0 0 BK A T + 0 0 BK A T M(τ) < 0. ( 13
)
Then closed loop system is asymptotically stable for the constant sampling period T .

Proof. Consider the classical quadratic Lyapunov function for linear continuous-time systems. Define V : R n → R + as V (x) = x T Px, where P > 0 is in S. This function V satisfies condition (6) from Theorem 2. Now define the functional for all s ∈ [0, T ] and all functions z ∈ K

Q(s, z) = z(0) z(s) T M(s) z(0) z(s) .
First, from ( 12), we note that

Q(0, z) = z(0) z(0) T M(0) z(0) z(0) = z(0) T I n I n T M(0) I n I n z(0) = 0.
Furthermore,

Q(T, z) = z(0) z(T ) T M(T ) z(0) z(T ) = 0.
Therefore, we have Q(T, z) = Q(0, z) = 0 and hence condition ( 7) is satisfied.

Computing the derivative term (8), we get

d dt [V (x(t)) + Q(t -t k , x T k )] = d dt x(t) T Px(t) + x T k (0) x T k (t -t k ) T M(t -t k ) x T k (0) x T k (t -t k ) = d dt x(t) T Px(t) + x(t k ) x(t) T M(t -t k ) x(t k ) x(t) = x T (t)P ẋ(t) + ẋT (t)Px(t) + 0 ẋ(t) T M(t -t k ) x(t k ) x(t) + x(t k ) x(t) T d dt M(t -t k ) x(t k ) x(t) + x(t k ) x(t) T M(t -t k ) 0 ẋ(t)
.

Recalling that ẋ(t) = Ax(t) + BKx(t k ), we get d dt [V (x(t)) + Q(t -t k , x T k )] = x(t k ) x(t) T 0 I n T P [BK A] + K T B T A T P [0 I n ] x(t k ) x(t) + x(t k ) x(t) T 0 0 BK A T M(t -t k ) x(t k ) x(t) + x(t k ) x(t) T Ṁ(t -t k ) x(t k ) x(t) + x(t k ) x(t) T M(t -t k ) 0 0 BK A x(t k ) x(t) = x(t k ) x(t) T Ψ(t -t k ) x(t k ) x(t) , for all t ∈ [t k ,t k + T ].
Thus if there exists a solution of inequality (13), and by virtue of Theorem 1, the closed loop system is asymptotically stable for the constant sampling period T .

It is important to highlight that Theorem 2 only guarantees the stability of the solutions of system (9) for a given sampling period T . By virtue of Theorem 1, the previous theorem only ensures that: Γ T (T )PΓ(T ) -P < 0. for a given T . As it was mentioned in the introduction, the stability of sampled-data systems with a constant sampling period can be dealt by checking if the eigenvalues of the matrix Γ(T ) are included in the unit circle. This is only possible if the matrices (A, B) which characterize the system are known. Thus, in the case of uncertain systems where the matrices (A, B) lies in a polytope, it is not easy to derived the eigenvalues of the matrix Γ(T ). Noting that, in Theorem 2, the stability condition linearly depends on the matrices A and B, it is possible to extend the previous results to the case of systems with a polytopic type of uncertainties. This correspond to the main improvement of this paper.

Asynchronous sampling

The case of asynchronous sampling, where T k is unknown but bounded in some range, is clearly more realistic than the synchronous case in a networked control scenario. However, the stability conditions for this case are not significantly more complex than for the synchronous case. We simply allow the function M to vary with the sampling period, T k . Theorem 3. Consider system (5). For given 0 ≤ T 1 < T 2 < ∞, if there exist P ∈ S n , positive definite and a bi-polynomial matrix M :

[0, T 2 ] × [T 1 , T 2 ] → S 2n such that for all T ∈ [T 1 , T 2 ], P > 0, (14)
I n I n T M(0, T ) I n I n = 0, (15)
M(T, T ) = 0, ( 16) and such that for all s ∈ [0, T ], the following inequality holds

Ψ(τ, T ) = 0 I n P [BK A] + K T B T A T P [0 I n ] + d ds M(s, T ) + M(s, T ) 0 0 BK A + 0 0 BK A T M(s, T ) < 0. (17) Then if T k ∈ [T 1 , T 2 ]
for all k ≥ 0, the closed loop system is asymptotically stable.

Proof. The proof is a trivial extension of Theorem 2.

By virtue of Theorem 1, if the conditions of Theorem 3 are satisfied, then

V (x) = x T Px is decreasing across every time interval T k . That is ∀T ∈ [T 1 , T 2 ], Γ T (T )PΓ(T ) -P < 0.
Another important remark concerns the functional Q introduced in Theorem 2. In [START_REF] Fridman | A refined input delay approach to sampled-data control[END_REF] or [START_REF] Seuret | A novel stability analysis of linear systems under asynchronous samplings[END_REF], an integral term of the form

Q(t -t k , x KT ) = (t k+1 -t) t t k ẋT (s)R ẋ(s)ds,
is employed. This term has an important role in reducing the conservatism of the stability conditions. However it unavoidably leads to the use of the Jensen inequality to compute an upper bound of the derivative of V + Q + Q. This inequality unavoidably introduces conservatism in the stability criteria. In the present paper, an exact expression of the derivative of V + Q is provided since the following equality is obtained

d dt [V (x(t)) + Q(t -t k , x T k )] = x(t k ) x(t) T Ψ(t -t k , T k ) x(t k )
x(t) Then the stability criterion from Theorem 3 is less conservative then the ones from [START_REF] Fridman | A refined input delay approach to sampled-data control[END_REF] or [START_REF] Seuret | A novel stability analysis of linear systems under asynchronous samplings[END_REF].

SUM OF SQUARES AS ALGORITHMIC TOOL

General presentation of SOS

The methodology we use to implement the conditions of Theorems 2 and 3 is based on the sum-of-squares decomposition of positive polynomials. When applying this methodology we assume that all matrix functions are polynomial, can be approximated by polynomials, or there is a change of coordinates that renders them polynomial.

Denote by R[y] the ring of polynomials in y = (y 1 , . . . , y n ) with real coefficients. Denote by Σ s the cone of polynomials that admits a SOS decomposition, i.e., those p ∈ R[y] for which there exist h i ∈ R[y], i = 1, . . . , M so that

p(y) = M ∑ i=1 h 2 i (y).
If p(y) ∈ Σ s , then clearly p(y) ≥ 0 for all y. The converse is not always true, although the converse does hold for univariate matrix-valued polynomials. The advantage of SOS is that the problem of testing if p(y) ≥ 0 is known to be NP-hard, whereas testing if p(y) ∈ Σ s is equivalent to an SDP [START_REF] Parrilo | Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization[END_REF]), and hence is worst-case polynomial-time verifiable. SOS results apply to matrix-valued polynomials as well as scalars, although in this case the inequality means positive semidefinite. The SDPs related to SOS can be formulated efficiently and the solution can be retrieved using SOSTOOLS [START_REF] Prajna | Introducing SOSTOOLS: a general purpose sum of squares programming solver[END_REF]), which interfaces with semidefinite solvers such as SeDuMi [START_REF] Sturm | Using SeDuMi 1.02, a Matlab Toolbox for optimization over symmetric cones[END_REF]).

Consider now the conditions in Theorem 2 which take the form. L(s) ≤ 0, s ∈ S , (18) where L(s) ∈ R n× n and S is a semialgebraic set described by polynomial inequalities: S = {s ∈ R | g i (s) ≥ 0, i = 1, . . . , M}, where g i (s) are polynomial functions. In order to test condition (18), we can apply Positivstellensatz results such as [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] which allow us to test positivity on a semialgebraic set using SOS. Specifically, Condition (18) holds if there exists SOS polynomials P i (s, y), such that

L(s) + M ∑ i=1 g i (s)P i (s, y) = P 0 (s).
Intuitively, the above condition guarantees that when s ∈ S , we have L(s) ≤ -∑ M i=1 g i (s)p i (s, y) ≤ 0 since g i ≥ 0 and p i ≥ 0, and therefore L(s) ≤ 0 for those s.

Application to the stability theorem

In this brief subsection, we identify the functions g i 's corresponding to sets [0, T ] and [T 1 , T 2 ] used in theorems 2 and 3. The function for Theroem 2 is g 1 (s) = -(T -s)s, which represents s ∈ [0, T ] and for Theorem 3, we use

g 1 (s, T ) = -(T -s)s and g 2 (T ) = -(T 2 -T )(T -T 1 ). where g 2 represents T ∈ [T 1 , T 2 ].

EXAMPLES Consider system (1) with several matrix definitions

• Example 1 from [START_REF] Fridman | Robust sampleddata stabilization of linear systems: An input delay approach[END_REF], [START_REF] Naghshtabrizi | Exponential stability of impulsive systems with application to uncertain sampled-data systems[END_REF]:

A = 0 1 0 -0.1 , BK = 0 0 -0.375 -1.15 , • Example 2 from Fridman [2010]: A = -2 0 0 -0.9 , BK = -1 0 -1 -1 ,
• and Example 3 from [START_REF] Gu | Stability of time-delay systems[END_REF], [START_REF] Michiels | Using delays and time-varying gains to improve the static output feedback stabilizability of linear systems : a comparison[END_REF]: Tables 1 and2 summarize the results obtained in the literature and using the theorems provided in the present paper for examples 1, 2 and 3. One can see that the obtained results are less conservative then existing ones. More precisely, for each example, Theorem 3 allows guaranteeing the stability of the solutions of the sampled-data systems with the same Lyapunov matrix P.

A = 0 1 -2 0.1 , BK = 0 0 1 0 .
Another important remark deals with Example 3. This system is well known in the time-delay literature because the delay has a stabilizing effect. This means that its solutions are not stable for sufficiently small delay but become stable for sufficiently large delay. The method proposed in this article is able to take into account this phenomena and is also able to isolate several intervals of possible values for the length of the sampling interval where the system is stable. Note that Theorem 3 (with N = 5) guarantees the stability for all asynchronous sampling lying in [0.4, 1.828] or [2.520, 3.550]. However no guarantee of stability can be provided if the sampling interval switched from one interval to the other. This recalls the classical behavior of switched systems. A resulting system of a switched systems defined by two stable systems is not necessary stable. In the present situation this comes from the fact that the Lyapunov matrices obtained for each interval are different.

CONCLUSION

In this article, a novel analysis of continuous linear systems under asynchronous sampling is provided. This approach is based on the discrete-time Lyapunov Theorem applied to the continuous-time model of the sampled-data systems. Numerical results compare favorably with result in the literature. Perhaps the most important feature of the method presented in this paper is that it is expressed using the sum-of-squares framework and is thus easily extended to nonlinear systems and systems with parametric uncertainty.

Fig. 1 .

 1 Fig. 1. Illustration of the proof of Theorem 1

Table 1 .

 1 Maximum allowable sampling period T 2 for examples 1, 2, with T 1 = 0.

	Theorems		T 2 for Ex.1 T 2 for Ex.2
	Fridman et al. [2004]	0.869	0.99
	Naghshtabrizi et al. [2008] 1.113	1.99
	Fridman [2010]		1.695	2.03
	Liu and Fridman [2009]	1.695	2.53
	Seuret [2011]		1.723	2.62
	Th.2 N = 1		0.702	2.319
	Th.2 N = 3		1.729	3.219
	Th.2 N = 5		1.729	3.269
	Th.3 N = 1		0.701	2.310
	Th.3 N = 3		1.729	3.218
	Th.3 N = 5		1.729	3.269
	Theorems for Ex.3
	Seuret [2011]	[0.201, 1.623]
	Th.2 N = 1	∅
	Th.2 N = 3	[0.2007, 2.016] [2.606, 3.055]
	Th.2 N = 5	[0.2007, 2.020] [2.470, 3.694]
	Seuret [2011]	[0.400, 1.251]
	Th.3 N = 1	∅
	Th.3 N = 3	[0.4, 1.820] or [2.680, 3.005]
	Th.3 N = 5	[0.4, 1.828] or [2.520, 3.550]

Table 2 .

 2 Interval of allowable asynchronous samplings of the form [T 1 , T 2 ] for example 3.

This research is supported by FeedNetBack project, FP7-ICT-2007-2: http://www.feednetback.eu/. This paper was not presented at any IFAC meeting.


Guillaume Mandil
email: guillaume.mandil@usherbrooke.ca

Philippe Serré

Mireille Moinet

Alain Desrochers

Geometrical tools for the description and control of functional specifications at the conceptual design phase

Keywords: Exigence géométrique, Cycle de vie, Tenseur métrique, Matrices de Gram, Géométrie non Cartésiennes Geometrical requirement, Life Cycle, Metric tensor, Gram matrices, coordinate free geometry

Cet article présente un modèle géométrique à base de points et de segments de droites utilisé pour représenter des mécanismes dans les phases de préconception. Ce modèle est traduit sous forme mathématique par une matrice d'incidence qui représente la topologie et une matrice de Gram qui représente les informations métriques de l'objet. Il est ensuite indiqué comment assembler deux objets représentés par ce modèle. Enfin, un exemple permet de montrer l'intérêt de ce modèle pour réaliser le suivi d'une exigence géométrique au cours du cycle de vie du produit.

Introduction

During the design process of a mechanical product, functional requirements are translated into geometrical requirements. For instance the functional requirement saying that: "part A must follow a given face of part B along the movement" can be translated as: "The clearance between the two surfaces of part A and B must remain inferior to x mm". This translation could also be applied to the definition of kinematic joints. The technique developed by M'Henni [M'henni, 2010] allows the accurate calculation of the geometrical parameters of the joint. Moreover, a mechanical product is subjected to dimensional variations along its life cycle due to mechanical strains. These variations affect the dimensions of parts that in turn influence the value of the geometrical requirements. Generally there exist several useful values of a requirement depending on the use--case or the user. For instance, the manufacturer is interested in the value of the geometrical requirements at the assembly stage of the life--cycle to perform the assembly of the parts and components. From another point of view, the final user is interested in the values of the same requirement but under operating conditions.

As a matter of fact, considering the designer's point of view, it becomes necessary to link (or to compare) the values of a geometrical requirement at several stages of the product life--cycle. In particular, for the designer, several problems appear: "Does the chosen dimension for manufacturing (or assembly) allow the geometrical requirements under operating conditions to be met?" or "Which dimensions must be specified on the drawing to ensure a given value of the geometrical requirement in operation?"

In order to compare the geometric configuration of an object (or product) at two distinct stages of its life--cycle, this paper proposes a technique to combine the two mathematical representations of the same object under different use--cases in a unique and common representation.

Authors noticed that there exist various tools to manage the detailed design of a product. For instance the Computer Aided Design (CAD) tools help designers define the detailed and nominal 3D geometry of a product. From this nominal geometrical model it becomes possible to use a Finite Element Analysis (FEA) to calculate the dimension variations due to mechanical strains [START_REF] Pierre | Integration of multiple physical behaviours into a geometric tolerancing approach[END_REF] and to rebuild a geometrical model [START_REF] Louhichi | Intégration CAO/Calcul par reconstruction du modèle CAO à partir des résultats éléments finis[END_REF]. Form the nominal model, there also exists several methods [START_REF] Ghie | Modèle unifié jacobien--torseur pour le tolérancement assisté par ordinateur[END_REF], [START_REF] Anselmetti | Generation of functional tolerancing based on positioning features[END_REF], to deal with the tolerancing problem. This addresses the issue of the real versus nominal dimensions of the parts. These methods help the mechanical designer in the specification of tolerances zones and the management and control of dimensional uncertainties due to manufacturing.

On the other hand, there are few tools available for geometry management at the early design phases. Consequently this work proposes a geometrical model dedicated to preliminary design that allows the calculation of the evolution of geometrical parameters or requirements along the product life--cycle. In consequence, this work includes the proposition of a simplified coordinate free representation to represent objects. Coordinate free approaches allow the direct specification of intrinsic properties of geometrical objects that avoid the artificial dependence with a reference frame induced by the coordinates.

The first part of this paper will detail the topological and vectorial model used for representing the object. Then the second part will detail how to associate two topological models. Finally, the third part of the paper will explicit the association of two vectorial models.

Notations

This paper will use the following conventions:

Matrices will be noted with capital bold letters: M ; Vectors will be noted with bold letters: u ; Scalar number will be noted with italic letters: x. Scalar product of vectors u and v is noted <u,v> ⊗ represent the product of two matrices.

Models

The model used to represent objects is based on simplified geometries that describe a skeleton of the object. It includes points and line segments (or pairs of points). From the authors point of view, this representation is sufficient for the description of geometrical objects during the preliminary design phase. The example of an object that can be represented using this model is presented in figure 1. In this example, points are noted P1, P2, P3 and P4. Segment lines are noted Sl1, Sl2, Sl3, Sl4, Sl5 and Sl6.

In addition to this graphical and geometrical representation, the model is composed of two matrices. The first one is used to represent the topology of the object while the second gives the metric to measure the length and orientation of the elements.

Topological Model

The topological model contains the points and the line segments used to describe the object. It also describes how points and segments are connected. This information is represented in a topological graph constituted of oriented simplexes. The points {P1, P2, P3, P4} of figure 1 are represented in the topological graph (figure 2) by the vertices {V1, V2, V3, V4}. In the same way, the line segments { Sl1, Sl2, Sl3, Sl4, Sl5, Sl6} are represented by the arcs {E1, E2, E3, E4, E5, E6}. Consequently, the topological model must contain the list of the vertices and arcs that describes the object. This description is completed by the information on the incidence of vertices on arcs. This information indicates from which vertex the arc starts and at which vertex it ends. The topological graph associated to the object drawn in figure 1 is represented in figure 2.

Geometrical model.

The geometrical model is one realization of the topological oriented graph. To perform this realization a vector is associated to each arc. The vector will take the same orientation as the arc.

This geometrical or vectorial model provides the lengths of all the segments and their relative orientation. It is coordinate free in the sense that the mathematical representation used to store this information does not depend on any coordinate system. In concrete terms, a given geometry described in two different coordinate systems would have a common, unique description if a coordinate free system were used. From there it becomes possible for the designer to describe the intrinsic geometric properties of an object using a compact mathematical model without paying attention to the coordinate system in which the object is defined.

During the preliminary design phase, the geometrical parameters are subjected to a lot of changes. Consequently, a tool for the comparison of two representations of an object at this stage of the design process should be based on a mathematical model that allows the efficient solving of geometric constraints in order to quickly rebuilt an object as some parameters are updated. From there, the choice of using Gram Matrices as vectorial model has been motivated by the existence of generic

E4 E1 E2 E3 E5 E6 V3 V1 V2 V4
constraints specification techniques (as in [START_REF] Serré | Non--cartesian modelling for analysis of the consistency of a geometric specification for conceptual design[END_REF]) and solvers (cf. in [START_REF] Moinet | A new approach to transform a constrained geometric object[END_REF]).

For the example of figure 1 the set of vectors Su={u 1 , u 2 , u 3 , u 4 , u 5 , u 6 } is associated to the set of arcs {E1, E2, E3, E4, E5, E6} in the topological graph (figure 2).

Mathematical tools

Tools for the topological model

Topological informations are stored in a matrix that contains vertices in its columns and arcs in its rows. For each line of the matrix (representing an arc) a --1 indicates from which vertex the arc starts, a +1 indicates at which vertex the arc ends, all other terms of the line being equal to zero. For example the matrix relative to figure 2 is shown in table 1.

C V1 V2 V3 V4 E1 --1 1 0 0 E2 0 --1 1 0 E3 0 0 --1 1 E4 --1 0 0 1 E5 --1 0 1 0 E6 0 --1 0 1
Table 1: Connection matrix C relative to the example object of figure 1.

Tools for the vectorial model

The following definition of a Gram matrix is found in [START_REF] Gentle | Matrix Algebra: Theory, Computations, and Applications in Statistics[END_REF] : "the Gram matrix G (or Gramian matrix or Gramian) of a set of vectors {u 1 , u 2 , …, u k } in an inner product space is the Hermitian matrix of inner products, whose entries are given by equation [1]". G lm represents the term of the row l and column m of the G matrix. In this paper the names of all Gram matrices start with a capital "G". Gram matrices are positive semidefinite.

1 Gpq = <up,uq> [1]
Remark: a metric tensor is a particular case of a Gram matrix which has its rank equal to its dimension. For example, in the 3D Euclidian space, a 3 by 3 Gram matrix which has a nonzero determinant (which is equivalent to being constituted of 3 independent vectors) is called a metric tensor. In this paper, the names of all the metric tensors start with a capital "M".

For the example object of figure 1 the corresponding Gram matrix is shown in table 2 From the Gram matrices it is immediately possible to obtain the scalar product between two vectors. From there, it is easy to deduce the norm of a vector with relation [2] and the angle between two vectors with relations [2] and[3].

2 ||up|| = ||up|| = [2] 3 cos(up, uq) = <up, uq> / (||up|| ||uq||) ) cos(up, uq) = Gpq / ( ) [3]

General discussion

Thanks to the connection matrix, the topological model describes the points, line segments, and the way they are connected. The vectorial model provides the lengths and the relative orientation of the line segments using the Gram matrix. These two models contain all the necessary information for the description of an object. Consequently, the specification of the list of points and line segments, along with the connection matrix and the Gram matrix is sufficient to describe the skeleton of the object. This model can either describe an elementary skeleton object or the association of two objects.

Association of objects

As mentioned in the introduction (section 1), the aim of this work is the association of the two mathematical representations of the same object (at two stages of its life--cycle under different use--cases) in a unique and common representation. To perform such an association it is necessary to aggregate the topological connection matrices, and to associate the vectorial Gram matrix as shown in figure 3.

For the two representations, it is crucial that the result of the association remains describable with the connection and Gram matrices. To ensure this condition, authors use a declarative approach. One declaration is available for each association. The topology association is declared with the coincidence of two vertices. The vectorial model association is declared by the coincidence of two orthonormal reference frames. These reference frames are constituted by primary, secondary and tertiary datum elements from tolerancing. Hence for tolerancing applications no other constraints are needed. However, it is being envisioned to add other constraints for the declaration of the association of two objects to extend this approach to other fields of product design.

In any case, this paper considers that a complete representation of the elementary objects to be associated already exists, thanks to a connection matrix and a Gram matrix. For this application it is assumed that a model of the object exists. This model is instanced at two distinct stages "α" and "β" of the life--cycle. The reader is advised that the letters α and β always refer to the life cycle stages in all the following variable names. For the stage "α" of the life cycle two matrices are available : Gα and Cα. The elements of the Gα Gram matrix are scalar products between vectors from the set Suα = {uα 1 , uα 2 , …, uα q }. The Cα connection matrix indicates the relations between the arcs {Eα1, Eα2, … , Eαq} and the vertices {Vα1, Vα2, … , Vαs}. The index q is used to count arcs and vectors and the index s is used to count vertices. For the stage "β" of the life cycle, the matrix Gβ represents the set Suβ = {uβ 1 , uβ 2 , …, uβ q } and the matrix Cβ indicates the connection between the arcs {Eβ1, Eβ2, … , Eβq} and the vertices {Vβ1, Vβ2, … , Vβs}.

In our case, there are no changes in the topology of the object; consequently Cα = Cβ. Moreover, at the stage "α" of the life cycle, the Cα and Gα matrices can be obtained with the technique developed by Moinet [START_REF] Moinet | Descriptions non cartésiennes et résolution de problèmes géométriques sous contraintes[END_REF]. The Cβ and Gβ matrices are calculated using the same approach.

Calculation of the global connection matrix

The calculation of the global connection matrix C (see figure 3) is based on the declaration of the coincidence of two vertices. This calculation supposes that the Cα and Cβ matrices relatives to each life--cycle stage are available. The generic term of Cα is noted Cα q,s and the generic term of Cβ is noted Cβ q,s . Without loss of generality, we also assume that the user has declared the coincidence of the first vertices of each set Vα1 and Vβ1. If the user declares another constraint (i.e. Vα2 coincident with Vβ4), it is possible to meet the previous hypothesis by renaming vertices and rearranging the corresponding C matrices.

At the first stage of this procedure, the Cα and Cβ matrices are associated in a global C matrix presented in table 3. Initially, the vertices of configuration "β" have no relation with the arcs of configuration "α" ; consequently the up--right terms of the global C matrix are all set to zero. In the same way, the bottom--left terms are also set to zero because vertices of configuration "α" have no incidence on the arcs of configuration "β".

Cα Gα Cβ Gβ

In the second stage, a new vertex noted Vγ is created and added in the last column of C. Accordingly, the vertices Vα1 and Vβ1 are removed from the global connection matrix C. The incidence of vertex Vγ on all the arcs is expressed in the last column of table 3. The global

C matrix obtained is presented in table 3. Vα2 … Vαs Vβ2 … Vβs Vγ Eα1 Cα 1,2 … Cα 1,s 0 … 0 Cα 1,1 Eα2 Cα 2,2 … Cα 2,s 0 … 0 Cα 2,1 … … … … … … Eαq Cα q,2 … Cα q,s 0 … 0 Cα q,1 Eβ1 0 … 0 Cβ 1,2 … Cβ 1,s Cβ 1,1 Eβ2 0 … 0 Cβ 2,2 … Cβ 2,s Cβ 2,1 … … … … … … C= Eβq 0 … 0 Cβ q,2 … Cβ q,s Cβ q,1

Calculation of the global Gram matrix

This calculation is based on the declaration of coincidence of two orthonormal reference frames. In order to declare this coincidence, the user declares an ordered list of 3 independent vectors for each of the two objects (or configurations) to be assembled. These lists are noted {dα 1 ,dα 2 ,dα 3 } and {dβ 1 ,dβ 2 ,dβ 3 }. This declaration ensures that after the association; vectors dα 1 and dβ 1 will first be collinear; secondly vectors dα 1 ,dα 2 and dβ 1 ,dβ 2 will be coplanar; and finally the axis systems {dα 1 ,dα 2 ,dα 3 } and {dβ 1 ,dβ 2 ,dβ 3 } will have the same orientation. This kind of declaration fits the tolerancing problem. For tolerancing purposes, the relative position of two parts or components is generally specified using some primary, secondary, and tertiary datum elements defined by the standards ISO 286--X. From these datum elements, it becomes possible to deduce the relevant vectors and their order in the declared list.

The global matrix is noted G and presented in table 4.

Gα Gαβ G= Gαβ

T Gβ Table 4: Global Gram matrix of the two configurations "α" and "β".

Principle

In order to calculate the relative orientation between vectors from these two sets Suα and Suβ (at stages "α" and "β"), the generic term of the Gαβ (see table 4) matrix expressed in equation [4] has to be calculated. Note that Gαβ is not a Gram matrix because it is not symmetrical. As the approach is coordinate free, the coordinates of the vectors included in the sets are not directly available.

Consequently, the direct application of equation [4] is impossible. The following paragraphs present a technique to perform this calculation.

4

Gαβp,s = <uαp,uβs>

[4]

Authors propose to use matrix factorization techniques to express any Gα and Gβ as the product specified in equation [5]. It is supposed that the size of Gα and Gβ are q (the number of line segments) and their rank is 3 because the problem is described in 3D Euclidian space. The calculation and the size of the Fα matrix will be detailed later on.

5 Gα = Fα T ⊗ Fα and Gβ = Fβ T ⊗ Fβ [5]

Calculation of the Gαβ Matrix

Equation [5] can be modified with the addition of the identity matrix Id as presented in equation [6] 6

Gα = Fα T ⊗ Id ⊗ Fα and Gβ = Fβ T ⊗ Id ⊗ Fβ [6]
In equation [6], Id matrices can be viewed as the metric tensors of two ortho-normal reference frames {e 1 ,e 2 ,e 3 } (3 vectors in 3D Euclidian space). From there Fα and Fβ can be viewed as the transformation matrix defined in [START_REF] Anselmetti | Generation of functional tolerancing based on positioning features[END_REF]. The size of Fα and Fβ is 3 by q. As Gα and Gβ are Gram matrices that are positive semidefinite, the terms of Fα and Fβ remain real numbers. The application of relation [START_REF] Anselmetti | Generation of functional tolerancing based on positioning features[END_REF] on the terms of relation [4] gives the expression [8] that allows the calculation of Gαβ. In relation [8] δ n,q represents the Kronecker symbol. The relation [9] gives the matrix expression of Gαβ.

8 Gαβp,s = <uαp,uβs> = € n, q ∑ <Fαn,p en , Fβq,s eq> = € n, q ∑ Fαn,p Fβq,s <en,eq> = € n, q ∑ Fαn,p Fβq,s δn,q Gαβp,s = € n ∑ Fαn,p Fβn,s [8] 9 Gαβ = Fα T ⊗ Fβ [9]
From there it becomes possible to calculate the global G matrix with the relations [5] and [9] and to associate these results as presented in table 5.

Mα = Lα T ⊗ Lα [10]
The following paragraphs will present the two concepts of covariant and contravariant coordinates used in the conversion from metric tensor to Gram matrix [START_REF] Lichnerowicz | Algèbre et analyse linéaires[END_REF]. The covariant coordinates noted uα k of a vector uα with respect to the reference frame {dα 1 ,dα 2 ,dα 3 } are the scalar products of equation [11]. These coordinates are those that are commonly used in engineering and science. One can notice that Gram matrices are constituted of covariant coordinates.

11 uαk = < uα , dαk > [11]
Moreover the covariant coordinates lead to the definition of the metric tensor Mα for the reference frame {dα 1 , dα 2 , dα 3 }. The term Mα lm of the row l and column m of Mα is defined by [12]. By construction Mα is symmetrical. Mα is invertible and its inverse matrix is noted Mα --1 and remains symmetrical.

12

Mαl,m = < dαl , dαm > [12]
The contravariant coordinates define the uα k coefficients used to obtain a vector uα as a unique linear combination of the vectors {dα 1 , dα 2 , dα 3 } defining the reference frame [13].

13 uα = € p ∑ uα p dαp [13]
The conversion from covariant to contravariant coordinates is achieved through a combination of relations [11], [12], [13]. From there, it is easy to deduce equations [14] and [15].

14 uαm = € p ∑ uα p Mαm,p [14] 15 uα p = € m ∑ uαm Mα -1 mp [15]

Factorization of Gram matrices

The calculation of < vα,wα >, that leads to the calculation of any term of the Gram matrix Gα, is given by equation [16]. The metric tensor Mα of the reference frame {dα 1 , dα 2 , dα 3 } is given with two vectors vα and wα from the set Suα. The contravariant coordinates of these vectors are defined with respect to relation [13]. The covariant coordinates are directly extracted from Gα. They are stored in the Pα matrix that contains all the columns of Gα and only the 3 rows corresponding to {dα 1 , dα 2 , dα 3 }. The size of Pα is 3 by q. The inverse matrix of the Mα metric tensor is to be computed. From relations [17] it is possible to deduce expression [18] of Gα.

Gα = Pα T ⊗ Mα -1 ⊗ Mα ⊗ Mα -1 ⊗ Pα = Pα T ⊗ Mα -1 ⊗ (Lα T ⊗ Lα) ⊗ Mα -1 ⊗ Pα Gα = (Lα ⊗ Mα -1 ⊗ Pα) T ⊗ (Lα ⊗ Mα -1 ⊗ Pα) [19]
The identification of the terms of relation [19] and relation [5] leads to the definition of the factorization of the Gram matrices that are given by relation [20].

20 Fα = Lα ⊗ Mα -1 ⊗ Pα [20]
21

Fβ = Lβ ⊗ Mβ -1 ⊗ Pβ [21]
The Gβ matrix can be factorized using the same approach and Fβ is given by relation [21]. From there the global matrix G representing the assembly of the two configurations can be calculated such as described in table 5. The G Gram matrix allows the mapping of the evolution of the geometrical parameters. This will be briefly illustrated on the case study presented in the following section.

Case Study

This section presents the application of the method on a simple 3D case. The proposed object for this case study is composed of three articulated bars arranged as a tetrahedron on a wall, as presented in figure 4. This case is comprised of 4 points {A, B, C, D} and 6 line segments {AB, AC, BC, SA, SB, SC}. This object is supposed to have a topological and geometrical (or vectorial) representation at two stages "α" and "β" of its life--cycle. A α designate point A at stage "α". A β is used for the stage "β". Here it is assumed that the topology remains unchanged between the two stages of the life--cycle. This means that the topological matrices for the representation of the object are the same (Cα = Cβ).

Figure 4: Objects for the case study

The object of the case study has for topological model the Cα (=Cβ) connection matrix presented in table 6.

Cα A α B α C α S α Cβ A β B β C β S β A α B α --1 1 0 0 A β B β --1 1 0 0 B α C α 0 --1 1 0 B β C β 0 --1 1 0 A α C α --1 0 1 0 A β C β --1 0 1 0 S α A α 1 0 0 --1 S β A β 1 0 0 --1 S α B α 0 1 0 --1 S β B β 0 1 0 --1 S α C α 0 0 1 --1 S β C β 0 0 1 --1

Table 6: Connection matrices for the case study

Moreover, from the works of Serré [START_REF] Serré | Cohérence de la spécification d'un objet de l'espace euclidien à n dimensions[END_REF] and Moinet [START_REF] Moinet | Descriptions non cartésiennes et résolution de problèmes géométriques sous contraintes[END_REF], two Gram matrices are calculated with the specifications presented in table 7. The two Gram matrices are presented in table 8 andtable 9. Stage "α" and stage "β" are two different states of the product life cycle. Stage "α" is for nominal values of temperature and loads. Stage "β" is when temperature and loads have changed. a α b α is the vector associated to line segment AB at stage "α". a β b β is the vector associated to line segment AB at stage "β".

Length

B β C β S β B α C α S α
At stage "α" of the life cycle At stage "β" of the life cycle In order to associate these two configurations, the following declarations are made by the user. First, he declares that vertex A α and vertex A β are coincident. Second, he also declares the following ordered lists of independent vectors for the geometrical association: {a α b α ,a α c α ,s α a α } and {a β b β ,a β c β ,s β a β }.

A α A β Gα a α b α b α c α a α c α s α a α s α b α s α c α a α b α 1 0 0 -1 -1 0 b α c α 0 1 0 1 0 -1 a α c α 0 0 1 0 1 1 s α a α -1 1 0 2 1 -1 s α b α -1 0 1 1 2 1 s α c α 0 -1 1 -1 1 2

Topological association

In order to associate the Cα and Cβ connection matrices (see table 6) using the coincidence of vertices A α and A β , it is necessary to create a third vertex termed A γ . The application of the procedure of section 4.1 finally gives the global connection matrix C presented in table 10.

Vectorial association

In accordance with the previous section the vertices A α and A β have been replaced by vertex A γ . Consequently, the ordered lists have been changed in the same way. To perform the association of Gram matrices, the methodology of section 4.2 is applied with the declaration of the following ordered lists: {a γ b α ,a γ c α ,s α a γ } and {a γ b β ,a γ c β ,s β a γ }. From these lists the metric tensors Mα and Mβ presented in table 11 are extracted.

Mα a

γ b α a γ c α s α a γ Mβ a γ b β a γ c β s β a γ a γ b α 1 0 -1 a γ b β 1.2539 0.

Pα

a γ b α b α c α a γ c α s α a γ s α b α s α c α a γ b α 1 0 0 -1 -1 0 a γ c α 0 0 1 0 1 1 je -1 1 0 2 1 -1
Table 13: Covariant coordinates of vectors for configuration "α" From there the global G matrix of the system is computable using Table 5. The result of this computation is presented in table 17. s β a γ -1.1493 1.0809 -0.1360 2.2302 1.0133 -1.2169 -1.2869 1.22080 -0.3768 2.5077 0.9101 -1.5976 s β b β -0.9367 0 1.2239 0.9367 2.1606 1.2239 -1.0489 -0.1388 1.3265 0.9101 2.3754 1.4653 s β c β 0.2126 -1.0809 1.3599 -1.2935 1.1474 2.4408 0.23800 -1.3596 1.7033 -1.5976 1.4653 3.0629

Pβ a γ b β b β c β a γ c β s β a γ s β b β s β c β a γ b β 1.
1 0 0 -1 -1 0 0 0 1 0 1 1 0 1 0 1 0 -1
G a γ b α b α c α a γ c α s α a γ s α b α s α c α a γ b β b β c β a γ c β s β a γ s β b β s β c β a γ b α 1 0 0 -1 -1 0
Table 17: Global Gram matrix for the case study

Example of the mapping of the evolution of a geometrical parameter.

In this section, the interest of the global representation of the association of two objects (or configurations) for the mapping of the evolution of a geometrical parameter is briefly shown. To this end, it is proposed, first to measure the angle between the vectors s α a γ and s β a γ and second to calculate the length of the vector s α s β .

The application of relation [3] directly gives the value of cos(s α a γ ,s β a γ ) = G 4,10 / ( )= 0.995836 which correspond to an angle of 0.091287 radian.

From matrix C (see table 10),a possible path to go from vertex S α to vertex S β is deduced as going through vertex A γ . Consequently the scalar product <s α s β ,s α s β > is expressed by relation [22].

22

<s α s β ,s α s β > = <s α a γ ,s α a γ > + 2 <s α a γ ,a γ s β > + <a γ s β ,a γ s β > <s α s β ,s α s β > = <s α a γ , s α a γ > -2 < s α a γ ,s β a γ > + <s β a γ ,s β a γ > <s α s β ,s α s β > = G4,4 -2 G4,10 + G10,10

[22]

The combination of relations [2] and [22] allows the calculation of ||s α s β || from the elements available in the global Gram matrix G presented in table 17. After calculation, the result obtained is ||s α s β || = 0.217565 length unit.

Conclusion and perspectives

This paper has first presented a generic model for representing objects using points and line segments exclusively. That description proved to be suitable for the representation of the skeleton of a mechanical product at the early stages of the design process. Secondly a means for representing objects, thanks to two matrices, was introduced. A connection matrix was used to indicate how points and line segments were connected and a Gram matrix is used to provide the user with lengths and orientation information about the line segments. In the third part, the paper showed how to perform an assembly with two objects represented with these two matrices. Finally, the interest of this model for the mapping of the evolution of a geometrical parameter has been exhibited on a case study.

In terms of future work, the authors propose first to consider the addition of surface elements such as triangles to enhance the possibilities for modelling complex objects. Secondly, it is also envisaged to implement additional constraints, such as topological coincidence between two lines segments, for the declaration of the assembly of the two objects.

Figure 1 :

 1 Figure 1: Example of object represented by the model.

Figure 2 :

 2 Figure 2: Topological graph associated to the example object.

Figure 3 :

 3 Figure 3: Association of two representations at phase "α" and "β" of the life-cycle.

  Association of object α and object βObject β

∑

  <vα r dαr, wα p dαp> = € r , p ∑ vα r <dαr,dαp> wα p < vα,wα > = € r , p ∑ vα r Mαr,p wα p [16]Using relation[15] it is possible to express equation[16] in its covariant form such as presented in equation [17] that leads to the calculation of the terms of the Gα gram matrix (defined by equation[4]). Reminding that Mα -), and δ m,p represents the Kronecker symbol, we have:

Fα

b

  β c β -0.0295 1.0809 -0.1360 1.1104 -0.1065 -1.2169 -0.0331 1.1877 -0.1719 1.2208 -0.1388 -1.3596 a γ c β 0.1830 0 1.2239 -0.1830 1.0409 1.2239 0.2050 -0.1719 1.5315 -0.3768 1.3265 1.7033

Table 3 :

 3 Global connection matrix C

Table 7 :

 7 Length specification

		at stage	Length at stage
	AB	1.00000	"α"	1.1198	"β"
	BC	1.00000		1.0898
	AC	1.00000		1.2375
	SA	1.41421		1.5836
	SB	1.41421		1.5412
	SC	1.41421		1.7501

Table 8 :

 8 Gram matrix for the object at stage "α".

	Gβ	a β b

β b β c β a β c β s β a β s β b β s β c β a β b β

	1.2539 -0.0331 0.2050 -1.2869 -1.0489 0.2380
	b β c β -0.0331 1.1877 -0.1719 1.2208 -0.1388 -1.3596
	a β c β 0.2050 -0.1719 1.5315 -0.3768 1.3265	1.7033
	s β a β -1.2869 1.22080 -0.3768 2.5077	0.9101 -1.5976
	s β b β -1.0489 -0.1388 1.3265	0.9101	2.3754	1.4653
	s β c β 0.23800 -1.3596 1.7033 -1.5976 1.4653	3.0629

Table 9 :

 9 Gram matrix for the object at stage "β"

Table 11 :

 11 Metric tensors for the application caseThe application of the Cholesky factorization technique on the Mα and Mβ metric tensors gives the Lα and Lβ matrices presented in table 12.

	2050 -1.2869

Table 12 :

 12 Lα and Lβ factorized matricesIn parallel, the covariant coordinates of the vectors are extracted from Gα and Gβ. The Pα and Pβ matrices are presented in table13 and table 14.

Table 14 :

 14 Covariant coordinates of vectors for configuration "β" With the elements presented in table 11, table 12, table 13 and table 14 it now becomes possible to calculate the Fα and Fβ matrices using relations [20] and [21]. The expression of Fα and Fβ are given in table 15 and table 16.

	2539 -0.0331 0.2050 -1.2869 -1.0489 0.2380
	a γ b β 0.2050 -0.1719 1.5315 -0.3768 1.3265	1.7033
	s β a γ -1.2869 1.2208 -0.3768 2.5077	0.9101 -1.5976

Table 15 :

 15 Factorization of the Gα Gram matrix

	Fβ
	1.1198 -0.0295 0.1830 -1.1493 -0.9367 0.2126
	0	-0.1360 1.2239 -0.1360 1.2239 1.3599
	0	1.0809	0	1.0809	0	-1.0809

Table 16 :

 16 Factorization of the Gβ Gram matrix

G

u 1 u 2 u 3 u 4 u 5 u 6 u

Table 2: Gram matrix relative to the example object.

The previous paragraphs have shown that factorization is suitable for the calculation of the global Gram matrix. The following subsections will detail the technique used by the authors to factorize Gram matrices. It will be illustrated by the calculation of Fα from the Gα Gram matrix. The same factorization technique is to be applied for the calculation of Fβ from Gβ.

Currently, authors have looked into the use of the Cholesky factorization. This technique appears to be appropriate because it builds an orthonormal reference frame from an ordered list of 3 independent vectors. However, the Cholesky factorization has a limitation. This method is only available for square matrices that have a non--zero determinant. This means that the matrix to be factorized has to be a metric tensor and so its size has to be equal to the dimension of the Euclidian space. In the general case, Gram matrices sizes are bigger than the dimension of the Euclidian space. Consequently, for the application of the Cholesky factorization, it first becomes necessary to be able to obtain one metric tensor from the Gram matrix and secondly to rebuilt the original Gram matrix from the metric tensor.

Mathematical tools

The first conversion is obvious: it is simply necessary to choose the subset of independent vectors as declared by the user and extract the corresponding columns and rows of the Gram matrix to obtain the resulting metric tensor. For the "α" configuration, the metric tensor Mα is extracted from Gα. Once the Mβ metric tensor is obtained, it is factorized with the Cholesky technique [START_REF] Gentle | Matrix Algebra: Theory, Computations, and Applications in Statistics[END_REF] as presented in equation [10].

Conclusion.

The substitution of relation [10] in relation [18] gives the expression [19] for Gα.

Reminding that Mα

--1 is symmetrical (Mα --1 = (Mα --1 ) T ):

Table 10: Global connection matrix for the case study