We propose two efficient automatic differentiation (AD) schemes to compute incrementally Taylor series and System Jacobian for solving differential-algebraic equations (DAEs) by Taylor series. Our schemes are based on topological ordering of a DAE's computational graph and then partitioning the topologically sorted nodes using structural information obtained from the DAE. Solving a DAE by Taylor series is carried out in stages. From one stage to another, partitions of the computational graph are incrementally activated so that we can reuse Taylor coefficients and gradients computed in previous stages. As a result, the computational complexity of evaluating a System Jacobian is independent of the number of stages. We also develop a common subexpression elimination (CSE) method to build a compact computational graph through operator overloading. The CSE method is of linear time complexity, which makes it suitable as a preprocessing step for general operator overloaded computing. By applying CSE, all successive overloaded computation can save time and memory. Furthermore, the computational graph of a DAE reveals its internal sparsity structure. Based on it, we devise an algorithm to propagate gradients in the forward mode of AD using compressed vectors. This algorithm can save both time and memory when computing the System Jacobian for sparse DAEs. We have integrated our approaches into the \daets solver. Computational results show multiple-fold speedups against two popular AD tools, \FAD~and ADOL-C, when solving various sparse and dense DAEs. / Thesis / Master of Science (MSc)

We first provide a detailed background of a geometric projection methodology developed by Professor Roswitha Marz at Humboldt University in Berlin for showing uniqueness and existence of solutions for ordinary differential-algebraic equations (DAEs). Because of the geometric and operator-theoretic aspects of this particular method, it can be extended to the case of infinite-dimensional abstract DAEs. For example, partial differential equations (PDEs) are often formulated as abstract Cauchy or evolution problems which we label abstract ordinary differential equations or AODE. Using this abstract formulation, existence and uniqueness of the Cauchy problem has been studied. Similarly, we look at an AODE system with operator constraint equations to formulate an abstract differential-algebraic equation or ADAE problem. Existence and uniqueness of solutions is shown under certain conditions on the operators for both index-1 and index-2 abstract DAEs. These existence and uniqueness results are then applied to some index-1 DAEs in the area of thermodynamic modeling of a chemical vapor deposition reactor and to a structural dynamics problem. The application for the structural dynamics problem, in particular, provides a detailed construction of the model and development of the DAE framework. Existence and uniqueness are primarily demonstrated using a semigroup approach. Finally, an exploration of some issues which arise from discretizing the abstract DAE are discussed. / Ph. D.

Made available in DSpace on 2016-04-27T16:59:03Z (GMT). No. of bitstreams: 1 Armando Pereira.pdf: 461594 bytes, checksum: aeb2a3fb8278ff84be43c2ee3be64f43 (MD5) Previous issue date: 2010-05-12 / The purpose of this research was to develop a panorama of the dissertations from PUC-SP about the theme algebraic equations in Elementary School (6th to 9h grades). The methodology from the essay was defined as having a bibliographic character, in the "panorama" modality. Our analysis method was constituted of four dissertations published, from 2005 to 2008, in the Mathematical Education area. For the essay selection, it was used the site of the Program of Post- Graduate Studies in Mathematical Education from PUC-SP, obeying to predetermined criteria. Thus, the similarities among the purposes, conclusions, indications, for future researches and theoretical referentials were sought. The results indicated that the majority of the researches analyzed presented similarities between the researchers conclusions and the indications for future researches. However, there were very few similarities between the purposes of these researches and between the theoretical referentials used in the development of the dissertations. At last, it is considered to have presented a contribution to the Group of Researches in Algebraic Education from PUC-SP and possibly to the investigation in Mathematical Education, because research modalities of bibliographical type are recognized, not considered before by authors that theorized about them, which it was not our initial intention. Being, this, the present study presented results that might give subsides to future researches / Esta pesquisa teve como objetivo desenvolver um panorama de dissertações da PUC-SP sobre o tema equações algébricas no Ensino Fundamental (6º ao 9º anos). A metodologia do trabalho definiu-se como de caráter bibliográfico, na modalidade panorama . Nosso material de análise constituiu-se de quatro dissertações publicadas, entre 2005 e 2008, na área de Educação Matemática. Para a seleção dos trabalhos, utilizou-se o sítio do Programa de Estudos Pós- Graduados em Educação Matemática da PUC-SP, obedecendo a critérios predeterminados. Assim, buscamos as similaridades entre os objetivos, conclusões, indicações para futuras pesquisas e referenciais teóricos. Os resultados indicaram que a maioria das pesquisas analisadas apresentou similaridades entre as conclusões dos pesquisadores e entre as indicações para futuras pesquisas. No entanto, ocorreram exíguas similaridades entre os objetivos dessas pesquisas e entre os referenciais teóricos utilizados no desenvolvimento das dissertações. Por fim, consideramos ter apresentado uma contribuição ao Grupo de Pesquisas em Educação Algébrica da PUC-SP e, possivelmente, à investigação em Educação Matemática, porque reconhecemos modalidades de pesquisa de tipo bibliográfico, não consideradas antes por autores que teorizam-nas, o que não era nossa intenção inicial. Sendo, assim, o presente estudo apresentou resultados que poderão proporcionar subsídios para futuras pesquisas

