<p> This work presents a new automatic differentiation method, Nilpotent Matrix Differentiation (NMD), capable of propagating any order of mixed or univariate derivative through common linear algebra functions&mdash;most notably third-party sparse solvers and decomposition routines, in addition to basic matrix arithmetic operations and power series&mdash;without changing data-type or modifying code line by line; this allows differentiation across sequences of arbitrarily many such functions with minimal implementation effort. NMD works by enlarging the matrices and vectors passed to the routines, replacing each original scalar with a matrix block augmented by derivative data; these blocks are constructed with special sparsity structures, termed &ldquo;stencils,&rdquo; each designed to be isomorphic to a particular multidimensional hypercomplex algebra. The algebras are in turn designed such that Taylor expansions of hypercomplex function evaluations are finite in length and thus exactly track derivatives without approximation error. </p><p> Although this use of the method in the &ldquo;forward mode&rdquo; is unique in its own right, it is also possible to apply it to existing implementations of the (first-order) discrete adjoint method to find high-order derivatives with lowered cost complexity; for example, for a problem with <i>N</i> inputs and an adjoint solver whose cost is independent of <i>N</i>&mdash;i.e., <i><b> O</b></i>(1)&mdash;the <i>N &times; N</i> Hessian can be found in <i><b>O</b></i>(<i>N</i>) time, which is comparable to existing second-order adjoint methods that require far more problem-specific implementation effort. Higher derivatives are likewise less expensive&mdash;e.g., a <i>N &times; N &times; N</i> rank-three tensor can be found in <i><b> O</b></i>(<i>N</i>²). Alternatively, a Hessian-vector product can be found in <i><b>O</b></i>(1) time, which may open up many matrix-based simulations to a range of existing optimization or surrogate modeling approaches. As a final corollary in parallel to the NMD-adjoint hybrid method, the existing complex-step differentiation (CD) technique is also shown to be capable of finding the Hessian-vector product. All variants are implemented on a stochastic diffusion problem and compared in-depth with various cost and accuracy metrics.</p>

Cycle Systems

<p> From the early days of AI, computers have been programmed to play games against human players. Most of the AI work has sought to build world-champion programs to play turn-based games such as Chess and Checkers, however computer games increasingly provide for entertaining real-time play. In this dissertation, we present an extension of recursive game theory, which can be used to analyze games involving simultaneous movement. We include an algorithm which can be used to practically solve recursive games, and present a proof of its correctness. We also define a game theory of lowered expectations to deal with situations where game theory currently fails to give players a definitive strategy, and demonstrate its applicability using several example games.</p>

<p> We consider a classical lattice dipole gas with low activity in dimension <i>d</i> &ge; 3. We study long distance properties by a renormalization group analysis. We prove that various correlation functions have a infinite volume limit. We also get estimates on the decay of correlation functions.</p>

<p> This dissertation is devoted to solving general mixed integer optimization problems. Our main focus is understanding and developing strong cutting planes for mixed integer linear programs through Gomory and Johnson's <i> k</i>-dimensional infinite group relaxation. Each cut generated from this problem has an associated function, and among the strongest are extreme functions. For <i>k</i>=1 , we give an algorithm for testing the extremality of piecewise linear (possibly discontinuous) functions with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically for deciding extremality in this important class of minimal valid functions. We extend this algorithm to a large class of functions for <i>k </i>= 2 and develop theory for a more general result for <i>k</i> &ge; 2. For the <i>k</i>-dimensional infinite group relaxation, we prove that any minimal valid function that is continuous piecewise linear with at most <i>k</i>+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for <i>k</i>=1, and Cornu&eacute;jols and Molinaro for <i>k</i>=2. </p><p> We also contribute to the understanding of cutting plane closures for mixed integer programs. Cutting planes derived from maximal lattice-free convex sets have recently been studied intensely by the integer programming community. Although some fairly general results were obtained by Andersen, Louveaux and Weismantel, and later by Averkov, some basic questions remain unresolved. We show that when the number of integer variables is two the triangle closure is a polyhedron and its number of facets can be bounded by a polynomial in the size of the input data. The techniques of our proof are also used to refine Cornu&eacute;jols and Margot's necessary conditions identifying valid inequalities as facet-defining and to obtain polynomial complexity results concerning the mixed integer hull. </p><p> Finally, we study the integer minimization of a quasiconvex polynomial with quasiconvex polynomial constraints. We propose a new algorithm that is an improvement upon the best known algorithm, which is attributed to Heinz. This improvement is achieved by applying a new modern Lenstra-type algorithm, finding optimal ellipsoid roundings, and considering sparse encodings of polynomials. Our algorithm achieves a time-complexity of 2^{2nlog₂(n) + O(n)} in terms of the dimension <i>n</i>.</p>

