yes / Highlights: Non-additive probabilities and Choquet integrals in a classical context. The use of Choquet integrals in a quantum context. Approximation of partially known density matrices with Choquet integrals.

We consider the problem of controlling a thermal convection flow by feedback. The system is governed by the Boussinesq approximation of the coupled set of Navier-Stokes and heat equations. The control is applied through Dirichlet boundary conditions. We concentrate on a two-dimensional mode and use a semidiscrete Galerkin scheme for numerical computations. We construct both a linear control and a non-linear quadratic control and apply them to the full non-linear model. First, we test these controllers on a one-mode approximation. The convergence of the numerical scheme is analyzed. We also consider LQR control for a two-dimensional heat equation. / Ph. D.

Geometric trimming of surfaces results in a new mathematical description of the matching surface. This matching surface is required to closely resemble the remaining portion of the original surface. Typically, the approximation error in such cases is measured with a view to minimize it. The data associated with the error between two matching surfaces is large and needs to be filtered into meaningful information.This research looks at suitable norms for achieving this data reduction or abstraction with a view to provide quantitative feedback about the approximation error. Also, the differences between geometric shapes are easily discerned by the human eye but are difficult to characterize or describe. Error visualization tools have been developed to provide effective visual inputs that the designer can interpret into meaningful information. / Master of Science

We propose a dynamic, input dependent filter approximation and selection technique to improve the computational efficiency of Deep Neural Networks. The approximation techniques convert 32 bit floating point representation of filter weights in neural networks into smaller precision values. This is done by reducing the number of bits used to represent the weights. In order to calculate the per-input error between the trained full precision filter weights and the approximated weights, a metric called Multiplication Error (ME) has been chosen. For convolutional layers, ME is calculated by subtracting the approximated filter weights from the original filter weights, convolving the difference with the input and calculating the grand-sum of the resulting matrix. For fully connected layers, ME is calculated by subtracting the approximated filter weights from the original filter weights, performing matrix multiplication between the difference and the input and calculating the grand-sum of the resulting matrix. ME is computed to identify approximated filters in a layer that result in low inference accuracy. In order to maintain the accuracy of the network, these filters weights are replaced with the original full precision weights. Prior work has primarily focused on input independent (static) replacement of filters to low precision weights. In this technique, all the filter weights in the network are replaced by approximated filter weights. This results in a decrease in inference accuracy. The decrease in accuracy is higher for more aggressive approximation techniques. Our proposed technique aims to achieve higher inference accuracy by not approximating filters that generate high ME. Using the proposed per-input filter selection technique, LeNet achieves an accuracy of 95.6% with 3.34% drop from the original accuracy value of 98.9% for truncating to 3 bits for the MNIST dataset. On the other hand upon static filter approximation, LeNet achieves an accuracy of 90.5% with 8.5% drop from the original accuracy. The aim of our research is to potentially use low precision weights in deep learning algorithms to achieve high classification accuracy with less computational overhead. We explore various filter approximation techniques and implement a per-input filter selection and approximation technique that selects the filters to approximate during run-time. / Master of Science / Deep neural networks, just like the human brain can learn important information about the data provided to them and can classify a new input based on the labels corresponding to the provided dataset. Deep learning technology is heavily employed in devices using computer vision, image and video processing and voice detection. The computational overhead incurred in the classification process of DNNs prohibits their use in smaller devices. This research aims to improve network efficiency in deep learning by replacing 32 bit weights in neural networks with less precision weights in an input-dependent manner. Trained neural networks are numerically robust. Different layers develop tolerance to minor variations in network parameters. Therefore, differences induced by low-precision calculations fall well within tolerance limit of the network. However, for aggressive approximation techniques like truncating to 3 and 2 bits, inference accuracy drops severely. We propose a dynamic technique that during run-time, identifies the approximated filters resulting in low inference accuracy for a given input and replaces those filters with the original filters to achieve high inference accuracy. The proposed technique has been tested for image classification on Convolutional Neural Networks. The datasets used are MNIST and CIFAR-10. The Convolutional Neural Networks used are 4-layered CNN, LeNet-5 and AlexNet.

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

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.

