Dynamical systems are mathematical models characterized by a set of differential or difference equations. Due to the increasing demand for more accuracy, the number of equations involved may reach the order of thousands and even millions. With so many equations, it often becomes computationally cumbersome to work with these large-scale dynamical systems. Model reduction aims to replace the original system with a reduced system of significantly smaller dimension which will still describe the important dynamics of the large-scale model. Interpolation is one method used to obtain the reduced order model. This requires that the reduced order model interpolates the full order model at selected interpolation points. Reduced order models are obtained through the Krylov reduction process, which involves solving a sequence of linear systems. The Iterative Rational Krylov Algorithm (IRKA) iterates this Krylov reduction process to obtain an optimal Η₂ reduced model. Especially in the large-scale setting, these linear systems often require employing inexact solves. The aim of this thesis is to investigate the impact of inexact solves on interpolatory model reduction. We considered preconditioning the linear systems, varying the stopping tolerances, employing GMRES and BiCG as the inexact solvers, and using different initial shift selections. For just one step of Krylov reduction, we verified theoretical properties of the interpolation error. Also, we found a linear improvement in the subspace angles between the inexact and exact subspaces provided that a good shift selection was used. For a poor shift selection, these angles often remained of the same order regardless of how accurately the linear systems were solved. These patterns were reflected in Η₂ and Η∞ errors between the inexact and exact subspaces, since these errors improved linearly with a good shift selection and were typically of the same order with a poor shift. We found that the shift selection also influenced the overall model reduction error between the full model and inexact model as these error norms were often several orders larger when a poor shift selection was used. For a given shift selection, the overall model reduction error typically remained of the same order for tolerances smaller than 1 x 10^-3, which suggests that larger tolerances for the inexact solver may be used without necessarily augmenting the model reduction error. With preconditioned linear systems as well as BiCG, we found smaller errors between the inexact and exact models while the order of the overall model reduction error remained the same. With IRKA, we observed similar patterns as with just one step of Krylov reduction. However, we also found additional benefits associated with using an initial guess in the inexact solve and by varying the tolerance of the inexact solve. / Master of Science

For parameter inversion problems governed by systems of partial differential equations, such as those arising in Diffuse Optical Tomography (DOT), even the cost of repeated objective function evaluation can be overwhelming. Despite the linear (in the state variable) nature of the DOT problem, the nonlinear parameter inversion process is dominated by the computational burden of solving a large linear system for each source and frequency. To compute the Jacobian for use in Newton-type methods, an adjoint solve is required for each detector and frequency. When a three-dimensional tomography problem may have nearly 1,000 sources and detectors, the computational cost of an optimization routine is a large burden. While techniques from model order reduction can partially alleviate the computational cost, obtaining error bounds in parameter space is typically not feasible. In this work, we examine two different remedies based on stochastic estimates of the objective function. In the first manuscript, we focus on maximizing the efficiency of using stochastic estimates by replacing our objective function with a surrogate objective function computed from a reduced order model (ROM). We use as few as a single sample to detect a misfit between the full-order and surrogate objective functions. Once a sufficiently large difference is detected, it is necessary to update the ROM to reduce the error. We propose a new technique for improving the ROM with very few large linear solutions. Using this techniques, we observe a reduction of up to 98% in the number of large linear solutions for a three-dimensional tomography problem. In the second manuscript, we focus on establishing a robust algorithm. We propose a new trust region framework that replaces the objective function evaluations with stochastic estimates of the improvement factor and the misfit between the model and objective function gradients. If these estimates satisfy a fixed multiplicative error bound with a high, but fixed, probability, we show that this framework converges almost surely to a stationary point of the objective function. We derive suitable bounds for the DOT problem and present results illustrating the robust nature of these estimates with only 10 samples per iteration. / Doctor of Philosophy / For problems such as medical imaging, the process of reconstructing the state of a system from measurement data can be very expensive to compute. The ever increasing need for high accuracy requires very large models to be used. Reducing the computational burden by replacing the model with a specially constructed smaller model is an established and effective technique. However, it can be difficult to determine how well the smaller model matches the original model. In this thesis, we examine two techniques for estimating the quality of a smaller model based on randomized combinations of sources and detectors. The first technique focuses on reducing the computational cost as much as possible. With the equivalent of a single randomized source, we show that this estimate is an effective measure of the model quality. Coupled with a new technique for improving the smaller model, we demonstrate a highly efficient and robust method. The second technique prioritizes robustness in its algorithm. The algorithm uses these randomized combinations to estimate how the observations change for different system states. If these estimates are accurate with a high probability, we show that this leads to a method that always finds a minimum misfit between predicted values and the observed data.