<p> We address outflow boundary conditions for blood flow modeling. In particular, we consider a variety of fundamental issues in the structured tree boundary condition. We provide a theoretical analysis of the numerical implementation of the structured tree, showing that it is sensible but must be performed with great care. We also perform analytical and numerical studies on the sensitivity of model output on the structured tree's defining geometrical parameters. The most important component of this dissertation is the derivation of the new, generalized structured tree boundary condition. Unlike the original structured tree condition, the generalized structured tree does not contain a temporal periodicity assumption and is thus applicable to a much broader class of blood flow simulations. We describe a numerical implementation of this new boundary condition and show that the original structured tree is in fact a rough approximation of the new, generalized condition.</p><p> We also investigate parameter selection for outflow boundary conditions, and attempt to determine a set of structured tree parameters that gives reasonable simulation results without requiring any calibration. We are successful in doing so for a simulation of the systemic arterial tree, but the same parameter set yields physiologically unreasonable results in simulations of the Circle of Willis. Finally, we investigate the extension of recently introduced PDF methods to smooth solutions of systems of hyperbolic balance laws subject to uncertain inputs. These methods, currently available only for scalar equations, would provide a powerful tool for quantifying uncertainty in predictions of blood flow and other phenomena governed by first order hyperbolic systems. </p>

<p> In this work, we investigate the role of intracellular fluid flow in the migration of <i>Physarum polycephalum</i>. We develop two distinct models. Initially, we model the intracellular space of a <i>physarum </i> plasmodium as a peristaltic chamber. We derive a PDE relating the deformation of the chamber boundary and the flux of fluid along the chamber center line. We then solve this PDE for two distinct boundary deformations and evaluate the characteristic stress associated with the peristaltic flow. We compare the derived stress, as well as the relative phase of the deformation and flow waves, with values seen in experiments. Second, we develop a poro-elastic model of the interior of <i>physarum</i> that accounts for cytoskeletal structure, as well as adhesive interactions with the substrate. We develop this model within a framework similar to the Immersed Boundary method, which readily allows for computer simulation. We then use this model to simulate cell crawling across a range of parameters that characterize the coordination of adhesion to the substrate. We identify a spatio-temporal form of adhesion coordination that is consistent with experiments. We also show that this form is both efficient and robust, when compared to similar forms of adhesion coordination. </p>

<p> In this thesis we investigate two new Amplified Quantum Transforms. In particular we create and analyze the Amplified Quantum Fourier Transform (Amplified-QFT) and the Amplified-Haar Wavelet Transform. The Amplified-QFT algorithm is used to solve the Local Period Problem. We calculate the probabilities of success and compare this algorithm with the QFT and QHS algorithms. We also examine the Amplified-QFT algorithm for solving the Local Period Problem with Error Stream. We use the Amplified-Haar Wavelet Transform for solving the Local Constant or Balanced Signal Decision Problem which is a generalization of the Deutsch-Jozsa problem.</p>

<p> The purpose of this thesis is to prove the existence of a unique solution to a system of partial differential equations which models the flow of a compressible barotropic fluid under periodic boundary conditions. The equations come from modifying the compressible Navier-Stokes equations. The proof utilizes the method of successive approximations. We will define an iteration scheme based on solving a linearized version of the equations. Then convergence of the sequence of approximate solutions to a unique solution of the nonlinear system will be proven. The main new result of this thesis is that the density data is at a given point in the spatial domain over a time interval instead of an initial density over the entire spatial domain. Further applications of the mathematical model are fluid flow problems where the data such as concentration of a solute or temperature of the fluid is known at a given point. Future research could use boundary conditions which are not periodic.</p><p>

<p> Many problems in physics and engineering require the solution of the heat equation in moving geometry. Integral representations are particularly appropriate in this setting since they satisfy the governing equation automatically and, in the homogeneous case, require the discretization of the space-time boundary alone. Unlike methods based on direct discretization of the partial differential equation, they are unconditonally stable. Moreover, while a naive implementation of this approach is impractical, several efforts have been made over the past few years to reduce the overall computational cost. Of particular note are Fourier-based methods which achieve optimal complexity so long as the time step <i>&Delta;t</i> is of the same order as <i> &Delta;x,</i> the mesh size in the spatial variables. As the time step goes to zero, however, the cost of the Fourier-based fast algorithms grows without bound. A second difficulty with existing schemes has been the lack of efficient, high-order local-in-time quadratures for layer heat potentials. </p><p> In this dissertation, we present a new method for evaluating heat potentials that makes use of a spatially adaptive mesh instead of a Fourier series, a new version of the fast Gauss transform, and a new hybrid asymptotic/numerical method for local-in-time quadrature. The method is robust and efficient for any <i>&Delta;t,</i> with essentially optimal computational complexity. We demonstrate its performance with numerical examples and discuss its implications for subsequent work in diffusion, heat flow, solidification and fluid dynamics. </p><p>