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

Receive updates for this collection

Analysis of an Age-Structured Model of Chemotherapy-Induced Neutropenia

Date created: 
2014-11-19
Abstract: 

Neutropenia is a blood disorder characterized by low levels of neutrophils and is a common side effect of chemotherapy. Administration of granulocyte-colony stimulating factor (G-CSF) is a typical treatment that helps stabilize the level of neutrophils. However, it is not known if changes to the frequency and dosage of administered G-CSF will lead to better treatment. We analyze a nonlinear hyperbolic system of coupled integro-differential equations aimed at quantifying the effect of treatment plans on patients with chemotherapy-induced neutropenia. We show how this age-structured model can be decoupled for short time. We then investigate the equivalence of an integral equation with a related nonlinear PDE and prove existence and uniqueness of solutions of the integral equation. This is used to finally demonstrate existence and uniqueness of solutions to the full PDE system.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Nilima Nigam
Razvan Fetecau
Department: 
Science:
Thesis type: 
(Thesis) M.Sc.

The Bipartite Boolean Quadratic Programming Problem

Date created: 
2014-11-25
Abstract: 

We consider the Bipartite Boolean Quadratic Programming Problem (BQP01), which generalizes the well-known Boolean Quadratic Programming Problem (QP01). The model has applications in graph theory, matrix factorization and bioinformatics, among others. BQP01 is NP-hard. The primary focus of this thesis is on studying algorithms and polyhedral structure from a linearization of its integer programming formulation. We show that when the rank of the associated m x n cost matrix Q is fixed, BQP01 can be solved in polynomial time. Further, for the rank one case, we provide an O(n log n) algorithm. The complexity reduces to O(n) with additional assumptions. Further, we observe that BQP01 is polynomially solvable if m = O(log n). Similarly, when the minimum negative eliminator of Q is O(log n), the problem is shown to be polynomially solvable. We then develop several heuristic algorithms for BQP01 and analyze them using domination analysis. First, we give a closed-form formula for the average objective function value A(Q, c, d) of all solutions. Computing the median objective function value however is shown to be NP-hard. We prove that any solution with objective function value no worse than A(Q, c, d) dominates at least 2^(m+n-2) solutions and provide an upper bound for the dominance ratio of any polynomial time approximation algorithms for BQP01. Further, we show that some powerful local search algorithms could produce solutions with objective function value worse than A(Q, c, d) and propose algorithms that guarantee a solution with objective function value no worse than A(Q, c, d). Finally, we study the structure of the polytope BQP^(m;n) resulting from linearization of BQP01. We develop various approaches to obtain families of valid inequalities and facet-defining inequalities of BQP^(m,n) from those of other related polytopes. These approaches include rounding coeffcients, using the linear transformation between BQP^(m,n) and the corresponding cut polytope, and applying triangular elimination.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Abraham Punnen
Tamon Stephen
Department: 
Science: Mathematics
Thesis type: 
(Thesis) Ph.D.

Enumeration of Set Partitions Refined by Crossing and Nesting Numbers

Author: 
Date created: 
2014-12-02
Abstract: 

The standard representation of set partitions gives rise to two natural statistics: a crossing number and a nesting number. Chen, Deng, Du, Stanley, and Yan (2007) proved, via a non-trivial bijection involving sequences of Young tableaux that these statistics have a symmetric joint distribution. Recent results by Marberg (2013) has lead to algorithmic tools for the enumeration of set partitions with fixed crossing number and fixed nesting number. In this thesis we further consider set partitions refined by these two statistics. These sub-classes can be recognized by finite automata, and consequently have rational generating functions. Our main contribution is an investigation into the structure of the automata, the corresponding adjacency matrices, and the generating functions.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Marni Mishna
Lily Yen
Department: 
Science:
Thesis type: 
(Thesis) M.Sc.

Optimization Methods for Sparse Approximation

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

In the last two decades, there are numerous applications in which sparse solutions are concerned. Mathematically, all these applications can be formulated into the L0 minimization problems. In this thesis, we first propose a novel augmented Lagrangian (AL) method for solving the L1-norm relaxation problems of the original L0 minimization problems and apply it to our proposed formulation of sparse principal component analysis (PCA). We next propose penalty decomposition (PD) methods for solving the original L0 minimization problems in which a sequence of penalty subproblems are solved by a block coordinate descent (BCD) method. For the AL method, we show that under some regularity assumptions, it converges to a stationary point. Additionally, we propose two nonmonotone gradient methods for solving the AL subproblems, and establish their global and local convergence. Moreover, we apply the AL method to our proposed formulation of sparse PCA and compare our approach with several existing methods on synthetic, Pitprops, and gene expression data, respectively. The computational results demonstrate that the sparse {\it principal components} (PCs) produced by our approach substantially outperform those by other methods in terms of total explained variance, correlation of PCs, and orthogonality of loading vectors. For the PD methods, under some suitable assumptions, we establish some convergence results for both inner (the BCD method) and outer (the PD method) iterations, respectively. We test the performance of our PD methods by applying them to sparse logistic regression, sparse inverse covariance selection, and compressed sensing problems. The computational results demonstrate that when solutions of same cardinality are sought, our approach applied to the L0-based models generally has better solution quality and/or speed than the existing approaches that are applied to the corresponding L1-based models. Finally, we adapt the PD method to solve our proposed wavelet frame based image restoration problem. Some convergence analysis of the adapted PD method for this problem are provided. Numerical results show that the proposed model solved by the PD method can generate images with better quality than those obtained by either analysis based approach or balanced approach in terms of restoring sharp features as well as maintaining smoothness of the recovered images.

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