The purpose of this thesis was to develop a program that would accept, as input, a finite set of algebraic equations and simple if-then conditional expressions that model a natural system, and then produce a continuous computer simulation with graphics and tabular output. The equations and conditionals can be in any order and key elements can be missing. The program can be used to run existing models or as a development tool to produce immediate prototypic computer simulations through synergistic man-machine interactions. The theoretical aspects of automatic program generation were discussed, as well as the architectural design of the system. The simulation system was used to develop a computer simulation of an exploited Northern Utah pheasant population and the results were compared to the results from an earlier FORTRAN computer simulation of the same model. It was concluded that the simulation system developed for this thesis produces verified computer simulations from mathematical models that are at least as accurate as the corresponding simulation written in FORTRAN. The system was easy to use and should be useful for unsophisticated users. Some "tuning'' of the input was needed to produce a verified simulation and it was concluded that further work was needed here.

A Hamiltonian system in potential form (formula in the original abstract) subject to smooth constraints on q can be viewed as a Hamiltonian system on a manifold, but numerical computations must be performed in Rn. In this paper methods which reduce "Hamiltonian differential algebraic equations" to ODEs in Euclidean space are examined. The authors study the construction of canonical parameterizations or local charts as well as methods based on the construction of ODE systems in the space in which the constraint manifold is embedded which preserve the constraint manifold as an invariant manifold. In each case, a Hamiltonian system of ordinary differential equations is produced. The stability of the constraint invariants and the behavior of the original Hamiltonian along solutions are investigated both numerically and analytically.

Differential-algebraic equations (DAEs) form the natural way in which models of physical systems are delivered from an object-oriented modeling tool like Modelica. Differential-algebraic equations are also known as descriptor systems, singular systems, and implicit systems. If some constant parameters in such models are unknown, one might need to estimate them from measured data from the modeled system. This is a form of system identification called gray box identification. It may also be of interest to estimate the value of time-varying variables in the model. This is often referred to as state estimation. The objective of this work is to examine how gray box identification and estimation of time-varying variables can be performed for models described by differential-algebraic equations. If a model has external stimuli that are not measured or uncertain measurements, it is often appropriate to model this as stochastic processes. This is called noise modeling. Noise modeling is an important part of system identification and state estimation, so we examine how well-posedness of noise models for differential-algebraic equations can be characterized. For well-posed models, we then discuss how particle filters can be implemented for estimation of time-varying variables. We also discuss how constant parameters can be estimated. When estimating time-varying variables, it is of interest to examine if the problem is observable, that is, if it has a unique solution. The corresponding property when estimating constant parameters is identifiability. In this thesis, we discuss how observability and identifiability can be determined for DAEs. We propose three approaches, where one can be seen as an extension of standard methods for state-space systems based on rank tests. For linear DAEs, a more detailed analysis is performed. We use some well-known canonical forms to examine well-posedness of noise models and to implement estimation of time-varying variables and constant parameters. This includes formulation of Kalman filters for linear DAE models. To be able to implement the suggested methods, we show how the canonical forms can be computed using numerical software from the linear algebra package LAPACK.

