Physical Sciences and Mathematics Commons^™

New Algorithmic Support For The Fundamental Theorem Of Algebra, Vitaly Zaderman

Dissertations, Theses, and Capstone Projects

Univariate polynomial root-finding is a venerated subjects of Mathematics and Computational Mathematics studied for four millenia. In 1924 Herman Weyl published a seminal root-finder and called it an algorithmic proof of the Fundamental Theorem of Algebra. Steve Smale in 1981 and Arnold Schonhage in 1982 proposed to classify such algorithmic proofs in terms of their computational complexity. This prompted extensive research in 1980s and 1990s, culminated in a divide-and-conquer polynomial root-finder by Victor Pan at ACM STOC 1995, which used a near optimal number of bit-operations. The algorithm approximates all roots of a polynomial p almost as fast as one …

Hydrodynamic And Physicochemical Interactions Between An Active Janus Particle And An Inactive Particle, Jessica S. Rosenberg

Dissertations, Theses, and Capstone Projects

Active matter is an area of soft matter science in which units consume energy and turn it into autonomous motion. Groups of these units – whether flocks of birds, bacterial colonies, or even collections of synthetically-made active particles – may exhibit complex behavior on large scales. While the large-scale picture is of great importance, so is the microscopic scale. Studying the individual particles that make up active matter will allow us to understand how they move, and whether and under what circumstances their activity can be controlled.