When applying optimization techniques to complex physical systems, using very large numerical models for the solution of a system of parameter dependent partial differential equations (PDEs) is usually intractable. Surrogate models are used to provide an approximation to the high fidelity models while being computationally cheaper to evaluate. Typically, for time dependent nonlinear problems a reduced order model is built using a basis obtained through proper orthogonal decomposition (POD) and Galerkin projection of the system dynamics. In this thesis we present theoretical and numerical results for parameter dependent model reduction techniques. The methods are motivated by the need for surrogate models specifically designed for nonlinear parameter dependent systems. We focus on methods in which the projection basis also depends on the parameter through extrapolation and interpolation. Numerical examples involving 1D Burgers' equation, 2D Navier-Stokes equations and 2D Boussinesq equations are presented. For each model problem comparison to traditional POD reduced order models will also be presented. / Ph. D.

Dynamical systems and their numerical simulation are very important for investigating physical and technical problems. The more accuracy is desired, the more equations are needed to reach the desired level of accuracy. This leads to large-scale dynamical systems. The problem is that computations become infeasible due to the limitations on time and/or memory in large-scale settings. Another important issue is numerical ill-conditioning. These are the main reasons for the need of model reduction, i.e. replacing the original system by a reduced system of much smaller dimension. Then one uses the reduced models in order to simulate or control processes. The main goal of this thesis is to investigate an interpolation-based approach to the weighted-H2 model reduction problem. Nonetheless, first we will discuss the regular (unweighted) H2 model reduction problem. We will re-visit the interpolation conditions for H2-optimality, also known as Meier-Luenberger conditions, and discuss how to obtain an optimal reduced order system via projection. After having introduced the H2-norm and the unweighted-H2 model reduction problem, we will introduce the weighted-H2 model reduction problem. We will first derive a new error expression for the weighted-H2 model reduction problem. This error expression illustrates the significance of interpolation at the mirror images of the reduced system poles and the original system poles, as in the unweighted case. However, in the weighted case this expression yields that interpolation at the mirror images of the poles of the weighting system is also significant. Finally, based on the new weighted-H2 error expression, we will propose an iteratively corrected interpolation-based algorithm for the weighted-H2 model reduction problem. Moreover we will present new optimality conditions for the weighted-H2 approximation. These conditions occur as structured orthogonality conditions similar to those for the unweighted case which were derived by Antoulas, Beattie and Gugercin. We present several numerical examples to illustrate the effectiveness of the proposed approach and compare it with the frequency-weighted balanced truncation method. We observe that, for virtually all of our numerical examples, the proposed method outperforms the frequency-weighted balanced truncation method. / Master of Science

