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.

For a compact, nowhere dense set X in the complex plane, C, define Rp(X) as the closure of the rational functions with poles off X in Lp(X, dA). It is well known that for 1 ≤ p < 2, Rp(X) = Lp(X) . Although density may not be achieved for p > 2, there exists a set X so that Rp(X) = Lp(X) for p up to a given number greater than 2 but not after. Additionally, when p > 2 we shall establish that the support of the annihiliating and representing measures for Rp(X) lies almost everywhere on the set of bounded point evaluations of X.

Let 𝑋 be a compact subset of the complex plane and denote by 𝑅𝑝(𝑋) the closure of rational functions with poles off 𝑋 in the 𝐿𝑝(𝑋) norm. We show that if a point 𝑥0 admits a bounded point derivation on 𝑅𝑝(𝑋) for 𝑝 > 2, then there is an approximate derivative at 𝑥0. We also prove a similar result for higher order bounded point derivations. This extends a result of Wang, which was proven for 𝑅(𝑋), the uniform closure of rational functions with poles off 𝑋. In addition, we show that if a point 𝑥0 admits a bounded point derivation on 𝑅(𝑋) and if 𝑋 contains an interior cone, then the bounded point derivation can be represented by the difference quotient if the limit is taken over a non-tangential ray to 𝑥0. We also extend this result to the case of higher order bounded point derivations. These results were first shown by O'Farrell; however, we prove them constructively by explicitly using the Cauchy integral formula.

A connection is established between uniform rational approximation, and approximation in the mean by polynomials on compact nowhere dense subsets of the complex plane C. Peak points for R(X) and bounded point evaluations for Hp(X, dA), 1 ≤ p < ∞, play a fundamental role.

Cryptosystems are used to provide security in communications and data transmissions. Stream ciphers are private key systems that are often used to transform large volumn data. In order to have security, key streams used in stream ciphers must be fully analyzed so that they do not contain specific patterns, statistical infomation and structures with which attackers are able to quickly recover the entire key streams and then break down the systems. Based on different schemes to generate sequences and different ways to represent them, there are a variety of stream cipher analyses. The most important one is the linear analysis based on linear feedback shift registers (LFSRs) which have been extensively studied since the 1960's. Every sequence over a finite field has a well defined linear complexity. If a sequence has small linear complexity, it can be efficiently recoverd by Berlekamp-Messay algorithm. Therefore, key streams must have large linear complexities. A lot of work have been done to generate and analyze sequences that have large linear complexities. In the early 1990's, Klapper and Goresky discovered feedback with carry shift registers over Z/(p) (p-FCSRS), p is prime. Based on p-FCSRs, they developed a stream cipher analysis that has similar properties to linear analysis. For instance, every sequence over Z/(p) has a well defined p-adic complexity and key streams of small p-adic complexity are not secure for use in stream ciphers. This disstation focuses on stream cipher analysis based on feedback with carry shift registers. The first objective is to develop a stream cipher analysis based on feedback with carry shift registers over Z/(N) (N-FCSRs), N is any integer greater than 1, not necessary prime. The core of the analysis is a new rational approximation algorithm that can be used to efficiently compute rational representations of eventually periodic N-adic sequences. This algorithm is different from that used in $p$-adic sequence analysis which was given by Klapper and Goresky. Their algorithm is a modification of De Weger's rational approximation algorithm. The second objective is to generalize feedback with carry shift register architecture to more general algebraic settings which are called algebraic feedback shift registers (AFSRs). By using algebraic operations and structures on certain rings, we are able to not only construct feedback with carry shift registers, but also develop rational approximation algorithms which create new analyses of stream ciphers. The cryptographic implication of the current work is that any sequences used in stream ciphers must have large N-adic complexities and large AFSR-based complexities as well as large linear complexities.

