Christiane Kamdem Kengne

Noha Ibrahim

Marie-Christine Rousset

Maurice Tchuente
email: maurice.tchuente@ens-lyon.fr

Distance-based Trace Diagnosis for Multimedia Applications: Help me TED!

Keywords: Execution traces, Diagnosis, Audio/Video decoding, Multimedia applications

Execution traces have become essential resources that many developers analyze to debug their applications. Ideally, a developer wants to quickly detect whether there are anomalies on his application or not. However, in practice, size of multimedia applications trace can reach gigabytes, which makes their exploitation very complex. Usually, developers use visualization tools before stating a hypothesis. In this paper, we argue that this solution is not satisfactory and propose to automatically provide a diagnosis by comparing execution traces. We use distance based models and conduct a user case to show how TED, our automatic trace diagnosis tool, provides semantic added-value information to the developer. Performance evaluation over real world data shows that our approach is scalable.

I. INTRODUCTION

With the proliferation of embedded systems (from home boxes to tablets and smartphones) providing an everywhere access to multimedia contents, the development of multimedia applications is an area of high competition in which every second lost by a developer to debug the application amounts a financial loss for companies. The analysis of execution traces, that are sequences of timestamped events, is at the core of the optimization and debugging of applications. When the developer has a reference trace (which can be produced by a simulator), a technique for detecting possible anomalies within an execution trace is to compare it with the reference trace using a suitable distance [START_REF] Chandola | Anomaly detection for discrete sequences: A survey[END_REF]. However, although there is an abundant literature about distances on sequences ( [START_REF] Mörchen | Time series knowledge mining[END_REF]- [START_REF] Bergroth | A survey of longest common subsequence algorithms[END_REF]), very few distances take into account the temporal aspect that is crucial in execution traces. More generally, designing an appropriate distance for a meaningful comparison between multimedia execution traces is a difficult task. Indeed, it requires to capture and combine within a single numerical function, several aspects that are specific to multimedia execution traces. Whatever the quality of a distance for suggesting the existence of a bug in an execution trace, based on its numerical comparison with a reference trace, the results of the distance calculation are inherently difficult to interpret by human developers, in particular for finding the actual cause of the bug.

In this paper, we propose to replace a black-box approach encapsulated in a single complex distance by a glass-box approach based on a fine-grained analysis of problems that are likely to occur in multimedia applications. The idea is that anomalies in multimedia applications usually have visible effects such as desynchronization of sound with the picture or subtitles, the interruption of a video streaming or the loss of some frames (a frame being an image rendered during a known time interval). We make the following contributions:

1) We have identified a family of anomalies likely to occur in multimedia applications and that are visually perceptible when a user is watching a video. 2) For each type of anomaly, we have designed a specific distance which measures appropriately the amplitude of the corresponding anomaly. 3) Based on these distances, we have designed a diagnosis tool able to detect degraded execution traces and to identify the causes of such a degraded behaviour. The rest of the paper is organized as follows: Section II provides some background and states the problem that we consider in this paper. In Section III we present the general approach that we propose to solve this problem. In Section IV, we describe our TED tool and illustrate it on a use case. Section V summarizes experiments conducted using TED. Finally, Section VI briefly surveys related work, and concludes with some perspectives.

II. BACKGROUND AND PROBLEM STATEMENT

In this section, we explain how execution traces are obtained and described as timestamped sequences. We also introduce three well-known types of anomalies occurring in video streaming. Finally, we state the trace diagnosis problem.

A. Execution Traces Generation and Description

Embedded systems directly integrate hardware tracing support to collect events generated by applications or perform a post-mortem analysis of their execution. These techniques minimize intrusiveness, i.e tracing an application has a minimal impact on its behaviour, allowing complex interactions to be shown in real-time applications such as video decoding. In some cases, software tracing solutions are provided by the operating system. For instance, on an ST40 core [5], applications run on a Linux distribution for STMicroelectronics products. This operating system provides a tracing tool based on KProbes [START_REF] Krishnakumar | Kernel korner: kprobes-a kernel debugger[END_REF], which registers system and application events: interrupts, context switches, function calls, system calls, etc. In general there are toolkits for managing multimedia data, from source acquisition to treatment and diffusion. The source can be a network stream, a webcam or a file on the hard disk. The treatment concerns for instance audio/video effects and encoding. The architecture of such toolkits are generally modular, pipeline-based and composed of a gstreamer [7] core and different plugins. The pipeline connects a number of elements and each element is provided by a plug-in. To play a stream containing both video and audio data for instance, one thread is used for each output. In this case, the pipeline has essential components as audio decoder, video decoder, demuxer or filesrc [7].

Based on our previous work [START_REF] Kengne | Efficiently rewriting large multimedia application execution traces with few event sequences[END_REF], we formalize the execution traces that are generated as sequences of timestamped events as depicted in Fig. 1, where, for instance, 1965720232 is a timestamp of the event f f mpeg : gst f f mpegdec c hain : Received.

Fig. 1. An execution trace

More formally, let Σ be a set of events. A timestamped event is a pair (t, e) where t ∈ N is a timestamp and e is an event.

A trace is a sequence of timestamped events. The length of a trace T , denoted |T |, is the number of its timestamped events.

B. Audio/Video decoding Anomalies Description

While streaming a video, some common anomalies can occur. These anomalies are well known in the community of A/V developers ( [9], [START_REF]Faq: Play an audio or video file[END_REF]) and almost always have visual and sound effects on the video streaming. They can even be simulated using existing tools that are able to inject those perturbations.

We have chosen to detect three of the common errors that a developer encounters in his video players: P 1 : Audio/video/subtitle desynchronization anomaly: This anomaly reflects a desynchronization in time between audio, video or subtitles. The audio may be slower than the video or the subtitle may not appear at the right moment. P 2 : Player crash anomaly: The player stops abruptly at a random execution time, without any reason. P 3 : Slow streaming anomaly: Visually, video is very slow. In this case the audio/video/subtitles are synchronized but take much more time than in a normal execution.

C. Trace Diagnosis Problem Statement

The general trace diagnosis problem can be decomposed into two sub-problems.

1) Detect whether an execution trace presents some anomalies reflecting an abnormal behaviour of the application under supervision, and if this is the case 2) Identify the cause or at least the type(s) of these anomalies. The two sub-problems are difficult to solve in general, i.e. without exploiting some additional knowledge or without restricting their scope in order to exploit some domain-specific characteristics. Our approach to address the first sub-problem is to exploit error-free reference traces that can be obtained by a simulator, and to compare them with real execution traces using suitable distances. Detecting whether a real trace execution is abnormal consists in a distance-based comparison with the reference trace obtained by the simulator ran on the same video. Addressing the second sub-problem is crucial for trace debugging since the developers need to understand what is going wrong in order to identify the anomalies revealed by trace comparison. Our approach is to focus on the identification of pre-established types of domain-specific anomalies, namely those mentioned in Section II-B and referred to as P 1 , P 2 and P 3 respectively. The trace diagnosis problem that we consider in this paper can then be stated as follows: Given an execution trace T and a reference trace T r , how to automatically detect whether T contains anomalies of type P 1 , P 2 or P 3 , using a distance-based comparison with T r .

III. DISTANCE-BASED DIAGNOSIS

In this section, we explain our general approach for solving the trace diagnosis problem stated above, using appropriate distances. A distance d between two objects is a numerical measure of how far apart these objects are [START_REF] Pang-Ning | Introduction to data mining[END_REF]. There exist many distance definitions in the literature. For every three objects T 1 , T 2 and T 3 , the following relations must hold:

           d(T 1 , T 2 ) ≥ 0 d(T 1 , T 2 ) = 0 only if T 1 = T 2 d(T 1 , T 2 ) = d(T 2 , T 1 ) d(T 1 , T 2 ) + d(T 2 , T 3 ) ≥ d(T 1 , T 3 )
