Mathematics - Theses, Dissertations, and other Required Graduate Degree Essays

Receive updates for this collection

Game theoretic models of clear versus plain speech

Author: 
Date created: 
2018-11-27
Abstract: 

Clear speech is a speaking style intended to improve the comprehension of the hearer, which is usually due to the external noise, less ideal listening conditions, or the speaker is intended to be more intelligible. Clear speech, which exhibits increased duration, pitch, amplitude, and more exaggerated articulation, consumes more energy in order to improve the likelihood of accurate communication. To strike a balance between the cost of clear speech and the improvement it brings, we use game theory to model the phenomenon of clear speech. The conventions that speakers and hearers use to communicate are considered as equilibria in the communication game, and we need to make predictions of how the equilibria changes under the different circumstances. How our models correspond to what is experimentally observed, and what predictions are made for experimental results are discussed in the thesis. In the basic model, we study the case where the speaker has to send one of two messages equally likely in one-dimensional acoustic space. Next, we make a further discussion of the basic model in a priori probability of the sent message, the number of messages, and the conflicts between clearness and comprehensibility. The third contribution of this thesis is to extend the one-dimensional acoustic space to two dimensions, by introducing uncontrastive and contrastive features.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Paul Tupper
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Meso-swimmer suspensions: immersed boundary simulations of hydrodynamic interactions between worm-like swimmers

Date created: 
2018-09-26
Abstract: 

Hydrodynamic interaction between swimming organisms has long been a topic of interest in fluid-structure interaction. Especially, collective motion of swimming organisms such as bacteria, spermatozoa, and worms has recently received a great deal of attention from researchers in many disciplines, including biology, mathematics, engineering, food science, etc. To fully understand the collective behaviour of swimmers in dilute suspensions, near-field hydrodynamics need to be investigated. In an inertial regime, where Reynolds numbers range roughly from 0.1 to 100, and both advection and diffusion effects are present, the flow dynamics are described by the Navier-Stokes equations. We employed the immersed boundary method to couple the fluid and swimming worms (which we will refer to as meso-swimmers) in a system of integro-differential equations. We numerically examined individual, pairwise, and collective interactions of worms where phenomena such as synchronization, attraction as well as aggregation in dilute suspensions of swimmers are observed.

Document type: 
Thesis
File(s): 
Senior supervisor: 
John Stockie
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Minkowski theory and rational points on hyperelliptic curves

Author: 
Date created: 
2018-09-18
Abstract: 

A remarkable recent result of M.\ Bhargava shows in a certain precise sense that `most' hyperelliptic curves over $\q$ have no rational points. An object central to his proof is a certain representation $\Z^2 \otimes \Sym_2 \Z^2$ of $\GL_n(\Z)$. Elements in the set $\Z^2 \otimes \Sym_2 \Z^2$ can be viewed as a pair of $n \times n$ symmetric matrices with entires in $\z$ up to a $\GL_n(\Z)$ equivalence. Alternatively, $\Z^2 \otimes \Sym_2 \Z^2$ has an algebraic number theoretic description. By taking advantage of this property, in this thesis, we investigate $\Z^2 \otimes \Sym_2 \Z^2$ from the point of view of Minkowski theory. In particular, by assuming the hyperelliptic curve $C$ is given by $z^2 = f(x,y)$, where $f(x,y)$ is irreducible over $\q$, we gave a direct `Minkowski' style proof that a certain part of the set $\Z^2 \otimes \Sym_2 \Z^2$, which contains the elements arising from the rational points on $C$, is finite. Although, our main principle of proof mirrors the classical proof of finiteness for the class number of a number field, we develop new arguments when there exist some notable differences, and we strive to give self-contained proofs of some of the components of Bhargava's paper which we utilize.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Imin Chen
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Computing polynomial greatest common divisors using sparse interpolation

Author: 
Date created: 
2018-08-15
Abstract: 

