The object of this thesis is the study of the decidability properties of linear dynamical systems, which have fundamental ties to theoretical computer science, software verification, linear hybrid systems, and control theory. In particular, we describe a method for deciding the termination of simple linear loops, partly solving a 10-year-old open problem of Tiwari (2004) and Braverman (2006). We also study the membership problem for semigroups of matrix exponentials, which we show to be undecidable in general by reduction from Hilbert's Tenth Problem, and decidable for all instances where the matrices defining the semigroup commute. In turn, this entails the undecidability of the generalised versions of the Continuous Orbit and Skolem Problems to a multi-matrix setting. We also study point-to-point controllability for linear time-invariant systems, which is a central problem in control theory. For discrete-time systems, we show that this problem is undecidable when the set of controls is non-convex, and at least as hard as the Skolem Problem even when it is a convex polytope; for continuous-time systems, we show that this problem reduces to the Continuous Orbit Problem when the set of controls is a linear subspace, which entails decidability. Finally, we show how to decide whether all solutions of a given linear ordinary differential equation starting in a given convex polytope eventually leave it; this problem, which we call the "Polytope Escape Problem'', relates to the liveness of states in linear hybrid automata. Our results rely on a number of theorems from number theory, logic, and algebra, which we introduce in a self-contained way in the preamble to this thesis, together with a few new mathematical results of independent interest.

Hypothesis-free learning is increasingly popular given the large amounts of data becoming available. Structure learning, a hypothesis-free approach, of graphical models is a field of growing interest due to the power of such models and lack of domain knowledge when applied on complex real-world data. State-of-the-art techniques improve on scalability of structure learning, which is often characterized by a large problem space. Nonetheless, these techniques still suffer computational bottlenecks that are yet to be approached. In this work, we focus on two popular models: dynamical linear systems and Markov random fields. For each case, we investigate major computational bottlenecks of baseline learning techniques. Next, we propose two frameworks that provide higher scalability using appropriate problem reformulation and efficient structure based heuristics. We perform experiments on synthetic and real data to validate our theoretical analysis. Current results show that we obtain a quality similar to expensive baseline techniques but with higher scalability. / Master of Science / Structure learning of graphical models is the process of understanding the interactions and influence between the variables of a given system. A few examples of such systems are road traffic systems, stock markets, and social networks. Learning the structure uncovers the invisible inter-variables relationships that govern their evolution. This process is key to qualitative analysis and forecasting. A classic approach to obtain the structure is through domain experts. For example, a financial expert could draw a graphical structure that encodes the relationships between different software companies based on his knowledge in the field. However, the absence of domain experts in the case of complex and heterogeneous systems has been a great motivation for the field of data driven, hypothesis free structure learning. Current techniques produce good results but unfortunately require a high computational cost and are often slow to execute. In this work, we focus on two popular graphical models that require computationally expensive structure learning methods. We first propose theoretical analysis of the high computational cost of current techniques. Next, we propose a novel approach for each model. Our proposed methods perform structure learning faster than baseline methods and provide a higher scalability to systems of large number of variables and large datasets as shown in our theoretical analysis and experimental results.

We provide a unifying projection-based framework for structure-preserving interpolatory model reduction of parameterized linear dynamical systems, i.e., systems having a structured dependence on parameters that we wish to retain in the reduced-order model. The parameter dependence may be linear or nonlinear and is retained in the reduced-order model. Moreover, we are able to give conditions under which the gradient and Hessian of the system response with respect to the system parameters is matched in the reduced-order model. We provide a systematic approach built on established interpolatory $\mathcal{H}_2$ optimal model reduction methods that will produce parameterized reduced-order models having high fidelity throughout a parameter range of interest. For single input/single output systems with parameters in the input/output maps, we provide reduced-order models that are \emph{optimal} with respect to an $\mathcal{H}_2\otimes\mathcal{L}_2$ joint error measure. The capabilities of these approaches are illustrated by several numerical examples from technical applications.

We provide a unifying projection-based framework for structure-preserving interpolatory model reduction of parameterized linear dynamical systems, i.e., systems having a structured dependence on parameters that we wish to retain in the reduced-order model. The parameter dependence may be linear or nonlinear and is retained in the reduced-order model. Moreover, we are able to give conditions under which the gradient and Hessian of the system response with respect to the system parameters is matched in the reduced-order model. We provide a systematic approach built on established interpolatory $\mathcal{H}_2$ optimal model reduction methods that will produce parameterized reduced-order models having high fidelity throughout a parameter range of interest. For single input/single output systems with parameters in the input/output maps, we provide reduced-order models that are \emph{optimal} with respect to an $\mathcal{H}_2\otimes\mathcal{L}_2$ joint error measure. The capabilities of these approaches are illustrated by several numerical examples from technical applications.