Instead of defining a single distance as a black-box to detect various anomalies, our glass-box approach defines multiple distances that are appropriate to the types of anomalies we want to detect. The procedure we follow to define our distances is the following. First, we decode a movie video with gstreamer and obtain a reference trace. Then, we inject in the streaming, perturbations corresponding to the three types of anomalies and we obtain for each anomaly the corresponding abnormal execution traces. Finally, for each type of anomaly, we manually analyze the reference trace and the execution trace, and extract the differences that are relevant for each distance. Let us now present our three distances. The first distance is the occurrence distance, suitable for detecting an anomaly of type P 1 when applied to an execution trace and the corresponding reference trace. The second distance is the dropping distance, appropriate to identify anomalies of type P 2 . Finally, we introduce the temporal distance designed to detect anomalies of type P 3 . For each distance, we give a formal definition and an algorithm for its computation.

A. Occurrence distance

For P 1 anomaly, when examining the traces, one can detect different numbers of occurrences of some events in the simulated trace and the abnormal one. We first define the occurrence ratio of an event in two traces. Definition 1: Let T 1 and T 2 be two execution traces. Let nb occur(e, T ) be the number of occurrences of event e in trace T . The occurrence ratio of an event e in the two traces T 1 and T 2 is defined as follows:

occ ratio(e, T 1 , T 2 ) =
M in{nb occ(e, T 1 ), nb occ(e, T 2 )} M ax{nb occ(e, T 1 ), nb occ(e, T 2 )}

Note that e should appear in traces. A value of occ ratio(T 1, T 2) close to zero, means that event e occurs in one of the two traces much more frequently than in the other one. Such a situation is related to an anomaly P 1 because a desynchronization in time between audio, videao and/or subtitles induces many abnormal events. That is why we define the occurrence distance between two traces as the number of events that have an occurrence ratio less than or equal to a given threshold. This distance is appropriate to retrieve P 1 , A/V/S desync. anomaly, (see section II-B) because it measures the number of events that differentiate T 1 from T 2 . The formal definition of this distance, thereafter denoted d 1 is the following:

Definition 2: Let T 1 and T 2 be two execution traces. The occurrence distance between T 1 and T 2 is:

d 1 (T 1 , T 2 ) = |{e | occ ratio(e, T 1 , T 2 ) ≤ θ}|
where θ is a given threshold.

Example 1: consider the traces T 1 and T 2 below, and let θ = 0.5. d 1 (T 1 , T 2 ) = 1 with occ ratio(It, T 1 , T 2 ) = 3/4 = 0.75, occ ratio(CS, T 1 , T 2 ) = 1/3 = 0.33 .

B. Dropping distance

For P 2 anomaly, when comparing the simulated and abnormal traces, we found that some events seem to appear only in one trace and not in the other one.

The corresponding dropping distance refers to the number of distinct events that belong only to one trace.

Definition 3: Let events(T) be the set of distinct events in T .

The dropping distance between T 1 and T 2 is the size of the symmetric difference between event(T 1 ) and event(T 2 ).

d 2 (T 1 , T 2 ) = |events(T 1 ) events(T 2 )|
This distance is appropriate to retrieve P 2 , i.e. Player crash anomaly (see section II-B).

Example 2: for traces T 1 and T 2 below, events(T

1 ) = {X, CS, It, E}, events(T 2 ) = {CS, It, U }; events(T 1 ) events(T 2 ) = {X, E, U } and d 2 (T 1 , T 2 ) = 3.

C. Temporal distance

For P 3 anomaly, the duration and the order of some events differ in the two traces. In the abnormal trace, some events durations are much longer than in the simulated trace.

The temporal distance that we propose is an adaptation of the distance model of Mannila et. al [START_REF] Mannila | Similarity of event sequences[END_REF] which is an editdistance taking into account temporal aspects. It uses three basic operations:

• Ins(e,t) that inserts an event e at time t • Del(e,t) that deletes an event e at time t • Move(e,t,t') that moves an event e from t to t . Note that the Move operation is order-preserving. This means that if t(e) = t < t = t(e ) and e, e are not deleted than one cannot have M ove(e, t, t 1 ) and M ove(e , t , t 1 ) for t 1 > t 1 . Example 3: For instance, in the example below, the operation M ove(It, 1) that transforms T 1 into T 2 is forbidden.

A cost c(o) is associated with each operation o and c(Ins(e, t)) = c(Del(e, t)) = w(e) where w(e) is a weight associated with event e. c(M ove(e, t, t )) = V |t -t| where V is a constant such that V ≤ 2.w(e). Without this condition, it would always be better to do a deletion and an insertion of an event e, instead of moving e from t to t . The cost of a sequence of operations can then be deduced. Let O = o 1 . . . o k be a sequence consisting of k transformations. The cost of O is:

c(O) = k i=1 c(o i )
The distance d(T 1 , T 2 ) is defined as the cost of the cheapest sequence of operations that transform T 1 into T 2 . Thus, if Θ is the set of operation sequences that transform T 1 into T 2 , then:

d(T 1 , T 2 ) = M in O∈Θ c(O)
Example 4: For traces T 1 and T 2 below, the cheapest orderpreserving sequence of operations that transforms

T 1 into T 2 is M ove(It, 2, 1), M ove(It, 4, 2), Ins(U, 5)= 3V + w(U ).
The beginning timestamp in two traces is not always the same. Consequently, results obtained with this method are not satisfactory. We explain this problem in example 4.

Example 5: For the two traces below, d(T 1 , T 2 ) = 0. This is not satisfactory because T 1 and T 2 have exactly the same events, and the same time intervals between events. Clearly, such traces should be considered as similar. Therefore, we adapt the Mannila distance model in order to have d 3 (T 1 , T 2 ) = 0 when T 2 is obtained from T 1 by a time shift. Definition 4: Let T 1 = (e 1 , . . . , e n ) and T 2 = (f 1 , . . . , f m ) two execution traces, and let r(i, j) denote the minimum cost of the operations needed to transform the first i events of T 1 into the first j events of T 2 . The temporal distance between T 1 and T 2 is:

d 3 (T 1 , T 2 ) = r(n, m)
where r(i, j) is computed according to the following dynamic programming algorithm:

r(0, 0) = 0 r(i, 0) = r(i -1, 0) + w(e i ) r(0, j) = r(0, j -1) + w(f j ) r(i, j) = min { r(i -1, j) + w(e i ), r(i, j -1) + w(f j ), r(i -1, j -1) + cost(i, j)}
w(e i ) is the cost of deleting event e i at position i. w(f j ) the cost of inserting event f j at position j and

cost(i,j) =      w(ei)+w(fj ) if ei =fj V.|(ti-ti-1)-(t j -t j-1 )| if ei=fj and i=j V.

|ti-t j | if ei=fj and i =j

The application of this Temporal distance in the traces of example 2 gives d 3 (T 1 , T 2 ) = 0. Hence, this distance is appropriate to retrieve P 3 , i.e. slow streaming anomaly (see section II-B).

D. Distance computation algorithms

For each distance defined above the output is a value in R + . In order to better interpret the results, it is important to normalize the output. We use a non-linear transformation g, in order to normalize the distances:

g : R + → [0, 1] d → d/(1 + d) = g(d)
The computation of occurrence distance (Subsection III-A) and dropping distance (Subsection III-B) are done in linear time complexity since a simple scan of traces is necessary.

With the dynamic programming algorithm presented above, the computation of temporal distance (Subsection III-C), has a quadratic complexity O(m × n), where m and n are the lengths of the two traces. [START_REF] Wu | An o(np) sequence comparison algorithm[END_REF] proposed some improvements with a O(np) time complexity, where p = D/2 -(n -m)/2 with D being the length of a shortest edit script (consisting of insertions and deletions) between the two sequences to compare; we suppose n ≥ m.

It is important to emphasize that each of these distances can be computed at different levels of granularity. Each trace can be decomposed into blocks of events related to a specific plugin of the pipeline (Subsection II-A). When comparing sequences of events by plugin, we can detect in which plugin the anomaly that takes place.

IV. THE TED TOOL ILLUSTRATED ON A USE CASE

In this section, we describe TED, our TracE Diagnosis tool (Fig. 2), and illustrate its functioning on two use cases.

A. TED Architecture

TED handles two main phases. The Preprocessing and trace generation phase takes as input -a reference trace and a source file to generate an execution trace T via the multimedia Toolkit. The traces are preprocessed. This step is very important for a successful outcome of the analysis as a non cleansed and non normalized data can lead to spurious and meaningless results [START_REF] Mörchen | Time series knowledge mining[END_REF]. A parsed trace (c.f. figure 3) T p (respectively T r ) is obtained from T (respectively reference trace), by removing some redundant informations or by modifying others. If needed, we can abstract traces via the Fig. 2. TED Architecture abstractor tool. We further explain in section V the utility of such abstraction and how our distance-based algorithms can be adapted to such traces.

The Diagnosis process, is the second and core phase of TED. The distance selector engine chooses an appropriate distance from the Distances database and applies it to the anomaly it needs to detect. For instance, if we want to detect a desynchronization anomaly, the distance selector engine applies the occurrence distance on T p and the reference trace T r .

B. Use cases

We consider the following scenario. A user is watching a video and (a) the video streaming becomes very slow or, (b) the sound is desynchronized with images.

In the Preprocessing and Trace Generation phase, we decode the movie with gstreamer to obtain the reference trace T r . We use a gstreamer element identity [7], with property sleep-time, to obtain a A/V/S desync. anomaly (scenario b). The abnormal trace obtained is T . We generate another abnormal trace, with a slow streaming anomaly (scenario a) by a stress of CPU and memory in the system. T r and T have the format of Fig. 3(a). In order to reduce the size of the dataset for easier processing by temporal distance, we keep only four events columns, which correspond to timestamps, Debug level, function and the first argument of the message. As a result, the dataset was reduced to 26, 5% of its original size (Fig. 3(b)).

In the Diagnosis process phase, the developer uses TED as follow:

• The developer has an idea of the anomaly and just want to verify if his hypothesis is true or not. He selects the distance to apply and TED gives the diagnosis. In Fig. 4(a), temporal distance is used (scenario a). The developer suspects a slow streaming anomaly (P3). TED detects the anomaly and returns the value of temporal distances between the two traces per plugins. TED points out the audioresample plugin to be the one with the most dissimilar events between the two traces.

• The developer has no idea of what is happening and would like to find if there exists an anomaly in T . He selects the choice find anomaly, and TED applies successively all the distances, and stops when one of them gives a non-zero value (Fig. 4(b)). In scenario b, dropping and occurrences distances have been tested and a A/V/S desync. anomaly was detected.

• The developer wants to find all potential anomalies in T (choice all tests). Indeed, it is possible to have simultaneously a A/V/S desync. and a player crash anomaly. By using TED, a developer analyzing an execution trace is notified of anomalies, their types and where they appear in the trace (the plugin concerned). TED is a time saver for developers as they can quickly detect anomalies in their execution traces and fix them.

V. EXPERIMENTS

We conducted a set of experiments to demonstrate the quality and efficiency of our proposed execution trace diagnosis tool. First we use standard distance algorithms to compare traces and show the semantic added-value brought by TED. We also show how helpful this automatic tool can be for developers, by an evaluation of TED scalability and precision. Finally, we discuss the importance of trace abstraction and show how to adapt TED to take into account abstract traces.

System configuration: Our prototype system is implemented in Python 3.2. The experiments were run on an Intel Xeon E5-2650 at 2.0GHz with 32 Gigabytes of RAM with Linux.

Data Set: We use traces from two real applications, described below: Gstreamer application: Gstreamer [7] is a powerful open source multimedia framework for creating streaming applications, used by several corporations as Intel, Nokia, STMicroelectronics and many others. For these experiments we decoded several movies using Gstreamer on a Linux platform, with the f f mpeg plugin for video decoding. GSTapps application: It is a test video decoding application for STMicroelectronics development boards. This application is widely used by STMicroelectronics developers. The execution trace contains both application events and system-level events. It is generated from a ST 40 core of the SoC, which is dedicated to application execution and device control. Table I gives a description of reference traces.

Comparison with standards sequence distances: We used existing implementations of two well known sequence dis- tances DTW [START_REF] Sakurai | Stream monitoring under the time warping distance[END_REF] and LCS [START_REF] Bergroth | A survey of longest common subsequence algorithms[END_REF]. These implementations are given by mlpy [START_REF] Albanese | mlpy: Machine learning python[END_REF], a Python module for Machine Learning built. For our experimentations, the events of execution traces were coded as integers, as required by mlpy. LCS(x, y) returns the length of the longest common sequence of x and y. We then obtain distance between x and y by d(x, y) = |x|+|y|-2 * LCS(x, y). Table II shows the values of distances obtained w.r.t to two execution traces given as input. An error occurs during the video streaming, after a given number N of buffers. N = 500. We obtained for instance dtw(T r , T 3 ) = 920600.

The observation is that T 1 , T 2 and T 3 are far from T r . With standard distance algorithms, we can only compute distance values but we have no idea which type of anomalies are in the traces.

In our proposal, for T 1 , TED diagnoses a slow streaming problem. He gives 132090.5 as d 3 (T r , T 1 ), and 131525 as d 3 (T r , T 2 ) which confirm our expectation of d(T r , T 1 ) > d(T r , T 2 ), and the fact that the video execution of T 1 is slower than the one of T 2. For T 3 , TED diagnoses a player crash anomaly in addition to giving a distance value between T 3 and T r .

Running time and Scalability: Fig. 5 reports the wall clocks of TED for occurrence and dropping distance, when varying events number of execution traces. Horizontal axis represent the maximum number of events of the two compared traces.

In practice, we consider as θ = 0.25, as threshold of occ ratio. One can notice that, for traces of more than 1G o , corresponding to approximatively 4, 000, 000 events, TED can give a diagnosis in less than 10s. For the pub video of table II, an output is obtained in 0.12s. The experiments showed that the proposed methods can scale to real application traces. This makes TED suitable for analysis of real traces. III. The first observation is that all execution traces initially considered as normal were diagnosed as such by TED. However, the tool gave 14 false-true which are execution traces considered by TED as normal but which contain anomalies. Thus, TED has a precision of 95.33%. A reason of this lack of precision can be the value of threshold for occurrence distance. We fixed it at θ = 0.25 but we will surely gain to adapt the threshold value to the length of the video decoded. We are currently testing the correlation between the video length and the threshold value. Discussion about abstract traces: One way to bypass the problem raised by multimedia applications in which raw execution traces are very large (more than a gigabyte for few minutes of video decoding [START_REF] Gurin | Approche Efficace de Développement de Logiciel Embarqué pour des Systèmes Multiprocesseurs sur Puce[END_REF], [START_REF] Prada-Rojas | Summarizing embedded execution traces through a compact view[END_REF]) is to abstract traces. The abstraction process produce more compact traces and facilitate the readability of traces for human programmers. An abstract trace example is given Fig. 7.

A block in an trace

We define as timestamped block a pair (t, B) where B is a block and t ∈ N, is the timestamp of the first event of B.

A abstracted trace is a sequence of timestamped blocks. The length of a abstracted trace T denoted |T | is the number of its blocks (c.f. fig. 6). The size of a sequence S, denoted by S , is the total number of events that it contains. For an execution trace T , |T | = T whereas for an abstracted trace T a , described by blocks, |T a | = T a (except when blocks are singletons of events). Fig 7 is an example of abstracted trace obtained by FrameMiner [START_REF] Kengne | Efficiently rewriting large multimedia application execution traces with few event sequences[END_REF] on pub video. Our approach gains to be generic i.e. applicable to execution traces described at different levels of abstractions: on raw execution traces that are sequences of time-stamped low-level events, as well as on sequences of time-stamped blocks, in which (subsequences of) low-levels events have been abstracted into blocks [START_REF] Kengne | Efficiently rewriting large multimedia application execution traces with few event sequences[END_REF] more meaningful to the programmer. In order to apply TED on abstract traces, a first idea would be to consider occurrence of a block as a strict Fig. 7. An abstracted trace obtained with FrameMiner sequence of events and to apply our distances not on events but on blocks. The adaptation of TED to abstracted traces is currently under development.

VI. CONCLUSION

To analyse traces of finished events, and fix bugs, programmers use several tools such as trace visualizers ( [18]- [START_REF] Seyster | Techniques for visualizing software execution[END_REF]) and techniques such as tracepoints on the execution traces. These techniques need to have an expert to interpret the graphical representation. In contrast, our work based on distances develops a technique which limits the developer intervention. There is an abundant literature about distances. For distances between sequences, an edit distance model is used in [START_REF] Dobrisek | An edit-distance model for the approximate matching of timed strings[END_REF] to approximate matching of timed strings; [START_REF] Kostakis | Distance measure for querying sequences of temporal intervals[END_REF], [START_REF] Gundersen | Toward measuring the similarity of complex event sequences in real-time[END_REF] propose to represent each sequence in a suitable form, before computing distance. However, very few distances take into account the temporal aspect. We propose a temporal distance that is adapted for trace comparison. But the most distinguishing point of our approach is that our method is the first, to the best of our knowledge which returns a diagnosis to the user, added to the effective values of distance. Our approach diagnoses anomalies in an execution trace of multimedia application, by comparison with a reference trace. We use distances as models of comparison and specifically design three distinct distances in order to tackle well-known anomalies of the multimedia domain. We experimentally show the originality of our solution compared to existent distances and show that our proposed approach scales well to real huge application traces. Distances defined in our approach allow to identify a specific problem and give a semantic added-value level to the analysis. Moreover, as all distances, they also provide insights of how far an abnormal trace is from a correct one. We also present a use case on how TED performs the analysis of a trace and conduct some experiments to evaluate TED scalability and accuracy. We have three research directions. The first direction is to adapt our distances to abstract traces so that our proposal be as generic as possible. The second direction is to enlarge TED to other types of anomalies for instance the image is completely fuzzy, upside down and/or cut in half. The strength of our contribution is that it is easily extensible to other types of anomalies. For each new anomaly, we only need to follow the same methodology as explained in the paper to find the best suitable distance capable of clearly detecting the anomaly. There is no need to do any changes in TED existing architecture. Finally, additional constraints can be introduced such as parallel execution traces and the challenge is to identify, for example, streams of different execution and take them into account for the computation of distances.

ACKNOWLEDGMENT

This work is supported by French FUI project SoCTrace.

Fig. 3 .

 3 Fig. 3. Example of data preparation

  Fig. 5. Running time

TABLE I

 I

		EXPERIMENTAL DATASET
	Video	Duration Nb. of events	Size
	generic	5s	15, 110	2.9Mo
	pub	30s	74, 510	14.3Mo
	movie	3628s	12, 423, 095	2457, 6Mo
	SDK2	335s	2, 382, 720	73.2Mo

  With sleep -time = 5000, we obtained T 2 and a visual degradation slighter than those related to T 1 , not really perceptible. Naturally, we expect that d(T r , T 1 ) > d(T r , T 2 ). It is the case with DTW distance (509069 > 504472), but not with LCS distance. T 3 is obtained with property error-after.

		TABLE II
	DTW AND LCS DISTANCES
		DTW	LCS
	(Tr, T 1 )	509069	28035
	(Tr, T 2 )	504472	28086
	(Tr, T 3 )	920600	18377
	T r is the reference trace of generic video; T 1 is obtained
	by using the gstreamer element identity before the video
	decoding plugin, with property sleep -time = 30000.


Anders Thorin
email: anders.thorin@mcgill.ca

Mathias Legrand

Stéphane Junca

St Éphane Junca

Nonsmooth modal analysis: Investigation of a 2-dof spring-mass system subject to an elastic impact law

Keywords: vibro-impact oscillator, nonlinear modes of vibration, nonsmooth modal analysis, autonomous response

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Vibration analysis is easily carried out in the framework of linear elastodynamics because the principle of superposition says that any solution is a combination of linear normal modes. The notion of modes has been extended in the context of nonlinear dynamics [START_REF] Rosenberg | On nonlinear vibrations of systems with many degrees of freedom[END_REF][START_REF] Shaw | Non-linear normal modes and invariant manifolds[END_REF][START_REF] Shaw | Normal modes for non-linear vibratory systems[END_REF][START_REF] Vakakis | Normal modes and localization in nonlinear systems[END_REF] which opens doors to efficient dynamic analysis of smooth nonlinear systems in the neighbourhood of fixed points and to model-reduction of large-scale systems [START_REF] Kerschen | Nonlinear normal modes, part I: a useful framework for the structural dynamicist[END_REF]. Nevertheless, this extension relies on the smoothness of the solutions and many mechanical systems such as industrial robots, rotating machinery may undergo unilateral contact with adjacent components. Nonlinear modes have also been studied on piecewise linear systems with regularized contact occurrences but with no general outcome regarding modal analysis [START_REF] Chen | Normal modes for piecewise linear vibratory systems[END_REF][START_REF] Chati | Modal analysis of a cracked beam[END_REF][START_REF] Jiang | Large-amplitude non-linear normal modes of piecewise linear systems[END_REF]. When not regularized, unilateral contact events induce discontinuities in velocity and usual ordinary differential equations fo not properly capture nonsmooth events such as impacts [START_REF] Acary | Numerical methods for nonsmooth dynamical systems: applications in mechanics and electronics[END_REF]. Such a system is investigated in the present work.

Nonsmooth systems, i.e. systems undergoing nonsmooth events, have been increasingly studied in the last two decades [START_REF] Acary | Numerical methods for nonsmooth dynamical systems: applications in mechanics and electronics[END_REF][START_REF] Üls | Simultaneous enforcement of constraints at position and velocity levels in the nonsmooth generalized-˛scheme[END_REF] usually in the time-domain. Vibration analysis of forced nonsmooth systems is reported in the literature (see e.g. [START_REF] Masri | Dynamic response of a beam with a geometric nonlinearity[END_REF][START_REF] Wagg | Application of non-smooth modelling techniques to the dynamics of a flexible impacting beam[END_REF] among many others). Nevertheless, very few works tackle such systems with no external periodic forcing, with the aim of identifying nonlinear modes of vibration [START_REF] Lamarque | Modal analysis of mechanical systems with impact non-linearities: limitations to a modal superposition[END_REF][START_REF] Pilipchuk | Impact modes in discrete vibrating systems with rigid barriers[END_REF][START_REF] Pascal | Dynamics and stability of a two degree of freedom oscillator with an elastic stop[END_REF][START_REF] Laxalde | Nonlinear modal analysis of mechanical systems with frictionless contact interfaces[END_REF][START_REF] Moussi | Nonlinear normal modes of a two degrees-of-freedom piecewise linear system[END_REF]. The latter are commonly defined as continuous families-continuity with respect to the energy-of periodic orbits in the phase space. Extensions to nonsmooth systems yield families of nonsmooth periodic orbits. Illustrations are provided on an elementary system with two degrees-of-freedom exhibiting one and two impacts per period (ipp), similar to those studied in [START_REF] Luo | Hopf bifurcation of a two-degree-offreedom vibro-impact system[END_REF][START_REF] Wagg | Periodic sticking motion in a two-degree-of-freedom impact oscillator[END_REF]; we highlight again that here, the autonomous system only is investigated.

First, the model is exposed and the expression of the autonomous periodic solutions is derived. It is shown that the existence of periodic solutions depends on three necessary conditions. These conditions are explored for one and two ipp. Continuous families of admissible solutions organized on two-dimensional manifolds are introduced. Nonsmooth modes are then defined and illustrated. Unexpectedly, two supporting manifolds are connected by a "bridge" in the frequency-energy plot: this is described in the last section. Some of the proposed results have to be taken as conjectures since they have only been numerically observed, on a number of calculations, yet not mathematically proven.

The system of interest consists of two springs k 1 and k 2 connected to two masses m 1 and m 2 in series, as depicted in Figure 1.

The corresponding displacements are denoted x 1 .t / and x 2 .t /, respectively. For sufficiently large amplitudes, the second mass x 2 meets a rigid obstacle and thus should satisfy a Signorini condition which prevents any interpenetration with the foundation [START_REF] Jean | Non-smooth contact dynamics approach of cohesive materials[END_REF]:

8t 0; 8 < :d x 2 .t / 0 .t / 0 .t /.d x 2 .t // D 0 (1)
where is the reaction force of the obstacle on the second mass, negative for sticking. Note that the first mass is not subject to any unilateral contact condition.

To ensure the well-posedness of the problem, information regarding the impact must be added [START_REF] Ballard | The dynamics of discrete mechanical systems with perfect unilateral constraints[END_REF]. In this work, this information is incorporated in the form of a perfectly elastic Newton impact law through the introduction of a restitution coefficient 1 e 0. The dynamics is governed by the following equations: i / stand for the velocity of the second mass just before and just after the impact, respectively-more precisely the left-and right-hand side limits of P x 2 in t i . In this paper, periodic orbits are solely targeted. To ease the discussion to come, problem [START_REF] Shaw | Non-linear normal modes and invariant manifolds[END_REF]

8t such that x 2 .t / < d; Ä m 1 0 0 m 2 Â R x 1 .t / R x 2 .t / Ã C Ä k 1 C k 2 k 2 k 2 k 2 Â x 1 .t / x 2 .t / Ã D Â 0 0 Ã (2a) 8t i such that x 2 .t i / D d; P x 2 .t C i / D e P x 2 .t i / (2b)
Equation (3a) ensures the solutions obey the dynamics; (3b) is the impact law; (3c) guarantees the periodicity of the solution; (3d) ensures that t 1 ; : : : ; t m are actually impact instants, and finally (3e) means that x 2 does not undergo more than m impacts on the time interval OE0 I T OE. Without any loss of generality, the first impact is now assumed to occur at t 1 D 0. By periodicity, this also corresponds to an impact at T , which is the first impact of the second period. The periodicity (3c) requires that e D 1, which is considered here. Indeed, e < 1 leads to an instantaneous loss of kinetic energy of the second mass and therefore an instantaneous change of the total energy of the system at each impact.

With the final objective of calculating solutions to system (3), necessary conditions on their existence are now derived. This is achieved as follows: derive the free dynamics on 0 I t 2 OE, enforce the impact law at t 2 , and repeat with the subsequent sequences of free dynamics and corresponding impact occurrences up to the last interval t m I T OE. This yields a necessary condition on the period T and the intermediate impact time instants t 2 ; : : : ; t m . The linear dynamics is governed by Eq. (2a) which can be compactly cast in a matrix form: 4) can be diagonalized as