Dynamical systems are widely used to model physical phenomena and, in many cases, these physical phenomena are parameter dependent. In this thesis we investigate three prominent problems related to the simulation of parametric dynamical systems and develop the analysis and computational framework to solve each of them. In many cases we have access to data resulting from simulations of a parametric dynamical system for which an explicit description may not be available. We introduce the parametric AAA (p-AAA) algorithm that builds a rational approximation of the underlying parametric dynamical system from its input/output measurements, in the form of transfer function evaluations. Our algorithm generalizes the AAA algorithm, a popular method for the rational approximation of nonparametric systems, to the parametric case. We develop p-AAA for both scalar and matrix-valued data and study the impact of parameter scaling. Even though we present p-AAA with parametric dynamical systems in mind, the ideas can be applied to parametric stationary problems as well, and we include such examples. The solution of a dynamical system can often be expressed in terms of an eigenvalue problem (EVP). In many cases, the resulting EVP is nonlinear and depends on a parameter. A common approach to solving (nonparametric) nonlinear EVPs is to approximate them with a rational EVP and then to linearize this approximation. An existing algorithm can then be applied to find the eigenvalues of this linearization. The AAA algorithm has been successfully applied to this scheme for the nonparametric case. We generalize this approach by using our p-AAA algorithm to find a rational approximation of parametric nonlinear EVPs. We define a corresponding linearization that fits the format of the compact rational Krylov (CORK) algorithm for the approximation of eigenvalues. The simulation of dynamical systems may be costly, since the need for accuracy may yield a system of very large dimension. This cost is magnified in the case of parametric dynamical systems, since one may be interested in simulations for many parameter values. Interpolatory model order reduction (MOR) tackles this problem by creating a surrogate model that interpolates the original, is of much smaller dimension, and captures the dynamics of the quantities of interest well. We generalize interpolatory projection MOR methods from parametric linear to parametric bilinear systems. We provide necessary subspace conditions to guarantee interpolation of the subsystems and their first and second derivatives, including the parameter gradients and Hessians. Throughout the dissertation, the analysis is illustrated via various benchmark numerical examples. / Doctor of Philosophy / Simulation of mathematical models plays an important role in the development of science. There is a wide range of models and approaches that depend on the information available and the goal of the problem. In this dissertation we focus on three problems whose solution depends on parameters and for which we have either data resulting from simulations of the model or a explicit structure that describes the model. First, for the case when only data are available, we develop an algorithm that builds a data-driven approximation that is then easy to reevaluate. Second, we embed our algorithm in an already developed framework for the solution of a specific kind of model structure: nonlinear eigenvalue problems. Third, given a model with a specific nonlinear structure, we develop a method to build a model with the same structure, smaller dimension (for faster computation), and that provides an accurate approximation of the original model.

De nos jours, les évolutions technologiques imposent aux ingénieurs de modéliser desphénomènes toujours plus multiphysiques et complexes tout au long du processus dedéveloppement d’un système : le cycle en V. Pour cela, il est primordial d’avoir à disposition desoutils adaptés et performants, afin de réduire les temps de mise sur le marché, tout en obtenantdes produits plus matures et plus économes en énergie. Les travaux présentés ici décrivent lamise en place d’une plate-forme de prototypage virtuel et l’intérêt d’intégrer des considérationsénergétiques dans toutes les étapes de la modélisation. Cette approche permet, par exemple, dequantifier l’efficacité d’un système et de ses composants, et donc d’optimiser au plus tôt le coûténergétique d’une solution technique. Nous avons, dans un second temps, souhaité répondre àla problématique du « modèle le plus adapté ». Après analyse des différentes méthodes deréduction de modèles, nous avons décidé de développer la méthode PEMRA permettant depallier les limitations de la méthode MORA, introduite par Louca et al. en 1997. Les variables depuissance et d’énergie introduites précédemment sont utilisées pour calculer deux nouveauxcritères dans le processus de réduction de modèles, permettant de converger vers un modèleréduit plus simple et plus précis qu’avec la méthode MORA. Nous montrons enfin qu’enchoisissant judicieusement le signal d’excitation et un critère dit de précision temporelle adapté, ilest possible, par une approche innovante à la fois énergétique et fréquentielle, de trouver unmodèle réduit mieux adapté aux exigences imposées par l’utilisateur. / Nowadays, technological evolutions are leading engineers to model increasingly multiphysic andcomplex phenomena throughout the systems design process: the V-cycle. Adapted and efficientsystems design tools are therefore necessary in order to reduce time-to-market, while stillensuring fully developed and energy-saving products. First, this work describes the set-up of avirtual prototyping platform and highlights the interest of integrating energetic aspects in allmodelling stages. For example, this approach enables to quantify the system and components’efficiency, and therefore to optimise earlier in the process the energy consumption of a technicalsolution. Secondly, the problematic of the “Proper Model” has been addressed. After the study ofthe model reduction methodologies, we decide to develop PEMRA in order to compensate forlimitations of the MORA methodology, introduced by Louca et al. in 1997. The previous powerand energy variables are then used to compute two new model reduction criteria, in order toobtain a simpler and more accurate reduced model than with MORA methodology. Finally, weshow that a well-defined excitation signal and a new adapted temporal validation criterion willlead, with this innovative energy- and frequency-based approach, to a better suited reducedmodel.