Cette étude traite de l’identification de système dynamique non-linéaire. Une architecture multimodèle capable de surmonter certaines difficultés de l’architecture neuronale de type MLP a été étudiée. L’approche multimodèle consiste à représenter un système complexe par un ensemble de modèles de structures simples à validité limitée dans des zones bien définies. A la place de la structure affine des modèles locaux généralement utilisée, cette étude propose une structure polynômiale plus générale, capable de mieux appréhender les non-linéarités locales, réduisant ainsi le nombre de modèles locaux. L’estimation paramétrique d’une telle architecture multimodèle peut se faire suivant une optimisation linéaire, moins coûteuse en temps de calcul que l’estimation paramétrique utilisée dans une architecture neuronale. L’implantation des multimodèles récurrents, avec un algorithme d’estimation paramétrique plus souple que l’algorithme de rétro-propagation du gradient à travers le temps utilisé pour le MLP récurrent a également été effectuée. Cette architecture multimodèle permet de représenter plus facilement des modèles non-linéaires bouclés tels que les modèles NARMAX et NOE. La détermination du nombre de modèles locaux dans une architecture multimodèle nécessite la décomposition (le partitionnement) de l’espace de fonctionnement du système en plusieurs sous-espaces où sont définies les modèles locaux. Des modes de partitionnement flou (basé sur les algorithmes de« fuzzy-c-means », de « Gustafson et Kessel » et du « subtractive clustering ») ont été présentés. L’utilisation de telles méthodes nécessite l’implantation d’une architecture multimodèle où les modèles locaux peuvent être de structures différentes : polynômiales de degrés différents, neuronale ou polynômiale et neuronale. Une architecture multimodèle hétérogène répondant à ses exigences a été proposée, des algorithmes d’identification structurelles et paramétriques ont été présentés. Une étude comparative entre les architectures MLP et multimodèle a été menée. Le principal atout de l’architecture multimodèle par rapport à l’architecture neuronale de type MLP est la simplicité de l’estimation paramétrique. Par ailleurs, l’utilisation dans une architecture multimodèle d’un mode de partitionnement basé sur la classification floue permet de déterminer facilement le nombre de modèles locaux, alors que la détermination du nombre de neurones cachés pour une architecture MLP reste une tâche difficile / This work deals with non linear dynamical system identification. A multiple model architecture which overcomes certain insufficiencies of MLP neural networks is studied. Multiple model approach consists of modeling complex systems by mean of a set of simple local models whose validity are limited in well defined zones. Instead of using conventional affine models, a more general polynomial structure is proposed in this study, enabling to better apprehend local non linearities, reducing thus the number of local models. Models parameters of such a structure are estimated by linear optimization, which reduces computation time with respect to parameter estimation of a neural network architecture. The implementation of recurrent multiple models, with a more convenient learning algorithm than the back propagation through time, used in recurrent MLP models, is also studied. Such implementations facilitate representation of recurrent models like NARMAX and NOE. The determination of the number of local models in a multiple model architecture requires decomposition of system’s feature space into several sub-systems in which local models are defined. Fuzzy partitioning methods (based of « fuzzy-c-means », « Gustafson and Kessel » and « subtractive clustering »algorithms) are presented. The use of such methods requires the implementation of a multiple model architecture where local models can have different structures : polynomial with different degrees, neural or polynomial and neural. A multiple model with a heterogeneous architecture satisfying these requirements is proposed and structural and parametrical identification algorithms are presented. A comparative study between multiple model and MLP architectures is done. The main advantage of the multiple model architecture is the parameter estimation simplicity. In addition, the use of fuzzy partitioning methods in multiple model architecture enables to find easily the number of local models while the determination of hidden neurons in an MLP architecture remains a hard task

Time series data arise in many applications, from motion capture, environmental monitoring, temperatures in data centers, to physiological signals in health care. In the thesis, I will focus on the theme of learning and mining large collections of co-evolving sequences, with the goal of developing fast algorithms for finding patterns, summarization, and anomalies. In particular, this thesis will answer the following recurring challenges for time series: 1. Forecasting and imputation: How to do forecasting and to recover missing values in time series data? 2. Pattern discovery and summarization: How to identify the patterns in the time sequences that would facilitate further mining tasks such as compression, segmentation and anomaly detection? 3. Similarity and feature extraction: How to extract compact and meaningful features from multiple co-evolving sequences that will enable better clustering and similarity queries of time series? 4. Scale up: How to handle large data sets on modern computing hardware? We develop models to mine time series with missing values, to extract compact representation from time sequences, to segment the sequences, and to do forecasting. For large scale data, we propose algorithms for learning time series models, in particular, including Linear Dynamical Systems (LDS) and Hidden Markov Models (HMM). We also develop a distributed algorithm for finding patterns in large web-click streams. Our thesis will present special models and algorithms that incorporate domain knowledge. For motion capture, we will describe the natural motion stitching and occlusion filling for human motion. In particular, we provide a metric for evaluating the naturalness of motion stitching, based which we choose the best stitching. Thanks to domain knowledge (body structure and bone lengths), our algorithm is capable of recovering occlusions in mocap sequences, better in accuracy and longer in missing period. We also develop an algorithm for forecasting thermal conditions in a warehouse-sized data center. The forecast will help us control and manage the data center in a energy-efficient way, which can save a significant percentage of electric power consumption in data centers.