Dynamical systems are a commonly used and studied tool for simulation, optimization and design. In many applications such as inverse problem, optimal control, shape optimization and uncertainty quantification, those systems typically depend on a parameter. The need for high fidelity in the modeling stage leads to large-scale parametric dynamical systems. Since these models need to be simulated for a variety of parameter values, the computational burden they incur becomes increasingly difficult. To address these issues, parametric reduced models have encountered increased popularity in recent years. We are interested in constructing parametric reduced models that represent the full-order system accurately over a range of parameters. First, we define a global joint error mea- sure in the frequency and parameter domain to assess the accuracy of the reduced model. Then, by assuming a rational form for the reduced model with poles both in the frequency and parameter domain, we derive necessary conditions for an optimal parametric reduced model in this joint error measure. Similar to the nonparametric case, Hermite interpolation conditions at the reflected images of the poles characterize the optimal parametric approxi- mant. This result extends the well-known interpolatory H2 optimality conditions by Meier and Luenberger to the parametric case. We also develop a numerical algorithm to construct locally optimal reduced models. The theory and algorithm are data-driven, in the sense that only function evaluations of the parametric transfer function are required, not access to the internal dynamics of the full model. While this first framework operates on the continuous function level, assuming repeated transfer function evaluations are available, in some cases merely frequency samples might be given without an option to re-evaluate the transfer function at desired points; in other words, the function samples in parameter and frequency are fixed. In this case, we construct a parametric reduced model that minimizes a discretized least-squares error in the finite set of measurements. Towards this goal, we extend Vector Fitting (VF) to the parametric case, solving a global least-squares problem in both frequency and parameter. The output of this approach might lead to a moderate size reduced model. In this case, we perform a post- processing step to reduce the output of the parametric VF approach using H2 optimal model reduction for a special parametrization. The final model inherits the parametric dependence of the intermediate model, but is of smaller order. A special case of a parameter in a dynamical system is a delay in the model equation, e.g., arising from a feedback loop, reaction time, delayed response and various other physical phenomena. Modeling such a delay comes with several challenges for the mathematical formulation, analysis, and solution. We address the issue of transient behavior for scalar delay equations. Besides the choice of an appropriate measure, we analyze the impact of the coefficients of the delay equation on the finite time growth, which can be arbitrary large purely by the influence of the delay. / Ph. D. / Mathematical models play an increasingly important role in the sciences for experimental design, optimization and control. These high fidelity models are often computationally expensive and may require large resources, especially for repeated evaluation. Parametric model reduction offers a remedy by constructing models that are accurate over a range of parameters, and yet are much cheaper to evaluate. An appropriate choice of quality measure and form of the reduced model enable us to characterize these high quality reduced models. Our first contribution is a characterization of optimal parametric reduced models and an efficient implementation to construct them. While this first framework assumes we have access to repeated evaluations of the full model, in some cases merely measurement data might be available. In this case, we construct a parametric model that fits the measurements in a least squares sense. The output of this approach might lead to a moderate size reduced model, which we address with a post-processing step that reduces the model size while maintaining important properties. A special case of a parameter is a delay in the model equation, e.g., arising from a feedback loop, reaction time, delayed response and various other physical phenomena. While asymptotically stable solutions eventually vanish, they might grow large before asymptotic behavior takes over; this leads to the notion of transient behavior, which is our main focus for a simple class of delay equations. Besides the choice of an appropriate measure, we analyze the impact of the structure of the delay equation on the transient growth, which can be arbitrary large purely by the influence of the delay.

Bivariate or multivariate correlated data may be collected on a sample of unit in many applications. When the experimenters concern about the failure times of two related subjects for example paired organs or two chronic diseases, the bivariate binary data is often acquired. This type of data consists of a observation point x and indicators which represent whether the failure times happened before or after the observation point. In this work, the observed bivariate data can be written with the following form {x, £_1=I(X1≤ x), £_2=I(X2≤ x)}.The corresponding optimal design problems for parameter estimation under this type of bivariate data are discussed. For this kind of the multivariate responses with explanatory variables, their marginal distributions may be from different distributions. Copula model is a way to formulate the relationship of these responses, and the association between pairs of responses. Copula models for bivariate binary data are considered useful in practice due to its flexibility. In this dissertation for bivariate binary data, the marginal functions are assumed from exponential or Weibull distributions and two assumptions, independent or correlated, about the joint function between variables are considered. When the bivariate binary data is assumed correlated, the Clayton copula model is used as the joint cumulative distribution function. There are few works addressed the optimal design problems for bivariate binary data with copula models. The D-optimal designs aim at minimizing the volume of the confidence ellipsoid for estimating unknown parameters including the association parameter in bivariate copula models. They are used to determine the best observation points. Moreover, the Ds-optimal designs are mainly used for estimation of the important association parameter in Clayton model. The D- and Ds-optimal designs for the above copula model are found through the general equivalence theorem with numerical algorithm. Under different model assumptions, it is observed that the number of support points for D-optimal designs is at most as the number of model parameters for the numerical results. When the difference between the marginal distributions and the association are significant, the association becomes an influential factor which makes the number of supports gets larger. The performances of estimation based on optimal designs are reasonably well by simulation studies. In survival experiments, the experimenter customarily takes trials at some specific points such as the position of the 25, 50 and 75 percentile of distributions. Hence, we consider the design efficiencies when the design points for trials are at three or four particular percentiles. Although it is common in practice to take trials at several quantile positions, the allocations of the proportion of sample size also have great influence on the experimental results. To use a locally optimal design in practice, the prior information for models or parameters are needed. In case there is not enough prior knowledge about the models or parameters, it would be more flexible to use sequential experiments to obtain information in several stages. Hence with robustness consideration, a sequential procedure is proposed by combining D- and Ds-optimal designs under independent or correlated distribution in different stages of the experiment. The simulation results based on the sequential procedure are compared with those by the one step procedures. When the optimal designs obtained from an incorrect prior parameter values or distributions, those results may have poor efficiencies. The sample mean of estimators and corresponding optimal designs obtained from sequential procedure are close to the true values and the corresponding efficiencies are close to 1. Huster (1989) analyzed the corresponding modeling problems for the paired survival data and applied to the Diabetic Retinopathy Study. Huster (1989) considered the exponential and Weibull distributions as possible marginal distributions and the Clayton model as the joint function for the Diabetic Retinopathy data. This data was conducted by the National Eye Institute to assess the effectiveness of laser photocoagulation in delaying the onset of blindness in patients with diabetic retinopathy. This study can be viewed as a prior experiment and provide the experimenter some useful guidelines for collecting data in future studies. As an application with Diabetic Retinopathy Study, we develop optimal designs to collect suitable data and information for estimating the unknown model parameters. In the second part of this work, the optimal design problems for parameter estimations are considered for the type of proportional data. The nonlinear model, based on Jorgensen (1997) and named the dispersion model, provides a flexible class of non-normal distributions and is considered in this research. It can be applied in binary or count responses, as well as proportional outcomes. For continuous proportional data where responses are confined within the interval (0,1), the simplex dispersion model is considered here. D-optimal designs obtained through the corresponding equivalence theorem and the numerical results are presented. In the development of classical optimal design theory, weighted polynomial regression models with variance functions which depend on the explanatory variable have played an important role. The problem of constructing locally D-optimal designs for simplex dispersion model can be viewed as a weighted polynomial regression model with specific variance function. Due to the complex form of the weight function in the information matrix is considered as a rational function, an approximation of the weight function and the corresponding optimal designs are obtained with different parameters. These optimal designs are compared with those using the original weight function.