Miniaturisation of electronic chips poses challenges at the design stage. The progressively decreasing circuit dimensions result in complex electrical behaviour that necessitates complex models. Simulation of complex circuit models involves extraordinarily large compu- tational complexity. Such complexity is better managed through Model Order Reduction. Model order reduction has been successful in large reductions in system order for most types of circuits, at high levels of accuracy. However, multiport circuits with large number of inputs/outputs, pose an additional computational challenge. A strategy based on exible clustering of interconnects results in more e cient reduction of multiport circuits. Clustering methods traditionally use Krylov-subspace methods such as PRIMA for the actual model reduction step. These clustering methods are unable to reduce the model order to the optimum extent. SVD-based methods like Truncated Balanced Realization have shown higher reduction potential than Krylov-subspace methods. In this thesis, the di erences in reduction potential and computational cost thereof between SVD-based methods and Krylov-subspace methods are identi ed, analyzed and quanti ed. A novel algorithm has been developed, utilizing a particular combination of both these methods to achieve better results. It enhances the clustering method for model reduction using Truncated Balanced Realization as a second-level reduction technique. The algorithm is tested and signi cant gains are illustrated. The proposed novel algorithm preserves the other advantages of the current clustering algorithm.

La simulation numérique est de plus en plus utilisée dans l’industrie pour réduire le coût lié aux essais physiques. Une simulation de crash (préparation + soumission au solveur + traitement) dure environ une à deux journées. Renault utilise l’optimisation, donc de nombreuses simulations de crash, pour dimensionner ses véhicules. Afin de réduire le coût total d’un ensemble de simulations crash, le but de cette thèse est de proposer une ou des méthodes de réduction de modèle applicables dans un espace paramétrique. Les méthodes proposées dans cette thèse sont non-intrusives et n’obligent donc pas à modifier le solveur ni le modèle. La première méthode testée est la Proper Orthogonal Decomposition. Elle permet de réduire le comportement d’une simulation et de comprendre les propriétés du crash mais l’interpolation dans l’espace paramétrique est plus difficile. La deuxième méthode, ReCUR, est une variante de la décomposition CUR classique. Elle sera montrée comme une forme générale des méthodes non-intrusives. Elle permet de surmonter les deux limites importantes des méthodes de réduction actuelles : taille du modèle élevée et interpolation. / The numerical simulation is more and more applied in the industry in order to reduce the physical tests costs. A crash simulation (pre-processing, processing and post-processing) takes about one or two days. Renault uses the optimization, so numerous crash simulations, to size cars. To cut back the total cost of a whole crash simulations, the aim of this thesis is to propose a or some Reduced-Order Model (ROM) methods that can be applied in a parametric space. The suggested methods in this thesis are nonintrusive and neither the solver nor the model should not be modified . The first tested method is the Proper Orthogonal Decomposition. This method allows reducing the behavior of a crash simulation and understanding the crash properties but not interpolating in a parametric space. The second method, ReCUR, is a variant of the classical decomposition CUR. It will be demonstrated as a general form of the non-intrusive methods. It allows overcoming two important limits of actual ROM methods : size of the model and the interpolation.