MR x C Kx D 0 (4)
I 2 R q C q D 0 (5)
which gathers two uncoupled equations. In Eq. ( 5), the notations I 2 D diag.1; 1/ and D P 1 M 1 KP D diag.! 2 i / i D1;2 are used. This second order differential equation can be transformed into a first order differential equation:

 P q.t/ R q.t/ à D Ä 0 2 I 2 0 2  q.t/ P q.t/ à (6)
Introducing Q q.t/ D q.t/ > P q.t/ > > , the solutions of the smooth free motions are thus given by:

Q q.t/ D Q S.t/ Q q.0/ (7)
where Q S is the exponential of the matrix in ( 6):

Q S.t/ D 2 6 6 4 cos.! 1 t / 0 sin.! 1 t /=! 1 0 0 cos.! 2 t / 0 sin.! 2 t /=! 2 ! 1 sin.! 1 t / 0 cos.! 1 t / 0 0 ! 2 sin.! 2 t / 0 cos.! 2 t / 3 7 7 5 (8)
The dynamics is fully determined by the four initial conditions Q q.0/. Naturally, the components of q have the major benefit of being dynamically uncoupled, but the condition of unilateral contact inherently involves the physical coordinate x 2 .t /. There is hence no evident better choice for the basis into which the contact dynamics will be described: both the modal (for the free flight) and the physical basis (for the impact condition) are involved.