Numerical methods based on rational Krylov spaces have become an indispensable tool of scientific computing. In this thesis we study rational Krylov spaces by considering rational Krylov decompositions; matrix relations which, under certain conditions, are associated with these spaces. We investigate the algebraic properties of such decompositions and present an implicit Q theorem for rational Krylov spaces. We derive standard and harmonic Ritz extraction strategies for approximating the eigenpairs of a matrix and for approximating the action of a matrix function onto a vector. While these topics have been considered previously, our approach does not require the last pole to be infinite, which makes the extraction procedure computationally more efficient. Typically, the computationally most expensive component of the rational Arnoldi algorithm for computing a rational Krylov basis is the solution of a large linear system of equations at each iteration. We explore the option of solving several linear systems simultaneously, thus constructing the rational Krylov basis in parallel. If this is not done carefully, the basis being orthogonalized may become poorly conditioned, leading to numerical instabilities in the orthogonalization process. We introduce the new concept of continuation pairs which gives rise to a near-optimal parallelization strategy that allows to control the growth of the condition number of this non orthogonal basis. As a consequence we obtain a more accurate and reliable parallel rational Arnoldi algorithm. The computational benefits are illustrated using our high performance C++ implementation. We develop an iterative algorithm for solving nonlinear rational least squares problems. The difficulty is in finding the poles of a rational function. For this purpose, at each iteration a rational Krylov decomposition is constructed and a modified linear problem is solved in order to relocate the poles to new ones. Our numerical results indicate that the algorithm, called RKFIT, is well suited for model order reduction of linear time invariant dynamical systems and for optimisation problems related to exponential integration. Furthermore, we derive a strategy for the degree reduction of the approximant obtained by RKFIT. The rational function obtained by RKFIT is represented with the aid of a scalar rational Krylov decomposition and an additional coefficient vector. A function represented in this form is called an RKFUN. We develop efficient methods for the evaluation, pole and root finding, and for performing basic arithmetic operations with RKFUNs. Lastly, we discuss RKToolbox, a rational Krylov toolbox for MATLAB, which implements all our algorithms and is freely available from http://rktoolbox.org. RKToolbox also features an extensive guide and a growing number of examples. In particular, most of our numerical experiments are easily reproducible by downloading the toolbox and running the corresponding example files in MATLAB.

