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

Receive updates for this collection

Simultaneous prime values of binary forms

Author: 
Date created: 
2019-08-16
Abstract: 

The twin prime conjecture asserts that there are infinitely many positive integers x such that x and x+2 are simultaneously prime. In this thesis, we consider a two-variable analogue of this problem. Let F(x, y) be a positive definite quadratic form and G(x, y) a linear form, both with integer coefficients. Suppose for any prime p there exist l, m such that p t F(l, m)G(l, m). Then we prove that there are infinitely many l, m in Z such that both F(l, m), G(l, m) are primes. In fact, our proof extends to primes in arithmetic progressions F(l, m)= a mod q and G(l, m)=b mod q. The main result (when q=1) was first obtained independently by the author and another team of researchers D. Schindler and S. Y. Xiao. The extension is joint work with them.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Stephen Choi
Peter Borwein
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

An implementation of two-cover descent on plane quartic curves

Author: 
Date created: 
2019-08-09
Abstract: 

We gather experimental evidence related to the question of deciding whether a smooth plane quartic curve has a rational point. Smooth plane quartics describe curves in genus 3, the first genus in which non-hyperelliptic curves occur. We present an algorithm that determines a set of unramified covers of a given plane quartic curve, with the property that any rational point will lift to one of the covers. In particular, if the algorithm returns the empty set, then the curve has no rational points. We apply our algorithm to a total of 1000 isomorphism classes of randomly-generated plane quartic curves.

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

Low rank quadratic assignment problem: Formulations and experimental analysis

Author: 
Date created: 
2019-08-26
Abstract: 

In this thesis, we study the quadratic assignment problem (QAP) with a special emphasis on the case where the associated cost matrix is of rank r (QAP(r)), for small values of r. We first consider different representations of the cost matrix Q which were shown to be beneficial for the quadratic set covering problem (QSCP). Unlike QSCP, these representations were unable to solve QAP of size n >= 20 and had a behaviour different from that of QSCP. To reconfirm this, additional experiments were carried out using the quadratic knapsack problem (QKP). We did notice statistically significant preferred representations for QKP and QAP, but were different from what was observed and known for QSCP. Next we consider four different mixed integer linear programming (MILP) formulations of QAP(r), extending the known case of r=1. Extensive experimental results are provided for r=2,3,4. One of our new formulations was shown to be very effective in solving large size QAP(r) for r=2,3,4. The performance of the model is observed to deteriorate as the rank is increased. Finally, we present theoretical and experimental comparisons of the linear programming relaxations of our MILP formulations of QAP(r). Our MILP formulations for QAP(r) could be used as a heuristic for QAP by computing a low-rank approximation of the data matrix Q.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Abraham Punnen
Snezana Mitrovic Minic
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Formulating Quadratic Traveling Salesman Problems for computation

Author: 
Date created: 
2019-08-02
Abstract: 

The Traveling Salesman Problem (TSP) is a fundamental combinatorial optimization problem. Adding costs associated with pairs of edges included in a tour gives the Quadratic Traveling Salesman Problem (QTSP). This increases modeling power by allowing, for example, the inclusion of transfer costs between edges. We consider a general version of this problem, where costs are attached to all pairs of edges. We give a brief history of computational solvers, especially in relation to the TSP. For the QTSP, we consider modifying the structure of the quadratic cost input and linearizing the quadratic objective function, with detail on how to generate the modifications and linearizations. We study the impact of these structures on computational efficiency for randomly generated instances, using the Gurobi solver. We find that by making the quadratic cost matrix negative semidefinite, we improve solve times, and that solving the problem as a quadratic minimization problem outperforms linearization approaches.

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

Compressive imaging with total variation regularization and application to auto-calibration of parallel magnetic resonance imaging

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

An important task in imaging is to recover an image from samples of its Fourier transform. With compressed sensing, this is done by applying a sparsifying transform and solving a l1 minimization problem. One possible transform is the discrete gradient operator, in which case penalizing the l1 norm leads to Total Variation (TV) minimization. We present new recovery guarantees for TV regularization in arbitrary dimensions using two sampling strategies: uniform random Fourier sampling and variable density Fourier sampling. In particular, we determine a near-optimal choice of sampling density in any dimension. Our theoretical and numerical results show that variable density Fourier sampling increases the stability and robustness of TV regularization over uniform random Fourier sampling. As an application, we consider auto-calibration in parallel magnetic resonance imaging (pMRI). We develop a two-step algorithm: firstly, using sparse regularization to recover the coil images; secondly, using linear least squares to obtain the overall image.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Ben Adcock
Manfred Trummer
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Explicitly representing vector bundles over elliptic curves

Author: 
Date created: 
2019-08-02
Abstract: 