When contact occurs, the impact condition (3b) on P

x 2 and the continuity of P

x 1 are expressed in a matrix form as:

P x.t C / D N P x.t / with N WD Ä 1 0 0 e (9)
that is, in terms of modal velocities:

P q.t C / D P 1 NP P q.t / (10)
Overall, the impact law is written

Q q.t C / D Q N Q q.t / (11)
where by definition

Q N WD Ä I 2 0 2 0 2 P 1 NP (12)
Accordingly, the two possible states of the system in OE0 I T OE are:

Free phase on any interval t i I t i C1 OE, with i 2 1; : : : ; m:

Q q.t/ D Q S.t t i / Q q.t C i / (13)
Impact for any time of impact t i 2 f0; t 2 ; : : : ; t m g:

Q q.t C i / D Q N Q q.t i / (14)
It is now possible to describe the periodic solutions of period T with m intermediate impact occurrences ft 2 ; : : : ; t m g as listed in Tab. 1. The periodicity condition (3c) formulated on the modal

t Q q.t/ D t 2 OE0 I t 2 OE Q S.t/ Q q.0/ t 2 OEt 2 I t 3 OE Q S.t t 2 / Q N Q S.t 2 0/ Q q.0/ : : : : : : t 2 OEt m I T OE Q S.t t m / Q N Q S.t m t m 1 / Q N Q S.t 2 0/ Q q.0/ Table 1. Modal displacement Q q as a piecewise function of time.
coordinates, that is Q q.T / D Q q.0/, can now be expressed as

Q S.t t m / Q N Q S.t m t m 1 / Q N Q S.t 2 0/ Q q.0/ D Q q.0/ (15)
or equivalently

Q q.0/ 2 ker A m (16)
with