De nombreuses méthodes de traitement du signal reposent sur des résultats puissants d'approximation numérique. Un exemple significatif en est l'utilisation de l'approximation de type Chebyshev pour l'élaboration de filtres numériques.En pratique, le caractère fini des formats numériques utilisés en machine entraîne des difficultés supplémentaires pour la conception de filtres numériques (le traitement audio et le traitement d'images sont deux domaines qui utilisent beaucoup le filtrage). La majorité des outils actuels de conception de filtres ne sont pas optimisés et ne certifient pas non plus la correction de leurs résultats. Notre travail se veut un premier pas vers un changement de cette situation.La première partie de la thèse traite de l'étude et du développement de méthodes relevant de la famille Remez/Parks-McClellan pour la résolution de problèmes d'approximation polynomiale de type Chebyshev, en utilisant l'arithmétique virgule-flottante.Ces approches sont très robustes, tant du point de vue du passage à l'échelle que de la qualité numérique, pour l'élaboration de filtres à réponse impulsionnelle finie (RIF).Cela dit, dans le cas des systèmes embarqués par exemple, le format des coefficients du filtre qu'on utilise en pratique est beaucoup plus petit que les formats virgule flottante standard et d'autres approches deviennent nécessaires.Nous proposons une méthode (quasi-)optimale pour traîter ce cas. Elle s'appuie sur l'algorithme LLL et permet de traiter des problèmes de taille bien supérieure à ceux que peuvent traiter les approches exactes. Le résultat est ensuite utilisé dans une couche logicielle qui permet la synthèse de filtres RIF pour des circuits de type FPGA.Les résultats que nous obtenons en sortie sont efficaces en termes de consommation d'énergie et précis. Nous terminons en présentant une étude en cours sur les algorithmes de type Remez pour l'approximation rationnelle. Ce type d'approches peut être utilisé pour construire des filtres à réponse impulsionnelle infinie (RII) par exemple. Nous examinons les difficultés qui limitent leur utilisation en pratique. / The field of signal processing methods and applications frequentlyrelies on powerful results from numerical approximation. One suchexample, at the core of this thesis, is the use of Chebyshev approximationmethods for designing digital filters.In practice, the finite nature of numerical representations adds an extralayer of difficulty to the design problems we wish to address using digitalfilters (audio and image processing being two domains which rely heavilyon filtering operations). Most of the current mainstream tools for thisjob are neither optimized, nor do they provide certificates of correctness.We wish to change this, with some of the groundwork being laid by thepresent work.The first part of the thesis deals with the study and development ofRemez/Parks-McClellan-type methods for solving weighted polynomialapproximation problems in floating-point arithmetic. They are veryscalable and numerically accurate in addressing finite impulse response(FIR) design problems. However, in embedded and power hungry settings,the format of the filter coefficients uses a small number of bits andother methods are needed. We propose a (quasi-)optimal approach basedon the LLL algorithm which is more tractable than exact approaches.We then proceed to integrate these aforementioned tools in a softwarestack for FIR filter synthesis on FPGA targets. The results obtainedare both resource consumption efficient and possess guaranteed accuracyproperties. In the end, we present an ongoing study on Remez-type algorithmsfor rational approximation problems (which can be used for infinite impulseresponse (IIR) filter design) and the difficulties hindering their robustness.

Submitted by (lucia.rodrigues@ufrpe.br) on 2017-03-28T15:03:54Z No. of bitstreams: 1 Danilo Albuquerque de Campos.pdf: 453917 bytes, checksum: 1b07ec11128857b2e96af37543e335fe (MD5) / Made available in DSpace on 2017-03-28T15:03:55Z (GMT). No. of bitstreams: 1 Danilo Albuquerque de Campos.pdf: 453917 bytes, checksum: 1b07ec11128857b2e96af37543e335fe (MD5) Previous issue date: 2014-08-22 / In this work we are interested in showing three algorithms rational approximation of square roots by methods unknown or underutilized by teachers of elementary and secondary education. We begin by defining numerical sequence and convergence of sequences, will discuss the need to expand the concept of rational number and demonstrate the irrationality of the diagonal of a square. Prove an important theorem known in the literature as Dirichlet’s theorem and finally elencaremos three methods of approximating the square roots of natural non-perfect square numbers, very simple to be worked on in the classroom that are rational algorithm aproximção of Hiero of Alexandria, Theon’s Ladder and the Pell-Fermat equation, sende latter discursão fundamental to who will perform on the relationship of the three methods presented. / Neste trabalho estamos interessados em mostrar três algoritmos de aproximação racional de raízes quadradas por métodos pouco utilizados ou desconhecidos pelos professores do ensino fundamental e médio. Iniciaremos definindo sequência numérica e convergência de sequências, discutiremos sobre a necessidade de ampliação do conceito de número racional e demonstraremos a irracionalidade da diagonal de um quadrado. Provaremos um importante Teorema conhecido na literatura como o Teorema de Dirichlet, e por fim elencaremos três métodos de aproximação de raízes quadradas de números naturais não quadrados perfeitos, muito simples de serem trabalhados em sala de aula que são: O algoritmo de aproximação racional de Hierão de Alexandria, A escada de Theon e a Equação de Pell-Fermat, sendo este último fundamental para discussão que iremos realizar sobre a relação dos três métodos apresentados.