New Summit website coming in May 2021!

                   Check the SFU library website for updates.

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

Receive updates for this collection

The minimax linear fractional programming problem with binary variables

Author: 
Date created: 
2020-08-14
Abstract: 

The single ratio linear fractional programming problem when the denominator of the objective function ratio is non-negative is solvable in polynomial time. This result extends to several classes of optimization problems with binary variables. However, when the denominator is allowed to take both positive and negative values, even the unconstrained problem with binary variables is NP-hard. Generalization of this problem where a sum of ratios is also well studied. Experimental results on this however are restricted to non-negative denominators. In this thesis we consider the minimax version of the multi-ratio problem with binary variables. The continuous version of the minimax problem is also well-studied but to the best of our knowledge not much research work has been done on the binary version. We present various mathematical programming formulations of the problem for the case of non-negative denominators as well as arbitrary denominators. We also present algorithms to overcome some of the computational difficulties. Extensive computational analysis has been carried under the scenarios of unconstrained problems, problems with a knapsack constraint, and problems with assignment constraints to assess the relative merits of the models. The analysis disclosed some interesting insights into the structure of the problems.

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

From eigenbeauty to large-deformation horror

Date created: 
2020-08-14
Abstract: 

In this thesis we investigate eigenproblems arising in spectral geometry and in the theory of linear elasticity, and numerically study the mechanics of skeletal muscles in three dimensions. We first introduce a novel framework based on a combined finite element-Bayesian optimization strategy to tackle problems in spectral optimization. This method is used to investigate the Pólya-Szegö conjecture for the Dirichlet eigenvalues of the Laplacian on polygons and a similar conjecture for the Steklov eigenvalues for the Laplacian is proposed. We next explore four different eigenproblems for the Lamé operator in linear elasticity. For each we establish the existence of a countable (finite or infinite) set of eigenpairs. The first one relates to Steklov eigenpairs for elasticity where the spectral parameter appears on a Robin type boundary condition. The second eigenproblem concerns eigenmodes whose tangential traction and normal displacement on the boundary are constrained. The third eigenproblem refers to eigenmodes whose normal traction and tangential displacement are fixed on the boundary. We finally consider the Jones eigenvalue problem: elastic modes are assumed to be traction free on the boundary with the extra condition that they must be purely tangential to the boundary. For each eigenproblem, new versions of Korn’s inequalities are proven to establish the existence of a point spectrum. Finally, we present a new numerical framework to computationally simulate the large deformations of skeletal muscles in three dimensions. A semi-implicit method in time and finite element method in space are coupled to approximate the solutions of the nonlinear dynamic system that governs the deformation of these tissues. This framework is later utilized to explore questions on the effects of density and inertia in muscle performance, to investigate the energy distribution in muscle during isometric contractions, and to study the energetics of muscles during compression tests on the surface of the tissues.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Nilima Nigam
James Wakeling
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

The maximum weight stable set problem with a budget constraint

Author: 
Date created: 
2020-08-21
Abstract: 

We consider the maximum weight stable set problem with an additional budget constraint (BSS) which is also known as the knapsack problem with conflict-pair constraints. A unifying 0-1 programming formulation is given that subsumes two well-studied formulations for the problem and we analyze the strength of the LP relaxation of this model. Also, we present an alternative view of the extended cover inequalities for the knapsack polytope and using this, along with other upper bounds on the stability number of a graph, strengthened 0-1 linear programming formulations of BSS are presented. Further, we study two binary quadratic formulations of BSS and explore the relationship between its linearizations and our 0-1 linear programming formulations. Results of extensive computational analysis carried out using our models are presented that compares various features of the models and their relative merits.

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

Global guarantees from local knowledge: Stable and robust recovery of sparse in levels vectors

Date created: 
2020-08-17
Abstract: 

The model of sparse vectors has proven invaluable for compressive imaging, allowing for signal recovery from very few linear measurements. Recently however, the structured sparsity model of sparsity in levels has inspired a new generation of effective acquisition and reconstruction modalities. Moreover this local structure arises in various areas of signal processing such as parallel acquisition, radar, and the sparse corruptions problem. Reconstruction strategies for sparse in levels signals have previously relied on a suitable convex optimization program. While iterative and greedy algorithms can outperform convex optimization and have been studied extensively in the case of standard sparsity, little is known about their generalizations to the sparse in levels setting. We bridge this gap by showing new stable and robust recovery guarantees for sparse in level variants of the iterative hard thresholding and the compressive sampling matching pursuit algorithms. Our theoretical analysis generalizes recovery guarantees currently available in the case of standard sparsity and favorably compare to sparse in levels guarantees for weighted l1 minimization, both in accuracy and computational time. In addition, we propose and numerically test an extension of the orthogonal matching pursuit algorithm for sparse in levels signals.

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

Internal wave attractors and spectra of zeroth-order pseudo-differential operators

Date created: 
2020-08-12
Abstract: 

The propagation of internal gravity waves in stratified media (such as those found in ocean basins and lakes) leads to the development of geometrical patterns called "attractors". These structures accumulate much of the wave energy and make the fluid flow highly singular. Microlocal analysts have recently related this behaviour to the spectral properties of an underlying nonlocal zeroth-order pseudo-differential operator that characterizes the dynamics of this problem. In this work, we analyze this phenomenon from a numerical analysis perspective. First, we propose a high-order pseudo-spectral method to solve the evolution problem, whose long-term behaviour is known to be non-square-integrable. Then, we use similar tools to discretize the corresponding eigenvalue problem. Since the eigenvalues are embedded in a continuous spectrum, their computation is based on viscous approximations. Finally, we explore the effect that the embedded eigenmodes have in the long-term evolution of the system.

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