Given a set of n points on a plane, in the Minimum Weight Triangulation problem, we wish to find a triangulation that minimizes the sum of Euclidean lengths of its edges. The problem has been studied for more than four decades and is known to be incredibly challenging. In fact, the complexity status of this problem remained open until recently when it was shown to be NP-Hard. We present a novel polynomial-time algorithm that computes a 16-approximation of the minimum weight triangulation---a constant that is significantly smaller than what has been previously known. To construct our candidate solution, our algorithm uses grids to partition edges into levels by increasing weights, so that edges with similar weights appear in the same level. We incrementally triangulate the point set by constructing a growing partial triangulation for each level, introducing edges in increasing order of level. At each level, we use a variant of the ring heuristic followed by a greedy heuristic to add edges, finally resulting in a complete triangulation of the point set. In our analysis, we reduce the problem of comparing the weight of the candidate and the optimal solutions to a comparison between the cardinality of the two underlying graphs. We develop a new technique to compare the cardinality of planar straight-line graphs, and in combination with properties due to the imposed grid structure, we bound the approximation ratio. / Master of Science / Given a set of n points on a plane P, a triangulation of P is a set of edges such that no two edges intersect at a point not in P, and the edges subdivide the convex hull of P into triangles. Triangulations have a variety of applications, including computer graphics, finite element analysis, and interpolation, which motivates the need for efficient algorithms to compute triangulations with desirable qualities. The Minimum Weight Triangulation problem is the problem of computing the triangulation T that minimizes the sum of Euclidean lengths of its edges and performs well in many of the above-mentioned applications. The problem has been studied for more than four decades and is known to be incredibly challenging. In fact, the complexity status of this problem remained open until recently when it was shown to be NP-Hard. We present a novel polynomial-time algorithm that computes a 16-approximation of the minimum weight triangulation—a constant that is significantly smaller than what has been previously known. The algorithm makes use of grids together with a variant of the ring and greedy heuristic adapted to apply in a new setting, resulting in an elegant, efficient algorithm.

This work investigates modeling, approximation, estimation, and control for classes of nonlinear systems whose state evolves in space $mathbb{R}^n times H$, where $mathbb{R}^n$ is a n-dimensional Euclidean space and $H$ is a infinite dimensional Hilbert space. Specifically, two classes of nonlinear systems are studied in this dissertation. The first topic develops a novel framework for adaptive estimation of nonlinear systems using reproducing kernel Hilbert spaces. A nonlinear adaptive estimation problem is cast as a time-varying estimation problem in $mathbb{R}^d times H$. In contrast to most conventional strategies for ODEs, the approach here embeds the estimate of the unknown nonlinear function appearing in the plant in a reproducing kernel Hilbert space (RKHS), $H$. Furthermore, the well-posedness of the framework in the new formulation is established. We derive the sufficient conditions for existence, uniqueness, and stability of an infinite dimensional adaptive estimation problem. A condition for persistence of excitation in a RKHS in terms of an evaluation functional is introduced to establish the convergence of finite dimensional approximations of the unknown function in RKHS. Lastly, a numerical validation of this framework is presented, which could have potential applications in terrain mapping algorithms. The second topic delves into estimation and control of history dependent differential equations. This study is motivated by the increasing interest in estimation and control techniques for robotic systems whose governing equations include history dependent nonlinearities. The governing dynamics are modeled using a specific form of functional differential equations. The class of history dependent differential equations in this work is constructed using integral operators that depend on distributed parameters. Consequently, the resulting estimation and control equations define a distributed parameter system whose state, and distributed parameters evolve in finite and infinite dimensional spaces, respectively. The well-posedness of the governing equations is established by deriving sufficient conditions for existence, uniqueness and stability for the class of functional differential equations. The error estimates for multiwavelet approximation of such history dependent operators are derived. These estimates help determine the rate of convergence of finite dimensional approximations of the online estimation equations to the infinite dimensional solution of distributed parameter system. At last, we present the adaptive sliding mode control strategy developed for the history dependent functional differential equations and numerically validate the results on a simplified pitch-plunge wing model. / Ph. D. / This dissertation aims to contribute towards our understanding of certain classes of estimation and control problems that arise in applications where the governing dynamics are modeled using nonlinear ordinary differential equations and certain functional differential equations. A common theme throughout this dissertation is to leverage ideas from approximation theory to extend the conventional adaptive estimation and control frameworks. The first topic develops a novel framework for adaptive estimation of nonlinear systems using reproducing kernel Hilbert spaces. The numerical validation of the framework presented has potential applications in terrain mapping algorithms. The second topic delves into estimation and control of history dependent differential equations. This study is motivated by the increasing interest in estimation and control techniques for robotic systems whose governing equations include history dependent nonlinearities.

We consider questions involving two different variations of Schmidt's game: the rho game and the HAW (Hyperplane Absolutely Winning) game.

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