Computing polynomial greatest common divisors (GCD) plays an important role in Computer Algebra systems because the GCD operation is the bottleneck of many basic applications. For example, to simplify a rational function one divides the numerator and denominator by their GCD. In 1988 Ben-Or and Tiwari introduced the first deterministic polynomial interpolation algorithm which accounts for sparsity. The number of evaluation points needed by the Ben-Or/Tiwari algorithm is linear in the number of non-zero terms in the target polynomial, and moreover, all variables can be interpolated simultaneously hence parallelizing the algorithm is easier. In this thesis, we present modular multivariate polynomial GCD algorithms based on Ben-Or/Tiwari sparse interpolation. They compute the GCD modulo one or more primes. We apply a Kronecker substitution to reduce the number of variables and we modify the Ben-Or/Tiwari evaluation point sequence so that we can use primes of acceptable size (machine primes) as well as gain randomness on the choice of evaluation points to avoid several known issues in polynomial GCD algorithms. Based on several assumptions, we first present a simplified algorithm for GCD computation in Z[x1, . . . , xn] from which we derive some theoretical bounds and convince the reader why it works. Then we present a practical version of the algorithm where those assumptions are dropped. This leads to a more complicated algorithm but it can be shown that it always terminates and it computes the GCD efficiently. In the 1980s, subsequent research in polynomial GCD algorithm mainly focused on polynomials over number fields. In this thesis, we also present a GCD algorithm for multivariate polynomials in Q(_)[x1, . . . , xn] where _ is an algebraic number. With a prime modulus p, all operations are performed in the finite ring Zp(_) where inversions may fail due to zero divisors. We manage to get all necessary bounds to support the correctness of our algorithm.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Michael Monagan
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Swarm equilibria in domains with boundaries

Author: 
Date created: 
2018-08-13
Abstract: 

This thesis involves the study of a well-known swarming model with interaction and external potentials in one and two dimensions. We refer to this model as the plain aggregation model and later study the model with nonlinear diffusion, so-called the diffusive model here. Typically set in free space, one of the novelties of this thesis is the study of such swarming models in the presence of a boundary. We consider a no-flux boundary condition enforced in a particle context via a ``slip'' condition. Of particular relevance to the context of this thesis, the swarming model used here can be formulated as an energy gradient flow and thusly, one might expect equilibrium states to be minima of the energy. In this work we demonstrate, through both analytical and numerical investigations, a continuum of equilibria of the plain aggregation model that are not minima of the energy. Furthermore, we show that these non-minimizing equilibria are achieved dynamically from a non-trivial set of initial conditions with a variety of interaction potentials and boundary geometries. Thus we show conclusively a deficiency with the plain aggregation model in domains with boundaries, namely that it appears to evolve into equilibria that are not minima of the energy. Following this we then propose a rectification to this deficiency in way of nonlinear diffusion. This choice of nonlinear diffusion is especially attractive because it preserves compact states of the plain aggregation model. We showcase how the diffusive model approaches, but does not equilibrate at, the non-minimizing equilibria of the plain aggregation model. Furthermore we demonstrate how minimizers of the diffusive model do approach minimizers of the plain aggregation model in the zero diffusion limit.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Razvan Fetecau
JF Williams
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Genome rearrangement problems accounting for duplicate genes

Author: 
Date created: 
2018-08-10
Abstract: 

We investigate certain genome rearrangement problems studied in relation to genome evolution. We introduce the SCJ-TD-FD rearrangement model to explain the directed evolution from an ancestor A to a descendant D, where D may contain multiple copies of genes from A. We study the pairwise genome distance problem that aims at finding the most parsimonious sequence of cuts, joins and single-gene duplications that transforms A to D, under this model. Next, we study the rooted median problem under the SCJ-TD-FD model, for which the problem is shown to be NP-hard. We provide an Integer Linear Program that, on simulated data, predicts an optimal median with high accuracy. Finally, we study the Small Parsimony Problem under the SCJ-TD-FD model that aims at finding the gene orders at the internal nodes of a given species tree. We define an ILP-based approach to reconstruct the ancestral gene orders and present our experiments on a data-set of Anopheles mosquito genomes.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Cedric Chauve
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Domain decomposition solvers and preconditioners for the implicit closest point method

Author: 
Date created: 
2018-07-17
Abstract: 

The numerical treatment of surface intrinsic elliptic PDE presents several interesting chal-lenges over those posed on flat space. The implicit closest point method, (iCPM) is an embedding method well suited to these problems, and allows the treatment of general sur-faces, S. An extension operator brings surface bound information into the embedding space, to be constant in the surface normal direction, and allows the solution of the problem by standard methods. The positive Helmholtz equation, (c − △S ) u = f, is considered with ten-sor product barycentric Lagrange interpolation defining the extension operator and stan-dard second-order centered di˙erences for the ambient Laplacian. Under this scheme, a non-symmetric system with poor sparsity is obtained, which reduces the performance of iterative solvers and motivates the development of specialized solvers. Optimized restricted additive Schwarz (ORAS) methods are well suited to this task and are formulated for these problems. The interesting geometry of the problem presents challenges for the construction of subdomains as well as the enforcement of Robin boundary conditions. The developed solvers perform well over a range of test problems with the optimized methods providing a distinct advantage. With Krylov acceleration, convergence is obtained rapidly with dimin-ished di˙erence between the optimized and non-optimized methods.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Steven Ruuth
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Efficient periodic graph traversal on graphs with a given rotation system