Brauer-Severi varieties associated to twists of the Burkhardt quartic

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

The Burkhardt quartic is a projective threefold which, geometrically, is birational to the moduli space of abelian surfaces with full level-3 structure. We study this moduli interpretation of the Burkhardt quartic in an arithmetic setting, over a general field $k$. As it turns out, some twists of the Burkhardt quartic have a nontrivial field-of-definition versus field-of moduli obstruction. Classically, if a twist has a $k$-rational point then the obstruction can be computed as the Brauer class of an associated conic. Using representation theory, we show how to compute the obstruction without assuming the existence of a $k$-rational point, giving rise to an associated 3-dimensional Brauer-Severi variety rather than a conic. This Brauer-Severi variety itself has a related moduli interpretation.

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

Cops and robbers on Cayley graphs and embedded graphs

Author: 
Date created: 
2020-08-12
Abstract: 

We consider the game of cops and robbers, which is a game played on a finite graph G by two players, Alice and Bob. Alice controls a team of cops, and Bob controls a robber, both of which occupy vertices of G. On Alice's turn, she may move each cop to an adjacent vertex or leave it at its current position. Similarly, on Bob's turn, he may move the robber to an adjacent vertex or leave it at its current position. Traditionally, Alice wins the game when a cop occupies the same vertex as the robber---that is, when a cop captures the robber. Conversely, Bob wins the game by letting the robber avoid capture forever. In a variation of the game, Alice wins the game when each neighbor of the robber's vertex is occupied by a cop---that is, when cops surround the robber. We will consider both of these winning conditions. The most fundamental graph invariant with regard to the game of cops and robbers is the cop number of a graph G, which denotes the minimum number of cops that Alice needs in order to have a winning strategy on G. We will introduce new techniques that may be used to calculate lower and upper bounds for the cop numbers of certain Cayley graphs. In particular, we will show that the well-known Meyniel's conjecture holds for both undirected and directed abelian Cayley graphs. We will also introduce new techniques for establishing upper bounds on the cop numbers of surface-embedded graphs bounded by the genus of the surface in the surrounding win condition.

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

Colouring complexes of planar triangulations and the line graphs of cubic graphs

Author: 
Date created: 
2020-08-17
Abstract: 

In order to study the parity of a k-colouring, Tutte introduced the notion of a k-colouring complex in 1969. Given a k-colourable graph X, the k-colouring complex Bk(X) is the graph which has all the independent sets which are colour classes of X as its vertices and two vertices A and B in V (Bk(X)) joined by an edge if the colour classes A and B appear together in a k-colouring of X. Subsequently, Fisk proved that the graph Bk(X) is k-colourable and discovered infinite families of graphs for which Bk(Bk(X)) is isomorphic to X. In this thesis, we resolve a question Tutte posed about the 4-colouring complex at one of his final public lectures in 1999. He asked whether the 4-colouring complex of a planar triangulation could have two components in which all colourings have the same parity. In response, we construct triangulations of the plane whose 4-colouring complexes have arbitrarily many even and odd components. Furthermore, we exhibit an infinite family of 4-connected triangulations of the plane whose 4-colouring complexes have an arbitrarily large number of even components, as well as a number of 5-connected triangulations of the plane whose 4-colouring complexes have at least two components in which all colourings have the same parity. In the later chapters of this thesis, we continue our study of the k-colouring complex, discovering many new infinite families of graphs X for which Bk(Bk(X)) is isomorphic to X. We call these graphs reflexive graphs. Most notably, if G is a 3-edge-colourable, connected, cubic (possibly including half-edges) outerplanar graph, we prove that L(G) is reflexive if and only if G is triangle-free. In order to establish this result, we show how to reduce questions about the reflexivity of a connected graph to questions about the reflexivity of its 2-edge-connected components. Then we determine conditions under which subdividing an edge preserves reflexivity. These two novel theorems are of independent interest. In particular, we apply the latter theorem to prove that theta graphs have reflexive line graphs.

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

Toric degenerations of rational curves of degree n+2 in P^n

Author: 
Date created: 
2020-08-11
Abstract: 

A common technique for studying a projective variety relies on finding a flat degeneration to a toric variety, which is a variety described by combinatorial data. However, it is not clear in general how to find such a degeneration or even if one exists. Ilten and Wrobel have shown that a very general rational plane curve of degree at least four does not admit this degeneration. In this thesis, we investigate the existence of toric degenerations for the special case of projective rational curves of degree n+2 in P^n where n≥3. Using work of Buczyński, Ilten, and Ventura, we obtain explicit parametrizations for all rational curves of degree n+2 in P^n and characterize which of these admit such a degeneration. Our results show that for these curves, the problem of having a toric degeneration can be decided algorithmically.

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

Safe coverage of compact domains for second order dynamical systems

Author: 
Date created: 
2020-08-07
Abstract: 

Autonomous systems operating in close proximity with each other to cover a specified area has many potential applications, but coordination and safety are two fundamental challenges. For coordination, we propose a locally asymptotically stable distributed coverage controller for moving compact domains for two types of vehicles with second order dynamics (double integrator and fixed-wing aircraft) with bounded input forces. This control policy is based on artificial potentials and consensus forces designed to promote desired vehicle-domain and inter-vehicle separations and relative velocities. We prove that certain coverage configurations are locally asymptotically stable. For safety, we establish minimal energy conditions for collision free motion and we utilize Hamilton-Jacobi (HJ) reachability theory for pairwise collision avoidance. Rather than computing numerical solutions of the associated HJ partial differential equation, we derive an analytical solution for the double integrator vehicle. We demonstrate our approach in several numerical simulations involving convex and non-convex moving domains.

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