Here we delve into the world of active matter by studying colloidal-sized (100 …

Symmetry-Inspired Analysis Of Biological Networks, Ian Leifer

Dissertations, Theses, and Capstone Projects

The description of a complex system like gene regulation of a cell or a brain of an animal in terms of the dynamics of each individual element is an insurmountable task due to the complexity of interactions and the scores of associated parameters. Recent decades brought about the description of these systems that employs network models. In such models the entire system is represented by a graph encapsulating a set of independently functioning objects and their interactions. This creates a level of abstraction that makes the analysis of such large scale system possible. Common practice is to draw conclusions about …

Prime Factors: America’S Prioritization Of Literacy Over Numeracy And Its Relationship To Systemic Inequity, Troy Smith

Dissertations, Theses, and Capstone Projects

For much of American history, literacy has been prioritized in K-12 education and society, at large, at the expense of numeracy. This lack of numerical emphasis has established innumeracy as an American cultural norm that has resulted in America not producing a sufficient number of numerate citizens, and ranking poorly on mathematical performance in international comparisons. This paper investigates the decisions and circumstances that led to this under prioritization, along with the public and cultural impact of said actions. Toward this end, literature regarding contemporary and historical influences on American mathematics education (e.g., civic, policy, and parental) was reviewed. The …

Modeling And Analysis Of Affiliation Networks With Subsumption, Alexey Nikolaev

Dissertations, Theses, and Capstone Projects

An affiliation (or two-mode) network is an abstraction commonly used for representing systems with group interactions. It consists of a set of nodes and a set of their groupings called affiliations. We introduce the notion of affiliation network with subsumption, in which no affiliation can be a subset of another. A network with this property can be modeled by an abstract simplicial complex whose facets are the affiliations of the network.

We introduce a new model for generating affiliation networks with and without subsumption (represented as simplicial complexes and hypergraphs, respectively). In this model, at each iteration, a constant number …

An Accurate Solution Of The Self-Similar Orbit-Averaged Fokker-Planck Equation For Core-Collapsing Isotropic Globular Clusters: Properties And Application, Yuta Ito

Dissertations, Theses, and Capstone Projects

Hundreds of dense star clusters exist in almost all galaxies. Each cluster is composed of approximately ten thousand through ten million stars. The stars orbit in the clusters due to the clusters' self-gravity. Standard stellar dynamics expects that the clusters behave like collisionless self-gravitating systems on short time scales (~ million years) and the stars travel in smooth continuous orbits. Such clusters temporally settle to dynamically stable states or quasi-stationary states (QSS). Two fundamental QSS models are the isothermal- and polytropic- spheres since they have similar structures to the actual core (central part) and halo (outskirt) of the clusters. The …

Matrix Low Rank Approximation At Sublinear Cost, Qi Luan

Dissertations, Theses, and Capstone Projects

A matrix algorithm runs at sublinear cost if the number of arithmetic operations involved is far fewer than the number of entries of the input matrix. Such algorithms are especially crucial for applications in the field of Big Data, where input matrices are so immense that one can only store a fraction of the entire matrix in memory of modern machines. Typically, such matrices admit Low Rank Approximation (LRA) that can be stored and processed at sublinear cost. Can we compute LRA at sublinear cost? Our counter example presented in Appendix C shows that no sublinear cost algorithm can compute …

On The Complexity Of Computing Galois Groups Of Differential Equations, Mengxiao Sun

Dissertations, Theses, and Capstone Projects

The differential Galois group is an analogue for a linear differential equation of the classical Galois group for a polynomial equation. An important application of the differential Galois group is that a linear differential equation can be solved by integrals, exponentials and algebraic functions if and only if the connected component of its differential Galois group is solvable. Computing the differential Galois groups would help us determine the existence of the solutions expressed in terms of elementary functions (integrals, exponentials and algebraic functions) and understand the algebraic relations among the solutions.

Hrushovski first proposed an algorithm for computing the differential …

Galois Groups Of Differential Equations And Representing Algebraic Sets, Eli Amzallag

Dissertations, Theses, and Capstone Projects

The algebraic framework for capturing properties of solution sets of differential equations was formally introduced by Ritt and Kolchin. As a parallel to the classical Galois groups of polynomial equations, they devised the notion of a differential Galois group for a linear differential equation. Just as solvability of a polynomial equation by radicals is linked to the equation’s Galois group, so too is the ability to express the solution to a linear differential equation in "closed form" linked to the equation’s differential Galois group. It is thus useful even outside of mathematics to be able to compute and represent these …

The Philosophical Foundations Of Plen: A Protocol-Theoretic Logic Of Epistemic Norms, Ralph E. Jenkins

Dissertations, Theses, and Capstone Projects

In this dissertation, I defend the protocol-theoretic account of epistemic norms. The protocol-theoretic account amounts to three theses: (i) There are norms of epistemic rationality that are procedural; epistemic rationality is at least partially defined by rules that restrict the possible ways in which epistemic actions and processes can be sequenced, combined, or chosen among under varying conditions. (ii) Epistemic rationality is ineliminably defined by procedural norms; procedural restrictions provide an irreducible unifying structure for even apparently non-procedural prescriptions and normative expressions, and they are practically indispensable in our cognitive lives. (iii) These procedural epistemic norms are best analyzed in …

Physical Applications Of The Geometric Minimum Action Method, George L. Poppe Jr.

Dissertations, Theses, and Capstone Projects

This thesis extends the landscape of rare events problems solved on stochastic systems by means of the \textit{geometric minimum action method} (gMAM). These include partial differential equations (PDEs) such as the real Ginzburg-Landau equation (RGLE), the linear Schroedinger equation, along with various forms of the nonlinear Schroedinger equation (NLSE) including an application towards an ultra-short pulse mode-locked laser system (MLL).

Additionally we develop analytical tools that can be used alongside numerics to validate those solutions. This includes the use of instanton methods in deriving state transitions for the linear Schroedinger equation and the cubic diffusive NLSE.

These analytical solutions are …

The Advection-Diffusion Equation And The Enhanced Dissipation Effect For Flows Generated By Hamiltonians, Michael Kumaresan

Dissertations, Theses, and Capstone Projects

We study the Cauchy problem for the advection-diffusion equation when the diffusive parameter is vanishingly small. We consider two cases - when the underlying flow is a shear flow, and when the underlying flow is generated by a Hamiltonian. For the former, we examine the problem on a bounded domain in two spatial variables with Dirichlet boundary conditions. After quantizing the system via the Fourier transform in the first spatial variable, we establish the enhanced-dissipation effect for each mode. For the latter, we allow for non-degenerate critical points and represent the orbits by points on a Reeb graph, with vertices …

Elimination For Systems Of Algebraic Differential Equations, Richard Gustavson

Dissertations, Theses, and Capstone Projects

We develop new upper bounds for several effective differential elimination techniques for systems of algebraic ordinary and partial differential equations. Differential elimination, also known as decoupling, is the process of eliminating a fixed subset of unknown functions from a system of differential equations in order to obtain differential algebraic consequences of the original system that do not depend on that fixed subset of unknowns. A special case of differential elimination, which we study extensively, is the question of consistency, that is, if the given system of differential equations has a solution. We first look solely at the ``algebraic data" of …

Fast Algorithms On Random Matrices And Structured Matrices, Liang Zhao

Dissertations, Theses, and Capstone Projects

Randomization of matrix computations has become a hot research area in the big data era. Sampling with randomly generated matrices has enabled fast algorithms to perform well for some most fundamental problems of numerical algebra with probability close to 1. The dissertation develops a set of algorithms with random and structured matrices for the following applications: 1) We prove that using random sparse and structured sampling enables rank-r approximation of the average input matrix having numerical rank r. 2) We prove that Gaussian elimination with no pivoting (GENP) is numerically safe for the average nonsingular and well-conditioned matrix preprocessed with …