A m WD S.T t m / Q NS.t m t m 1 / Q NS.t 2 0/ I 4 (17)
This 4 4 matrix A m stems from Eq. (3a), (3b), and (3c) and governs the existence of periodic solutions with m impact(s) per period. It embeds the free dynamics on every time interval 0 I t 2 OE; : : : ; t m I T OE and the change of sign of P x 2 at impact times 0; t 2 ; : : : ; t m . It is essential to find impact times ft 2 ; : : : ; t m g for which solutions to (3) may exist. Indeed, if det A m ¤ 0, the unique solution of Eq. ( 16) is Q q.0/ D .0 0 0 0/ > . This indicates that det A m D 0 (or equivalently dim.ker A m / > 1) is a necessary condition for the existence of solutions of (3). It is denoted by (NC1).

However, A m does not include (3d) and (3e). Hence, identifying a period T and impact times ft 2 ; : : : ; t m g using (NC1) does not ensure that the corresponding displactement is a solution of [START_REF] Shaw | Non-linear normal modes and invariant manifolds[END_REF]. Two additional verifications have to be performed: first, impacts must occur when the second mass meets the obstacle (3d). This condition ensures that the impact law on x 2 .t i / is enforced only when x 2 .t i / D d . Otherwise, the second mass should free-flight in OE0 I T OE for times other 0; t 2 ; : : : ; t m n that is x 2 < d since x 2 is continuous on R C . Formally and all together these conditions are:

(NC1) det.A 2 / D 0 for T and t 2 ; : : : ; t m (NC2) 8t 2 f0; t 2 ; : : : ; t m g;

x 2 .t i / D d (NC3) 8t 0, x 2 .t / Ä d .
To illustrate the necessity of (NC2) and (NC3), a displacement x 2 .t / calculated using A 2 and Tab. 1 is represented in Figure 2. It is clear that it is not a solution of (3), because it does not satisfy (NC2) nor (NC3).

t 2 T 0 d t x 2 .t/ Figure 2. Non-admissible displacement with m D 2: [ ] x 2 .t /. The motion satisfies condition (NC1) but neither (NC2) (x 2 .t 2 / ¤ d ) nor (NC3) (because x 2 d for some t 2 OE0 I T OE). Defining Q P WD Ä 0 2 P 0 2 P (18)
condition (NC2) can be expressed in the modal basis as:

Q P Q S.t i t i 1 / Q N Q S Q N Q S.t 2 0/ Q q.0/ e 2 D d (19)
8t i 2 ft 2 ; : : : ; t m g. Eq. ( 19) yields an algebraic system of m equations. It will be shown that whether these equations are redundant or not is an essential criterion for the existence of solutions of (2). All together, the three necessary conditions yield a necessary and sufficient condition for the existence of a solution to system (3). In terms of computation, (NC3) is the most costly condition because to our knowledge, it can only be checked numerically.

To summarize, given .k 1 ; k 2 /, .m 1 ; m 2 /, and m:

1. matrix A m can be defined as a function of t 2 ; : : : ; t m ; T .

a solution exists if and only if

(NC1) det.A m / D 0 (NC2) 8t 2 f0; t 2 ; : : : ; t m g;

x 2 .t i / D d (NC3) 8t; d x 2 .t / > 0
3. when these three conditions are met for some t 2 ; : : : ; t m ; T , the solution is a piecewise function given by Tab. 1.

In the following, the terminology potential solution refers to motions which satisfy conditions (NC1) and (NC2), and admissible solutions refer to motions which satisfy conditions (NC1), (NC2), and (NC3), and are thus solutions of (2). Of course, admissible solutions are also potential solutions. Also, all figures were obtained with .m 1 ; m 2 / D .1; 1/ kg, .k 1 ; k 2 / D .0:85; 2/ N m 1 , and d D 1 m. These values are arbitrary. They correspond to periods T 1 2:97 s and T 2 10:19 s. Units are no longer indicated in the remainder.

Existence of admissible solutions 2.1 One impact per period

In this section, attention is paid to periodic orbits with exactly one impact per period. It can be theoretically shown that the mapping

A 1 W T 7 ! Q N Q S.
T / I 4 has a kernel of dimension 1, for every T > 0, except for some very specific values of k i and m i , i D 1; 2 corresponding to internal resonances that are not discussed in the present work. Condition (NC1) is thus verified. (NC2) consists in a unique equation:

Pq.0/ e 2 D d " P 11 q 1 .0/ C P 12 q 2 .0/ D d (20)
Since the kernel of A 1 is of dimension 1, condition ( 20) is always satisfied: for the unique vector y D OEy 1 ; y 2 ; y 3 ; y 4 > in ker.A 1 /, then ˛y verifies (NC2) with ˛D d=.P 11 y 1 C P 12 y 2 /. Accordingly, there is a unique potential solution for every T > 0. Let us now focus on (NC3). Given T and a potential solution x 2 .t /, it is possible to calculate numerically its maximum over OE0 I T and check that max x 2 .t/ < d . It appears that there are intervals of T which contains admissible solutions, as illustrated in Fig. 3.

To understand these seemingly random zones of admissible solu- [ ] Linear modal transitions. T S is an example of singular transition. T G is an arbitrary grazing transition used in Fig. 5.

T 1 2T 1 3T 1 T 2 4T 1 5T 1 6T 1 2T 2 T (period)
tions, the expression of x 2 is explored in more details: given an arbitrary T and t 2 OE0 I T OE, its expansion yields:

x 2 .t/ D A.T / B 1 .T / cos ! 1 .t T =2/ C B 2 .T / cos ! 2 .t T =2/ (21)
where Such T S are shown in Fig. 3. In the left neighbourhood of a T S , x 2 diverges to C1, while in the right neighbourhood, it diverges to 1.

A.T / D d
Linear modal transitions They may occur when T is a multiple of the linear periods T 1 or T 2 , that is when

! 1 T Á 0 .mod 2 / or ! 2 T Á 0 .mod 2 / (24)
Fig. 4 illustrates how an admissible solution smoothly becomes non-admissible. These transitions occur when a linear mode has a sufficiently large energy to graze the wall, level after which they vanish.

Grazing transitions They can be found by comparing d and max t2OE0 IT OE x 2 .t /. These are by far the most interesting transitions: from 1-ipp trajectories, they lead to multiple impacts per period solutions as shown later. Such a transition period denoted by T G is represented in Fig. 3 and the corresponding T G -periodic motion is plotted in Fig. 5. Grazing transition in T G (see Fig. 3). Solutions with two impacts per period emerge from this transition, see last section.

[ ] Solution forT D T G .

Solutions corresponding to a grazing transition always have at least a solution to the equation x 2 .t / D d in 0 I T OE. They are common solutions to two distinct problems [START_REF] Pascal | Dynamics and stability of a two degree of freedom oscillator with an elastic stop[END_REF] (with the associated conditions (NC1), (NC2), and (NC3)) with a different number of impacts per period m. Our observations on numerical examples tend to show that grazing transitions have a very particular property-which we have not proven mathematically yet: the conditions 8t i , x 2 .t i / D d in Eq. (3c) are all redundant. This property has remarkable consequences as explained later.

Two impacts per period

T -periodic admissible solutions with two impacts per period are targeted in this section. To this end, we explore the mapping

A 2 W .t 2 ; T / 7 ! Q N Q S.T t 2 / Q N Q S.t 2 / I 4 (25)
We recall that the necessary condition (NC1) requires that t 2 and T be such that det A 2 .t 2 ; T / D 0. A first result is that given an arbitrary T , condition (NC11) is satisfied for a few t 2 only, if any. This is illustrated in Fig. 6 proven but the proof is not detailed for the sake of brevity, is that 8T; det.A 2 .T =2; T // D 0 (26) so that t 2 D T =2 always satisfies (NC1). This corresponds to 2-ipp T -periodic solutions which are in fact 1-ipp T =2-periodic solutions seen on two periods. This result is complemented by a second one which states the existence of a threshold above which there always exists at least a t 2 ¤ T =2 which is root of det.A 2 . ; T //. Such a threshold, which can be refined in specific cases is Q T D 3 = min.! 1 ; ! 2 / or equivalently Q T D 3 max.T 1 ; T 2 /=2. This can be mathematically written as