No description available.

Les applications utilisant les procédés de fabrication directe par laser et projection de poudre sont en pleine expansion, en particulier, dans l'aéronautique. Néanmoins, cette technologie prometteuse fait état de quelques points durs et est confrontée aux problèmes d'instabilités du procédé. Lorsque ces phénomènes ne sont pas maîtrisés, cela conduit à des défauts (résistances mécaniques insuffisantes, porosités trop importantes, mauvais états de surface,….etc), qui, selon leur répartition et leur taille, risquent d'engendrer des non conformités, de détériorer les caractéristiques mécaniques des pièces et qui peuvent représenter un coût de post-traitement non négligeable. Par conséquent, il est primordial de maîtriser le procédé d'élaboration, afin de rendre le procédé de fabrication robuste et préserver l'intégrité structurelle de la pièce. Cela requiert la mise en place de système d'instrumentation du procède de projection laser, et par l'intermédiaire du contrôle procédé, d'avoir un système de commande temps réel permettant d'adapter les paramètres procédés en cours d'élaboration, afin de de maintenir une haute qualité de la pièce fabriquée. Dans cette perspective, nous avons développé une solution technologique (matérielle et algorithmique) à base de caméras (vision) permettant de suivre des paramètres clefs lors de la fabrication. L'application de ce système de vision a permis la mise en œuvre de méthodes innovantes, utilisant des outils de l'automatique moderne, pour surveiller l'état de pièces projetées, voire même corriger leurs défauts lors de la fabrication, en ayant un suivi et un contrôle du procédé en temps réel. De plus ce système de vision a permis à partir de mesures effectuées sur les entrées et les sorties du procédé, d'identifié un modèle dynamique qui ont conduit à la réalisation du système de contrôle procédé. / Applications using the direct metal deposition laser process have been expanded rapidly, particularly in aeronautics. However, this promising technology reported some difficult points and faced several problems, mainly the process instability. When these phenomena are not controlled, several defects was obtained (lack of mechanical strength, excessive porosity, poor surface, ... etc.). According to their distribution and size, non-conformity, deteriorate the mechanical characteristics of the parts was recorded and result in a significant cost of post-processing. Therefore, it is important to control the process, to make the process both robust and preserve the structural integrity of the piece. This requires the development of instrumentation through the control process, in order to have a real-time system able to adjust the process parameters to keep a high quality of the manufactured part. In this perspective, the studied thesis developed a technological solution (hardware and algorithms) based on cameras (vision) to monitor key parameters during manufacture. The application of this vision system has been allowed for the implementation of innovative methods by using modern automatic tools to monitor the status of the built part or even correct their defects during the manufacture parts, having a monitoring and process control in real time. Furthermore this vision system performed measurements for the inputs and outputs of the process, matched to a dynamic model that lead to the realization of the process control system.

