Numerical Analysis and Computation 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 …

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 …

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 …

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 …