In this thesis, different topics for models that consist of both differential and algebraic equations are studied. The interest in such models, denoted DAE models, have increased substantially during the last years. One of the major reasons is that several modern object-oriented modeling tools used to model large physical systems yield models in this form. The DAE models will, at least locally, be assumed to be described by a decoupled set of ordinary differential equations and purely algebraic equations. In theory, this assumption is not very restrictive because index reduction techniques can be used to rewrite rather general DAE models to satisfy this assumption. One of the topics considered in this thesis is optimal feedback control. For state-space models, it is well-known that the Hamilton-Jacobi-Bellman equation (HJB) can be used to calculate the optimal solution. For DAE models, a similar result exists where a Hamilton-Jacobi-Bellman-like equation is solved. This equation has an extra term in order to incorporate the algebraic equations, and it is investigated how the extra term must be chosen in order to obtain the same solution from the different equations. A problem when using the HJB to find the optimal feedback law is that it involves solving a nonlinear partial differential equation. Often, this equation cannot be solved explicitly. An easier problem is to compute a locally optimal feedback law. For analytic nonlinear time-invariant state-space models, this problem was solved in the 1960's, and in the 1970's the time-varying case was solved as well. In both cases, the optimal solution is described by convergent power series. In this thesis, both of these results are extended to analytic DAE models. Usually, the power series solution of the optimal feedback control problem consists of an infinite number of terms. In practice, an approximation with a finite number of terms is used. A problem is that for certain problems, the region in which the approximate solution is accurate may be small. Therefore, another parametrization of the optimal solution, namely rational functions, is studied. It is shown that for some problems, this parametrization gives a substantially better result than the power series approximation in terms of approximating the optimal cost over a larger region. A problem with the power series method is that the computational complexity grows rapidly both in the number of states and in the order of approximation. However, for DAE models where the underlying state-space model is control-affine, the computations can be simplified. Therefore, conditions under which this property holds are derived. Another major topic considered is how to include stochastic processes in nonlinear DAE models. Stochastic processes are used to model uncertainties and noise in physical processes, and are often an important part in for example state estimation. Therefore, conditions are presented under which noise can be introduced in a DAE model such that it becomes well-posed. For well-posed models, it is then discussed how particle filters can be implemented for estimating the time-varying variables in the model. The final topic in the thesis is model reduction of nonlinear DAE models. The objective with model reduction is to reduce the number of states, while not affecting the input-output behavior too much. Three different approaches are studied, namely balanced truncation, balanced truncation using minimization of the co-observability function and balanced residualization. To compute the reduced model for the different approaches, a method originally derived for nonlinear state-space models is extended to DAE models.

Solutions to physical problems described by Differential Equationson complex domains are in except for special cases almost impossibleto find. This turns our interest toward numerical approaches. Sincethe size of the numerical models tends to be very large when handlingcomplex problems, the area of model reduction is always a hot topic. Inthis report we look into a model reduction method called ComponentMode Synthesis. This can be described as dividing a large and complexdomain into smaller and more manageable ones. On each of thesesubdomains, we solve an eigenvalue problem and use the eigenvectorsas a reduced basis. Depending on the required accuracy we mightwant to use many or few modes in each subdomain, this opens for anadaptive selection of which subdomains that affects the solution most.We cover two numerical examples where we solve Helmholtz equationin a linear elastic problem. The first example is a truss and the othera gear wheel. In both examples we use an adaptive algorithm to refinethe reduced basis and compare the results with a uniform refinementand with a classic model reduction method called Modal Analysis. Wealso introduce a new approach when computing the coupling modesonly on the adjacent subdomains.