With the arrival of modern component-based modeling tools for dynamic systems, the differential-algebraic equation form is increasing in popularity as it is general enough to handle the resulting models. However, if uncertainty is allowed in the equations — no matter how small — this thesis stresses that such equations generally become ill-posed. Rather than deeming the general differential-algebraic structure useless up front due to this reason, the suggested approach to the problem is to ask what assumptions that can be made in order to obtain well-posedness. Here, “well-posedness” is used in the sense that the uncertainty in the solutions should tend to zero as the uncertainty in the equations tends to zero. The main theme of the thesis is to analyze how the uncertainty in the solution to a differential-algebraic equation depends on the uncertainty in the equation. In particular, uncertainty in the leading matrix of linear differential-algebraic equations leads to a new kind of singular perturbation, which is referred to as “matrix-valued singular perturbation”. Though a natural extension of existing types of singular perturbation problems, this topic has not been studied in the past. As it turns out that assumptions about the equations have to be made in order to obtain well-posedness, it is stressed that the assumptions should be selected carefully in order to be realistic to use in applications. Hence, it is suggested that any assumptions (not counting properties which can be checked by inspection of the uncertain equations) should be formulated in terms of coordinate-free system properties. In the thesis, the location of system poles has been the chosen target for assumptions. Three chapters are devoted to the study of uncertain differential-algebraic equations and the associated matrix-valued singular perturbation problems. Only linear equations without forcing function are considered. For both time-invariant and time-varying equations of nominal differentiation index 1, the solutions are shown to converge as the uncertainties tend to zero. For time-invariant equations of nominal index 2, convergence has not been shown to occur except for an academic example. However, the thesis contains other results for this type of equations, including the derivation of a canonical form for the uncertain equations. While uncertainty in differential-algebraic equations has been studied in-depth, two related topics have been studied more passingly. One chapter considers the development of point-mass filters for state estimation on manifolds. The highlight is a novel framework for general algorithm development with manifold-valued variables. The connection to differential-algebraic equations is that one of their characteristics is that they have an underlying manifold-structure imposed on the solution. One chapter presents a new index closely related to the strangeness index of a differential-algebraic equation. Basic properties of the strangeness index are shown to be valid also for the new index. The definition of the new index is conceptually simpler than that of the strangeness index, hence making it potentially better suited for both practical applications and theoretical developments.

Transformers are very important parts of any electrical network, and their size increase so does their price. Protecting these important devices is a daunting task due to the wide variety of operating conditions. This thesis develops a new protection scheme based on state estimation.The foundation upon which our protection scheme is built is the modeling of the single phase transformer system of equations. The transformer equations are composed of polynomial and differential equations and this system of equations involving the transformer's electrical quantities are modeled into a system of equations such that highest degree of each of the system's equations is quadratic―in a process named Quadratization and then integrated using a technique called Quadratic integration to give a set of algebraic companion equations that can be solved numerically to determine the health of the transformer.

Nonlinear algebraic equations (NAEs) occur in many areas of science and engineering. The process of solving these NAEs is generally difficult, from finding a good initial guess that leads to a desired solution to deciding on convergence criteria for the approximate solution. In practice, Newton's method is the only robust general-purpose method for solving a system of NAEs. Many variants of Newton's method exist. However, it is generally impossible to know a priori which variant of Newton's method will be effective for a given problem.<p>Many high-quality software libraries are available for the numerical solution of NAEs. However, the user usually has little control over many aspects of what the library does. For example, the user may not be able to easily switch between direct and indirect methods for the linear algebra. This thesis describes a problem-solving environment (PSE) called pythNon for studying the effects (e.g., performance) of different strategies for solving systems of NAEs. It provides the researcher, teacher, or student with a flexible environment for rapid prototyping and numerical experiments. In pythNon, users can directly influence the solution process on many levels, e.g., investigation of the effects of termination criteria and/or globalization strategies. In particular, to show the power, flexibility, and ease of use of the pythNon PSE, this thesis also describes the development of a novel forcing-term strategy for approximating the Newton direction efficiently in the pythNon PSE.

Nonlinear algebraic equations (NAEs) occur in many areas of science and engineering. The process of solving these NAEs is generally difficult, from finding a good initial guess that leads to a desired solution to deciding on convergence criteria for the approximate solution. In practice, Newton's method is the only robust general-purpose method for solving a system of NAEs. Many variants of Newton's method exist. However, it is generally impossible to know a priori which variant of Newton's method will be effective for a given problem.<p>Many high-quality software libraries are available for the numerical solution of NAEs. However, the user usually has little control over many aspects of what the library does. For example, the user may not be able to easily switch between direct and indirect methods for the linear algebra. This thesis describes a problem-solving environment (PSE) called pythNon for studying the effects (e.g., performance) of different strategies for solving systems of NAEs. It provides the researcher, teacher, or student with a flexible environment for rapid prototyping and numerical experiments. In pythNon, users can directly influence the solution process on many levels, e.g., investigation of the effects of termination criteria and/or globalization strategies. In particular, to show the power, flexibility, and ease of use of the pythNon PSE, this thesis also describes the development of a novel forcing-term strategy for approximating the Newton direction efficiently in the pythNon PSE.