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

Receive updates for this collection

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): 
Supervisor(s): 
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): 
Supervisor(s): 
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): 
Supervisor(s): 
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): 
Supervisor(s): 
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): 
Supervisor(s): 
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): 
Supervisor(s): 
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): 
Supervisor(s): 
Zhaosong Lu
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Topics in quadratic binary optimization problems

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

In this dissertation, we consider the quadratic combinatorial optimization problem (QCOP) and its variations: the generalized vertex cover problem (GVC), the quadratic unconstrained binary optimization problem (QUBO), and the quadratic set covering problem (QSCP). We study these problems as discussed below. For QCOP, we analyze equivalent representations of the pair (Q, c), where Q is a quadratic cost matrix and c is a linear cost vector. We present various procedures to obtain equivalent representations, and study the effect of equivalent representations on the computation time to obtain an optimal solution, on the quality of the lower bound values obtained by various lower bounding schemes, and on the quality of the heuristic solution. The first variation of QCOP is GVC, and we show that GVC is equivalent to QUBO and also equivalent to some other variations of GVC. Some solvable cases are identified and approximation algorithms are suggested for special cases. We also study GVC on bipartite graphs. QUBO is the second variation of QCOP. For QUBO, we analyze several heuristic algorithms using domination analysis. We show that for QUBO, if any algorithm that guarantees a solution no worse than the average, has a domination ratio of at least 1/40. We extend this result to the maximum and minimum cut problems; maximum and minimum uncut problems; and GVC. We also study the QUBO when Q is: 1) (2d + 1)-diagonal matrix, 2) (2d + 1)-reverse-diagonal matrix, and 3) (2d+1)-cross diagonal matrix, and show that these cases are solvable in polynomial time when d is fixed or is of O(log n). The last variation of QCOP is QSCP. For QSCP, we identify various inaccuracies in the paper by R. R. Saxena and S. R. Arora, A linearization technique for solving the Quadratic Set Covering Problem, Optimization, 39 (1997) 33-42. In particular, we observe that their algorithm does not guarantee optimality, contrary to what is claimed. We also present the mixed integer linear programming formulations (MILP) for QSCP. We compare the lower bounds obtained by the linear programming relaxations of MILPs, and study the effect of equivalent representations of QSCP on these MILPs.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Abraham Punnen
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

The quadratic travelling salesman problem: complexity and approximation

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

In this thesis we study the Quadratic Travelling Salesman Problem (QTSP) which generalizes the well-studied Traveling Salesman Problem and several of its variations. QTSP is to find a least cost Hamiltonian cycle in an edge-weighted graph, where costs are defined for all pairs of edges contained in the Hamilton cycle. This is a more general version than the one that appears in the literature as the QTSP, denoted here as the adjacent quadratic TSP, which only considers costs for pairs of adjacent edges. We give a complete characterization of the QTSP linearization problem and give a polynomial time algorithm to find a linearization whenever one exists. The fixed-rank QTSP is introduced as a restricted version of the QTSP where the cost matrix has fixed rank p. We study QTSP by examining the complexity of searching exponential neighbourhoods for QTSP, the fixed-rank QTSP and the adjacent quadratic TSP. We develop pseudopolynomial time algorithms for many of these special cases, and give FPTAS whenever possible. Polynomial algorithms are given for each special case which is not NP-hard.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Abraham Punnen
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Well-posedness of a Gas-disk Interaction System

Author: 
Peer reviewed: 
No, item is not peer reviewed.
Date created: 
2019-08
Abstract: 

This thesis concerns a gas-disk interaction system: the disk is immersed in a gas and acted on by a drag force and an external force. The evolution of the system is described by a coupled system of integro-differential equations. More specifically, we use a pure kinetic transport equation to model the gas and a Newton’s Second Law ODE to model the disk. The two are coupled via the drag force exerted on the disk by the gas and the boundary condition for the gas colliding with the disk.

Systems of this type have been extensively studied in the literature, both analytically and numerically. To the best of our knowledge, existing works focus on existence of nearequilibrium solutions and their long-time behaviour. However, uniqueness of solutions has not been investigated previously. In the first part of the thesis we will give the first rigorous proof of existence and uniqueness of solutions for general initial data and external forcing.

The most important physical feature of this system is its inherent recursivity: particles can collide with the disk time and time again. Recognizing this structure and introducing recursivity into the equations by the means of gas decomposition is the key to obtaining the well-posedness result.

In the second part of the thesis we will present a simple numerical method for computing the trajectory of the disk using the aforementioned gas decomposition. We will contrast it with methods used previously, and also use it to show that considering only one or two precollisions for the gas particles is sufficient to accurately compute the density distribution of the gas and the velocity of the disk.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Weiran Sun
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.