8T Q T ; 9t 2 ¤ T =2 such that det.A 2 .t 2 ; T // D 0 (27)
A third interesting result when m D 2 is that if (NC1) is satisfied, then it is always possible to find initial conditions such that (NC2) is satisfied too. This comes from the following property: det.A 2 .t 2 ; T // D 0 H) dim.ker.A 2 .t 2 ; T /// D 2 (28) Indeed, dim.ker.A 2 .t 2 ; T // D 2 for some appropriate .t 2 ; T / means that it is possible to choose the initial conditions such that the motion obeys two independent constraints x 2 .0/ D d and

x 2 .t 2 / D d .
Again, (NC3) has to be tested numerically and zones of admissible solutions emerge again. This time, they involve both T and t 2 . Numerical results are exposed in Fig. 7. Since t 2 D T =2 always corresponds to a potential solution for m D 2, which is nothing else than two periods of the potential solution for m D 1, configurations with m D 1 and some of the configurations with m D 2 are related. This is highlighted in Fig. 8 which combines To summarize, when m D 2, potential solutions of minimal period T sometimes exist when T is smaller than Q T , and always exist when T > Q

T 1 2T 1 3T 1 T 2 4T 1 5T 1 6T 1 2T 2 T (
T . The existence of potential solutions coincide with the roots of det.A.t 2 ; T // which defines continuous curves in the plane .t 2 ; T /. Subparts of these curves define continuous zones of admissible solutions.

More than two impacts per period

More generally, (NC1) seems to be driven by the parity of m. The following results have not been mathematically proven but numerically verified on numerous examples. They have therefore to be understood as conjectures:

If m is odd, then dim.ker A m / D 1. (NC2) imposes m conditions, so potential solutions may exist only if these conditions form a system of rank 1, i.e. if they are all equivalent. This seems to happen only for a very few cases corresponding to 1 ipp grazing orbits, see Fig. 9. Any 1-ipp potential solution of period T =3 is of course also a potential solution of a 3-ipp problem.

If m is even, then dim.ker A m / D 2 and (NC2) imposes m conditions, so potential solutions may exist only if these conditions form a system of rank 1 or 2. These motions have not been thoroughly investigated but no potential solution has been found yet with m 4. Trajectory with two grazing points and one impact: admissible solution to both the 1-ipp and 3ipp formulations.

Nonsmooth modes of vibration

In linear dynamics, modes are two-dimensional flat surfaces in the phase space. The notion of normal mode has been particularly extended to smooth nonlinear dynamics in [START_REF] Shaw | Non-linear normal modes and invariant manifolds[END_REF], with the following definition: a nonlinear normal mode is a two-dimensional invariant manifold of the phase space, tangent to a mode of the linearized system. Invariant means that if a motion starts on the nonlinear mode at a given time, then it will remain on it for all times. In the same spirit, the definition of a nonsmooth mode of vibration is proposed here: a nonsmooth mode is an invariant manifold formed by a continuum of periodic autonomous (possibly nonsmooth) orbits in the phase space, containing one orbit the a linear mode. For two degree-of-freedom systems, such modes could be described by four functions f 1 ; : : : ; f 4 of two parameters, e.g. the energy E and time t such that:

x 1 D f 1 .E; t / x 2 D f 2 .E; t / P x 1 D f 3 .E; t / P x 2 D f 4 .E; t / (29)
We showed that for m D 1, continuous zones of admissible solutions exist. For each of them, it is therefore possible to define two-dimensional surfaces of the phase space .x 1 ; x 2 ; P x 1 ; P x 2 / which contains all their admissible motions. Note that in the energy-frequency plane, these zones are delimited by T 1 , T 2 or one of their multiples, therefore they contain an orbit of a grazing linear mode. Such a surface is represented in Fig. 10. The nonsmooth mode contains one orbit of a grazing linear mode (see red curve in Fig. 10). It is noteworthy that the nonsmooth mode indeed presents some discontinuities on P x 2 , when x 2 D d . Similarly, nonsmooth modes can be defined for 2-ipp motions, since continua of admissible solutions exist. While 1-ipp nonsmooth modes support periodic orbits of different periods T , 2-ipp nonsmooth modes gather periodic orbits which differ in both t 2 and T -but t 2 and T cannot vary independently, they are related by the constraint det.A 2 .t 2 ; T // D 0. To better understand the meaning of the invariant manifold, various x 2 are displayed in Figure 11. The corresponding orbits are combined in a three-dimensional cross-section .x 1 ; x 2 ; P x 2 / of the phase plot .x 1 ; x 2 ; P x 1 ; P x 2 /, which is an illustration of a cross-section of a 2-ipp nonsmooth mode.

Nonsmooth modes feature numerous benefits. They contain an infinity of admissible solutions which corresponds to a continuum of energy. They provide a picture of the possible admissible solutions lying in the phase space of the system of interest. They also provide indications on other regions of the phase space because orbits cannot intersect: for example they can define closed boundaries from which solutions cannot escape. It is also highly possible yet not proved that the associated forced solutions reach high amplitudes when they approach a nonsmooth mode, as it stands in linear and smooth nonlinear dynamics. Additionally, based on preliminary numerical experiments, the developments presented in this paper seem to directly extend to arbitrary Ndegree-of-freedom systems.

Relation between 1-ipp and 2-ipp nonsmooth modes

In this last section, a relation between 1-ipp and 2-ipp nonsmooth modes is described. This is not completely understood yet, but Periodic orbits with two impacts per period in the neighbourhood of 3T 1 . These orbits lie on a nonsmooth manifold. It is visible that x 2 6 1, and that when x 2 D 1, P x 2 is discontinuous. The continuum of orbits is illustrated by the red curve which continuously shades into blue ones.

unexpected admissible solutions exist that were never reported before. Indeed, we recall that for grazing transitions, conditions x 2 .t i / D d , i 2 f1; : : : ; mg, are apparently redundant, and can thus reduced to x 2 .0/ D d . When m D 2, for t 2 and T such that det.A 2 .t 2 ; T // D 0, then dim.ker A 2 .t 1 ; T // D 2. Initial conditions, which have to be elements of the bi-dimensional plane ker.A 2 / and simulaneously satisfy x 2 .0/ D d are underdetermined: there is a continuum of such initial conditions. Accordingly, a free parameter can be chosen to describe this continuum. The interval in which it lives in controlled by the admissibility of the displacements corresponding to this initial condition. Interestingly, the extremal values correspond to cases which are common solutions of the 1-ipp and the 2-ipp problems. Moreover, the two 1-ipp solutions happen to be actually the same solution shifted in time by half a period as depicted in Fig. 13. Such solutions are also illustrated in a cross-section of the phase plot in Fig. 14. The 1-ipp smooth manifold (only partially represented, in blue) gives rise to a surface made of a continuum of 2-ipp orbits. Moreover, the solutions contained in the continuum of 2-ipp orbits exhibit all the same period but distinct energies. In other words, the differences between the orange curves in Fig. 14 and the nonsmooth manifolds in Fig. 10 and 12: the orange curves correspond to trajectories which all have the exact same period and for which the two conditions x 2 .t 1 / D d and x 2 .T / D d are equivalent. They differ by the value of the free parameter which controls the choice of the initial conditions in the kernel of A 2 . Nonsmooth modes described previously do not all have the same period; they differ by a parameter which corresponds to a curve on the roots of det.A 2 /.

Conclusion

The free periodic dynamics of a simple oscillator with two degreesof-freedom undergoing unilateral conditions reflected as a Newton impact law was explored. Its behaviour proved to be extremely rich, dispite its apparent simplicity. A linear mapping A m which governs the existence of periodic solutions was defined for any number of impacts per period m. Continuous families of periodic orbits emerge from this mapping for m D 1 and m D 2

and were used to define the concept of nonsmooth modes of vibration. The frequency of these orbits is driven by the natural frequencies of the underlying linear system. Such modes were illustrated, and open doors to several key improvements in the analysis of nonsmooth systems. For m D 1, the admissibility of these trajectories is controlled by three kinds of transitions: singular, linear modal or grazing. The latter merges solutions with different numbers of impacts per period. This was illustrated for one and two impacts per period but is not fully understood yet. Configurations with m > 3 seem to be only degenerate counterparts of solutions featuring fewer impacts per period.

From preliminary numerical experiments, the results with two degrees-of-freedom extend to larger systems. This sounds promising for a systematic nonsmooth modal analysis, including modal reduction of more challenging nonsmooth systems. Next steps include mathematical proofs of the conjectures presented here as well as stability analyses.

Figure 3 .

 3 Figure 3. Energies of T autonous orbits. [ ] Potential solutions. [ ] Admissible solutions. [ ] Singular transitions.[ ] Linear modal transitions. T S is an example of singular transition. T G is an arbitrary grazing transition used in Fig.5.

2 Figure 4 . 2 Figure 5 .

 2425 Figure 4. Linear modal transition in the neighbourhood of 2T 2 , for 1-ipp. In the left neighbourhood of 2T 1 ([ ] T D 2T 1 "), motion is admissible. In the right neighbourhood ([ ] T D 2T 1 C "), it violates the unilateral constraints (x 2 > d ). The limit case is a modal motion ([ ] T D 2T 1 ).

Figure 7 .

 7 Figure 7. Energies of T -periodic 2-ipp motions as a function of T and the time of second impact t 2 . [ ] Potential solutions. [ ] Admissible solutions.

Fig. 3

 3 Fig. 3 and 7 in a two-dimensional graph: the factor 2 dilation of the admissible soltions in the 1-ipp energy plot along the T axis coincides with some parts of the 2-ipp admissible solutions.

Figure 8 .

 8 Figure 8. Energies for 1-ipp and 2-ipp orbits. [ ] 1-ipp. [ ] 2-ipp. [ ] 2-ipp with t 2 D T =2. The green curve, which is a subpart of the orange curve, is the factor 2 dilated version of the blue curve along the T axis.

Figure 9 .

 9 Figure 9. Trajectory with two grazing points and one impact: admissible solution to both the 1-ipp and 3ipp formulations.

2 Figure 10 .

 210 Figure10. Periodic orbits with one impact per period in the neighbourhood of 2T 1 . These orbits lie on a nonsmooth manifold. [ ] Grazing trajectory of the second linear mode. It is visible that x 2 Ä 1, and that when x 2 D 1, Px 2 is discontinuous.

1 ẋ2Figure 12 .

 112 Figure12. Periodic orbits with two impacts per period in the neighbourhood of 3T 1 . These orbits lie on a nonsmooth manifold. It is visible that x 2 6 1, and that when x 2 D 1, Px 2 is discontinuous. The continuum of orbits is illustrated by the red curve which continuously shades into blue ones.

2 Figure 13 .

 213 Figure 13. Continuum of 2-ipp orbits of period T ([ ], [ ] and [ ]) limited by one 1-ipp solution of period T [ ] and the same 1-ipp solution shifted by T =2 [ ]. The 2-ipp solutions differ by the value of the free parameter which determines Q q.0/ in the kernel of A 2 .

Figure 14 .Figure 15 .

 1415 Figure 14. Periodic orbits in the phase portrait .x 1 ; x 2 ; P x 2 / for a period T such that the transition is grazing: 1-ipp [ ] and 2-ipp [ ] orbits. Grazing solution [ ]. 2-ipp orbits all have the same period T .

Figure 1 .

 1 Model of interest and notations. where x 1 is twice differentiable everywhere in time and x 2 twice differentiable almost everywhere (i.e. everywhere except for t i such that x 2 .t i / D d ) in time. The two quantities P x 2 .t i / and P x 2 .t C

	Nomenclature diagonal matrix of the frequencies 0 n zero matrix of R n n D 1 ; D 2 eigenvectors of M 1 K I n identity matrix of R n n K stiffness matrix M mass matrix N mapping of the pre-impact velocities to the post-impact velocities, on P x P change of basis matrix, in R 2 2 Q N mapping of the pre-impact velocities to the post-impact velocities, on Q x Q S mapping of initial conditions to current state in a free phase q modal coordinates x vector of the displacement x 1 and x 2 (nodal coordinates)	Q q t P x 1 ; P x 2 ! 1 ; ! 2 d e k 1 ; k 2 m m 1 ; m 2 T t T 1 ; T 2 t i x 1 ; x 2 WD	vector of modal coordinates and modal velocities time-step velocities of the masses reaction force of the obstacle on the second mass eigenvalues of M 1 K distance between resting position of second mass and obstacle coefficient of restitution stiffnesses of the springs number of impact(s) per period masses period time modal periods, T i D 2 =! i impact time instant, i 2 f1; : : : ; mg (t 1 D 0 by choice) displacements of the masses equals, by definition
	resting position	k 1 m 1	k 2 m 2 d
	in motion
		x 1 .t/	x 2 .t/

  with x.t / D .x 1 .t / x 2 .t // > . The pairs of eigenvalues and eigenvectors of M 1 K are denoted by .! 1 ; ! 2 / and .D 1 ; D 2 /, respectively. The two corresponding periods are given by T 1 D 2 =! 1 and T 2 D 2 =! 2 . Introducing P D OED > 1 D > 2 and the vector of modal coordinates q.t/ D P 1 x.t /, Eq. (

  Singular transitions They correspond to singularities of A.T /, i.e. solutions T S to ! 2 P 12 P 21 cotan.! 1 T / D ! 1 P 11 P 22 cotan.! 2 T / (23)

! 2 P 12 P 21 cotan.! 1 T / ! 1 P 11 P 22 cotan.! 2 T / 1 B 1 .T / D P 12 P 21 ! 2 = sin.! 1 T =2/ (22) B 2 .T / D P 11 P 22 ! 1 = sin.! 2 T =2/ from which three kinds of distinct transitions from admissible to non-admissible solutions can be found:

  [START_REF] Rosenberg | On nonlinear vibrations of systems with many degrees of freedom[END_REF] . These orbits lie on a nonsmooth manifold. [ ] Grazing trajectory of the second linear mode. It is visible that x 2 Ä 1, and that when x 2 D 1, Px 2 is discontinuous. Figure 11. 2-ipp admissible solutions in the neighbourhood of T D 3T 1 . In red, the solution coincides with the linear mode.Other plots obtained by exploring the branch of admissible solutions for different roots .t 2 ; T / of det A 2 . The continuum of orbits is illustrated by the red curve which continuously shades into blue ones.

		d
						1			2
	x 2	0
		t 2	3:0		T	8:9	t 2	2:9	T	8:9
		d
						3			4
	x 2	0
		t 2	2:6		T	8:7	t 2	2:4	T	8:7
		d
						5			6
	x 2	0
		t 2	1:7		T	8:8	t 2	1:6	T	8:9
		d
						7			8
	x 2	0
		t 2	1:4		T	9:0	t 2	1:1	T	9:1
			T 1	t	2T 1	3T 1		T 1	t	2T 1	3T 1