Quantifying the Effect of Open-Mindedness on Opinion Dynamics and Advertising Optimization

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

Group opinion dynamics shape our world in innumerable ways. Societal aspects ranging from the political parties we support to the economic decisions we make in our daily lives are all directly af- fected in some way by group opinion dynamics. This makes understanding and potentially being able to predict the complex inter-relationships between individuals’ opinions and group opinion dynam- ics invaluable both scientifically and economically. We propose an aggregation model incorporating ingroup-outgroup dynamics, as well as media influence, to establish potential causal relationships between various types of social interaction and social phenomena such as the occurrence of group consensus and the hostile media effect. We further apply our model to simplified commercial appli- cations relating to advertisement optimization to determine the optimal proportion of a population to target with advertising in order to maximize opinion shift while fixing cost.

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

On tree hook length formulae, Feynman rules and B-series

Date created: 
2014-09-25
Abstract: 

This thesis relates similar ideas from enumerative combinatorics, Hopf algebraic quantum field theory and differential analysis. Hook length formulae, from enumerative combinatorics, are equations that can lead to bijections between tree classes and other combinatorial classes. Feynman rules are maps used in quantum field theory to generate integrals from particle interaction diagrams. Here we consider Feynman rules from the Hopf algebra perspective. B-series are powers series that sum over trees and are used in differential analysis to analyze Runge-Kutta methods. The aim of this thesis is to bring together the ideas of the three communities. We show how to use differential equations to obtain new hook length formulae. Some of these new hook length formulae result in new combinatorial bijections. We use hook length formulae to express differential equations combinatorially. We also provide a generalization to hook length. Finally we include a catalogue of known hook length formulae.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Karen Yeats
Department: 
Science:
Thesis type: 
(Thesis) M.Sc.

On Jacobians of dimension 2g that decompose into Jacobians of dimension g

Date created: 
2014-08-12
Abstract: 

In this thesis we describe a family of Jacobian varieties of non-hyperelliptic genus 2g curves that are isogenous to a product of Jacobians of genus g curves in a specific way. For any hyperelliptic genus g curve C we construct a 2-parameter family of hyperelliptic genus g curves H with J(H)[2] isomorphic to J(C)[2], and a generically non-hyperelliptic curve A such that there is an isogeny from J(C)  J(H) to J(A) whose kernel is the graph of the isomorphism taking J(H)[2] to J(C)[2]. This is accomplished by first showing that C can be considered as a subcover of a Galois cover of a P1 that has A and H naturally arising as subcovers and then showing the naturally occurring isogeny relations have the desired kernel. We also list some corollaries to the main result and provide a magma script to generate non-hyperelliptic genus 4 curves that have curious automorphism groups.

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

Laplace-Beltrami spectra as ‘Shape-DNA’ of surfaces using the closest point method

Date created: 
2014-07-28
Abstract: 

The need to compare two separate manifolds arises in a wide range of applications. In this thesis, ‘Shape-DNA’, i.e. the eigenvalues of the Laplace-Beltrami operator, are used to create a numerical signature representing an individual object. The corresponding spectrum is isometry invariant, which means it is independent of manifold representations such as parameterization or spatial positioning. Therefore, checking if two objects are isometry invariants does not require any alignment (registration/localization) of the objects but only comparing their spectra. We determine the Shape-DNA using the closest point method on the manifold. In 3D we illustrate the process for triangulated mesh and point cloud surfaces. Convergence studies demonstrate that the convergence rates correspond to those of the underlying finite difference methods. A 2D multidimensional scaling plot illustrates how identical objects are mapped to the same spot and similar objects form groups based on the Shape-DNA’s.

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

Combinatorial Hopf Algebras On Generating Trees And Certain Generating Graphs

Author: 
Date created: 
2014-07-29
Abstract: 

Hopf algebras capture how combinatorial objects can be decomposed into their subparts in different ways. Generating trees and generating graphs provide one structured way to understand many combinatorial classes. Furthermore, Hochschild 1-cocycle maps of renormalization Hopf algebras play an important role in quantum field theories but are not well known in combinatorics. In the generalised atmospheric method for sampling self-avoiding polygons, there is a weight function which deals with overcounting and hints at a connection with the 1-cocycle maps. Both of these combinatorial objects can be represented by generating graphs. As a first step towards understanding this connection, we provide two ways to construct Hopf algebras on generating trees through a normalizing map φ ̃. One is concatenation and deshuffle type and the other is shuffle and deconcatenation type. We also construct an incidence Hopf algebra on certain generating graphs and construct a Hopf algebra on self-avoiding polygons.

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

An agent-based approach to modelling chronic offenders

Date created: 
2014-08-06
Abstract: 

Police departments are required to ensure the safety of the general population using limited resources. Chronic offenders are a major drain on police resources. The precise definition of a chronic offender may change between jurisdictions but the general concept refers to a class of offenders who commit many crimes in short intervals. Unlike other offenders who typically stop committing crimes early in life, chronic offenders continue committing crimes late in life. Understanding this class of offenders allows police departments to modify their operational strategies and make better use of their resources. We develop an agent-based model of how chronic offenders move between incarceration and freedom. Under appropriate limits we convert the agent-based model to a system of differential equations which is analyzed using established differential equation methods.

Document type: 
Thesis
File(s): 
Senior supervisor: 
JF Williams
Alexander Rutherford
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.