Algebraic vector bundles are a construction useful for studying the geometry of varieties; they are objects which associate a vector space to each point of the variety in a "polynomial" fashion. These bundles can be explicitly represented via transition matrices, which encode how the vector spaces vary as one moves along the variety. In 1957, Sir Michael Atiyah showed that every indecomposable bundle over a smooth elliptic curve was determined by a point on the curve, and two invariants; the rank and degree. However, his work is not entirely explicit---using his results, we obtain explicit representations of the bundles in terms of transition matrices. As an application, we present a constructive proof of global generation for certain indecomposable bundles over elliptic curves.

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

Aggregation-diffusion phenomena in domains with boundaries

Author: 
Date created: 
2019-07-18
Abstract: 

This thesis is concerned with a class of mathematical models for the collective behaviour of autonomous agents, or particles, in general spatial domains, where particles exhibit pairwise interactions and may be subject to environmental forces. Such models have been shown to exhibit non-trivial behaviour due to interactions with the boundary of the domain. More specifically, when there is a boundary, it has been observed that the swarm of particles readily evolves into unstable states. Given this behaviour, we investigate the regularizing effect of adding noise to the system in the form of Brownian motion at the particle level, which produces linear diffusion in the continuum limit. To investigate the effect of linear diffusion and interactions with spatial boundaries on swarm equilibria, we analyze critical points of the associated energy functional, establishing conditions under which global minimizers exist. Through this process we uncover a new metastability phenomenon which necessitates the use of external forces to confine the swarm. We then introduce numerical methods for computing critical points of the energy, along with examples to motivate further research. Finally, we consider the short-time dynamics of the stochastic particle system as diffusion approaches zero. We verify that the analytical convergence rate in the zero diffusion limit is represented in numerics, which we believe validates and motivates the use of stochastic particle simulations for further exploration of the regularizing effect of Brownian motion on aggregation phenomena in domains with boundaries.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Razvan C. Fetecau
Ralf Wittenberg
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Cops and robbers on geometric graphs and graphs with a set of forbidden subgraphs

Author: 
Date created: 
2019-06-18
Abstract: 

In this thesis we study the game of cops and robbers on some special class of graphs, including planar graphs and geometric graphs. Moreover, under some conditions on graph diameter, we characterize all sets H of graphs with bounded diameter for which H-free graphs are cop-bounded. Furthermore, we extend our characterization to the case of cop-bounded classes of graphs defined by a set H of forbidden graphs such that the components of members of H have bounded diameter.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Ladislav Stacho
Bojan Mohar
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

On the density of parameterizations of generalized Fermat equations of signature (2,3,3) that produce locally primitive solutions

Date created: 
2019-05-15
Abstract: 

We consider the equations Ax^2+By^3=Cz^3, where A,B,C are square-free and pairwise co-prime integers. A solution (x,y,z) is called primitive if it consists of co-prime integers. Adapting earlier work for the equations x^2+y^3=Cz^3, we show that primitive solutions give rise to integer Klein forms of degree four, with discriminant A^3B^2C . Whether Klein forms come from primitive solutions is determined by local conditions. We show that for primes p dividing B, there are exactly four GL_2(Q_p)-equivalence classes of Klein forms that are relevant, and that exactly half of those classes come from Z_p-primitive solutions. We also show that if we set A=1, then further restricting B,C to square-free and co-prime integers leaves us with an asymptotically positive proportion of triples.

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

Sparse and low rank approximation via partial regularization: Models, theory and algorithms

Author: 
Date created: 
2019-02-28
Abstract: 

Sparse representation and low-rank approximation are fundamental tools in fields of signal processing and pattern analysis. In this thesis, we consider introducing some partial regularizers to these problems in order to neutralize the bias incurred by some large entries (in magnitude) of the associated vector or some large singular values of the associated matrix. In particular, we first consider a class of constrained optimization problems whose constraints involve a cardinality or rank constraint. Under some suitable assumptions, we show that the penalty formulation based on a partial regularization is an exact reformulation of the original problem in the sense that they both share the same global minimizers. We also show that a local minimizer of the original problem is that of the penalty reformulation. Specifically, we propose a class of models with partial regularization for recovering a sparse solution of a linear system. We then study some theoretical properties of these models including existence of optimal solutions, sparsity inducing, local or global recovery and stable recovery. In addition, numerical algorithms are proposed for solving those models, in which each subproblem is solved by a nonmonotone proximal gradient (NPG) method. Despite the complication of the partial regularizers, we show that each proximal subproblem in NPG can be solved as a certain number of one-dimensional optimization problems, which usually have a closed-form solution. The global convergence of these methods are also established. Finally, we compare the performance of our approach with some existing approaches on both randomly generated and real-life instances, and report some promising computational results.

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