Author: 
Date created: 
2018-08-22
Abstract: 

We consider periodic graph traversal in anonymous undirected graphs by a finite state Mealy automaton (agent). The problem is to design an automaton A and a port labeling scheme L such that A (using L) performs on any undirected graph an infinite walk that periodically visit all vertices. The goal is to minimize the revisit time of any vertex over all graphs (traversal period) π. If the labeling scheme L is given by an adversary, it has been shown by Budach [6] that no such finite automaton A exists. If L does not need to be a permutation at every vertex, one can easily encode a spanning tree and A can perform traversal with period 2n − 2 even it is an oblivious agent. The problem is difficult when L is limited to be a permutation. The best known upper bound on the traversal period in such a case is 3.5n−2 by Czyzowicz et al. [11], where n is the number of vertices. It is an open problem whether it is possible to achieve traversal period of 2n − 2. In this thesis, we answer this question affirmatively under the assumption that the input graph G is given with a rotation system, where a rotation system, where a rotation system of a graph is given by lists of local orders of edges incident to each vertex the graph.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Ladislav Stacho
Jan Manuch
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

2-Regular Digraphs on Surfaces

Author: 
Date created: 
2018-08-06
Abstract: 

A 2-regular digraph is one where every vertex has in-degree and out-degree 2. This thesis focuses on surface embeddings of 2-regular digraphs, one where the underlying graph is embedded in a surface and all faces are bounded by directed closed walks. Immersion acts as a natural minor-like containment relation for embedded 2-regular digraphs and this theory is linked to undirected graph minors by way of the directed medial graph. We parallel the theory of undirected graphs in surfaces by proving analogues of Whitney's Theorem and Tutte's peripheral cycles theorem for 2-regular digraphs in the sphere. Then, using a notion of branch-width and a 2-regular digraph grid theorem by Johnson, we prove that for each fixed surface S, the 2-regular digraphs embeddable in S are characterized by a finite list of immersion obstructions. We then present the current state of the art with regard to classification of obstructions for surfaces: Johnson characterized the sphere obstructions, we classify all projective plane obstructions, and we have a computer assisted partial list of obstructions for the torus and Klein bottle. We also consider two open problems in the world of undirected graphs on surfaces and resolve their analogues in the world of 2-regular digraphs on surfaces. The first conjecture by Negami we resolve in the affirmative, that a 2-regular digraph has a finite planar cover if and only if it is projective planar. The second, the strong embedding conjecture, is resolved in the negative and we provide an infinite family of well connected counter-examples.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Matt DeVos
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Aspects of the Arithmetic of Uniquely Trigonal Genus Four Curves: Arithmetic Invariant Theory and Class Groups of Cubic Number Fields

Author: 
Peer reviewed: 
No, item is not peer reviewed.
Date created: 
2018-11-01
Abstract: 

In this thesis, we study the family of uniquely trigonal genus 4 curves via their connection to del Pezzo surfaces of degree 1. We consider two different aspects of these curves. First, we show how to construct any uniquely trigonal genus 4 curve whose Jacobian variety has fully rational 2-torsion and whose trigonal morphism has a prescribed totally ramified fibre. Using this construction, we find an infinite family of cubic number fields whose class group has 2-rank at least 8. We also consider genus 4 curves that are superelliptic of degree 3, and prove sharp results on the size of the 2-torsion subgroup of their Jacobian varieties over the rationals. Our second result is a contribution to arithmetic invariant theory. We consider the moduli space of uniquely trigonal genus 4 curves whose trigonal morphism has a marked ramification point, originally studied by Coble, from a modern perspective.We then show under a technical hypothesis how to construct an assignment from the rational points on the Jacobian variety of such a curve to a fixed orbit space that is independent of the curve. The assignment is compatible with base extensions of the field, and over an algebraically closed field our assignment reduces to the assignment of a marked (in the aforementioned sense) uniquely trigonal genus 4 curve to its moduli point. The orbit space is constructed from the split algebraic group of type E8.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Nils Bruin
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.