Stochastic Processes And Their Applications To Change Point Detection Problems, Heng Yang

Dissertations, Theses, and Capstone Projects

This dissertation addresses the change point detection problem when either the post-change distribution has uncertainty or the post-change distribution is time inhomogeneous. In the case of post-change distribution uncertainty, attention is drawn to the construction of a family of composite stopping times. It is shown that the proposed composite stopping time has third order optimality in the detection problem with Wiener observations and also provides information to distinguish the different values of post-change drift. In the case of post-change distribution uncertainty, a computationally efficient decision rule with low-complexity based on Cumulative Sum (CUSUM) algorithm is also introduced. In the time …

An Averaging Method For Advection-Diffusion Equations, Nicholas Spizzirri

Dissertations, Theses, and Capstone Projects

Many models for physical systems have dynamics that happen over various different time scales. For example, contrast the everyday waves in the ocean with the larger, slowly moving global currents. The method of multiple scales is an approach for approximating the solutions of differential equations by separating out the dynamics at slower and faster time scales. In this work, we apply the method of multiple scales to generic advection-diffusion equations (both linear and non-linear, and in arbitrary spatial dimensions) and develop a method for 'averaging out' the faster scale phenomena, giving us an 'effective' solution for the slower scale dynamics. …

Cayley Graphs Of Semigroups And Applications To Hashing, Bianca Sosnovski

Dissertations, Theses, and Capstone Projects

In 1994, Tillich and Zemor proposed a scheme for a family of hash functions that uses products of matrices in groups of the form $SL_2(F_{2^n})$. In 2009, Grassl et al. developed an attack to obtain collisions for palindromic bit strings by exploring a connection between the Tillich-Zemor functions and maximal length chains in the Euclidean algorithm for polynomials over $F_2$.

In this work, we present a new proposal for hash functions based on Cayley graphs of semigroups. In our proposed hash function, the noncommutative semigroup of linear functions under composition is considered as platform for the scheme. We will also …

Preconditioning For Matrix Computation, Xiaodong Yan

Dissertations, Theses, and Capstone Projects

Preconditioning is a classical subject of numerical solution of linear systems of equations. The goal is to turn a linear system into another one which is easier to solve. The two central subjects of numerical matrix computations are LIN-SOLVE, that is, the solution of linear systems of equations and EIGEN-SOLVE, that is, the approximation of the eigenvalues and eigenvectors of a matrix. We focus on the former subject of LIN-SOLVE and show an application to EIGEN-SOLVE. We achieve our goal by applying randomized additive and multiplicative preconditioning. We facilitate the numerical solution by decreasing the condition of the coefficient matrix …

Component Trees For The Exploration Of Macromolecular Structures In Biology, Lucas Oliveira

Dissertations, Theses, and Capstone Projects

Understanding the three-dimensional structure of a macromolecular complex is essential for understanding its function. A component tree is a topological and geometric image descriptor that captures information regarding the structure of an image based on the connected components determined by different grayness thresholds. This dissertation presents a novel interactive framework for visual exploration of component trees of the density maps of macromolecular complexes, with the purpose of improved understanding of their structure. The interactive exploration of component trees together with a robust simplification methodology provide new insights in the study of macromolecular structures. An underlying mathematical theory is introduced and …