Le décrochage profond est un cas particulier du décrochage d’un avion, où l'empennage horizontal est entièrement situé dans le sillage décollé de la voilure principale. Le plan perd ainsi son efficacité, ce qui se traduit par une position d'équilibre en tangage stable, à une incidence élevée, dont il est impossible de sortir par une manœuvre simple. L’objectif de cette étude est de caractériser l’aérodynamique associée à ce phénomène et de proposer une procédure d’identification et de récupération. Il est proposé une démarche visant à déterminer la dynamique bidimensionnelle de l’écoulement autour d’une configuration aéronautique de référence. Les coefficients aérodynamiques, obtenus dans une large plage d’incidence, mettent en évidence l’effet de l’interaction entre les profils sur le décrochage, qui impacte principalement le profil aval. L’analyse des champs de vitesse fournit l’étendue et l’évolution axiale des sillages des profils. Un traitement des champs de vitesse par moyennes de phase permet de reconstruire la dynamique temporelle. À partir de ces résultats, un modèle potentiel de forçage de l’écoulement autour du profil aval permet d’expliquer la modification du coefficient de portance imposé par l’interaction. Des simulations numériques de l’écoulement, qui fournissent des champs résolus en temps, permettent de retrouver certaines évolutions expérimentales. L’ensemble des résultats est utilisé, en parallèle à des données issues d’un aéronef réel, dans un modèle de vol longitudinal afin d’analyser le comportement dynamique de l’avion. Des critères permettant d’identifier la dynamique qui conduit à cet équilibre, fournissent une détection précoce de ce dernier. / Deep stall is a specific type of airplane stall, in which the horizontal tail is inside the detached wake of the main wing. The tail loses its efficiency, leading to a stable pitching equilibrium position with a high angle-of-attack, without any easy recovery procedure. The aim of the study is to characterize the aerodynamic associated to that phenomenon in order to propose an identification and recovery procedure. The approach consists in a two-dimensional flow characterization based on an aeronautical reference configuration. Aerodynamic coefficients, obtained for a wide range of angles-of-attack, show the interaction between the airfoils on the stall of the downstream airfoil. The analysis of velocity fields gives the width and the axial development of the airfoils wakes. Phase-averages of velocity fields lead to the synthesis of flow time-development. With these results, a potential model of flow forcing on the downstream airfoil explains the lift coefficient alteration imposed by the interaction. Flow numerical simulations, giving time-resolved fields, provide good accordance with experimental developments .The whole set of results is used, concurrently with real aircraft data, inside a longitudinal flight model in order to analyze the airplane dynamical behavior. Criteria for the identification of the dynamic leading to that equilibrium provide a rapid detection of deep stall and the implementation of a recovery strategy.

This is a literature study, in linear algebra, about positive and nonnegative matrices and their special properties. We say that a matrix or a vector is positive/nonnegative if all of its entries are positive/nonnegative. First, we study some generalities and become acquainted with two types of nonnegative matrices; irreducible and reducible. After exploring their characteristics we investigate and prove the two main theorems of this subject, namely Perron's and Perron-Frobenius' theorem. In short Perron's theorem from 1907 tells us that the spectral radius of a positive matrix is a simple eigenvalue of the matrix and that its eigenvector can be taken to be positive. In 1912, Georg Frobenius generalized Perron's results also to irreducible nonnegative matrices. The two theorems have a wide range of applications in both pure mathematics and practical matters. In real world scenarios, many measurements are nonnegative (length, time, amount, etc.) and so their mathematical formulations often relate to Perron-Frobenius theory. The theory's importance to linear dynamical systems, such as Markov chains, cannot be overstated; it determines when, and to what, an iterative process will converge. This result is in turn the underlying theory for the page-ranking algorithm developed by Google in 1998. We will see examples of all these applications in chapters four and five where we will be particularly interested in different types of Markov chains.  The theory in this thesis can be found in many books. Here, most of the material is gathered from Horn-Johnson [5], Meyer [9] and Shapiro [10]. However, all of the theorems and proofs are formulated in my own way and the examples and illustrations are concocted by myself, unless otherwise noted. / Det här är en litteraturstudie, inom linjär algebra, om positiva och icke-negativa matriser och deras speciella egenskaper. Vi säger att en matris eller en vektor är positiv/icke-negativ om alla dess element är positiva/icke-negativa. Inledningsvis går vi igenom några grundläggande begrepp och bekanta oss med två typer av icke-negativa matriser; irreducibla och reducibla. Efter att vi utforskat deras egenskaper så studerar vi och bevisar ämnets två huvudsatser; Perrons och Perron-Frobenius sats. Kortfattat så säger Perrons sats, från 1907, att spektralradien för en positiv matris är ett simpelt egenvärde till matrisen och att dess egenvektor kan tas positiv. År 1912 så generaliserade Georg Frobenius Perrons resultat till att gälla också för irreducibla icke-negativa matriser.  De två satserna har både många teoretiska och praktiska tillämpningar. Många verkliga scenarios har icke-negativa mått (längd, tid, mängd o.s.v) och därför relaterar dess matematiska formulering till Perron-Frobenius teori. Teorin är betydande även för linjära dynamiska system, såsom Markov-kedjor, eftersom den avgör när, och till vad, en iterativ process konvergerar. Det resultatet är i sin tur den underliggande teorin bakom algoritmen PageRank som utvecklades av Google år 1998. Vi kommer se exempel på alla dessa tillämpningar i kapitel fyra och fem, där vi speciellt intresserar oss för olika typer av Markov-kedjor. Teorin i den här artikeln kan hittas i många böcker. Det mesta av materialet som presenteras här har hämtats från Horn-Johnson [5], Meyer [9] och Shapiro [10]. Däremot är alla satser och bevis formulerade på mitt eget sätt och alla exempel, samt illustrationer, har jag skapat själv, om inget annat sägs.