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

Receive updates for this collection

Double Triangle Descendants of K5

Author: 
Date created: 
2017-12-05
Abstract: 

Feynman diagrams in phi^4 theory can be represented as 4-regular graphs. The Feynman integral, or even the Feynman period, is very hard to calculate. A graph invariant, called the c2-invariant, is conjecturally thought to be equal for two graphs when their periods are equal. Double triangle reduction of 4-regular graphs is known to preserve the c2-invariant. Double triangle descendants of K5 all have a c2-invariant that is a constant -1, and conjecturally, are the only graphs with this c2-invariant. This thesis studies the structure of K5-descendants to gain insight on the c2-invariant, get closer to solving the conjecture, and to study what is an interesting combinatorial operation in its own right. It will be shown that the minimum number of triangles in a descendant is 4. Closed-form generating functions are found for three families of K5-descendants. Two encodings, one for n-zigzags, and a general one for all K5-descendants, are found.

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

Finding beauty in the dissonance: Analysis and applications of Bayesian inverse problems

Author: 
Date created: 
2017-10-27
Abstract: 

Inverse problems – the process of recovering unknown parameters from indirect measurements – are encountered in various areas of science, technology and engineering including image processing, medical imaging, geosciences, astronomy, aeronautics engineering and machine learning. Statistical and probabilistic methods are promising approaches to solving such problems. Of these, the Bayesian methods provide a principled approach to incorporating our existing beliefs about the parameters (the prior model) and randomness in the data. These approaches are at the forefront of extensive current investigation. Overwhelmingly, Gaussian prior models are used in Bayesian inverse problems since they provide mathematically simple and computationally efficient formulations of important inverse problems. Unfortunately, these priors fail to capture a range of important properties including sparsity and natural constraints such as positivity, and so we are motivated to study non-Gaussian priors. In this thesis we provide a systematic study of the theory and applications of Bayesian approaches to inverse problems with non-Gaussian priors. We develop the theory of well-posedness of infinite-dimensional Bayesian inverse problems with convex, heavy-tailed or infinitely divisible prior measures. We also introduce new prior measures that aim to model compressible or sparse parameters. Next, we demonstrate the applications of Bayesian approaches to important inverse problems in industrial applications: the estimation of emission rates of particulate matter, and the estimation of acoustic aberrations in ultrasound treatment. We propose two Bayesian approaches for the problem of estimating the emission rates of particulate matter into the atmosphere from far field measurements of deposition. Next, we present a Bayesian method for estimation of acoustic aberrations in high intensity focused ultrasound treatment of tissue in the brain using magnetic resonance images. The final contribution of this thesis is a systematic construction and convergence analysis of regularizations of the Dirac delta distribution. Point sources arise naturally in many models and we discuss smooth regularizations of these.

Document type: 
Thesis
File(s): 
Senior supervisor: 
John M. Stockie
Nilima Nigam
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Sap flow and heat transport in trees: An asymptotic and numerical study

Date created: 
2017-10-12
Abstract: 

Transport of fluid and heat inside a tree, and the interchange of water and energy between the tree and the environment, are topics that have been and continue to be areas of active research in plant physiology, agriculture and environmental studies. Many models have been proposed to describe the flow of sap inside the tree, and to connect it to the driving transpiration rate, with various levels of complexity, and with different levels of abstraction. Most existing models are 1D models and many only attempt to get numerical results, without much analysis. For our work, we adopt a porous medium model that has been verified experimentally [Chuang et al., Ecological Modelling, 191(3):447-468, 2006]. We generalize this 1D model to a 3D axisymmetric geometry, where flow is transpiration driven and has anisotropic and spatially dependent hydraulic conductivity. Through asymptotic analysis, we derive approximate solutions that produce the axial and radial trunk sap fluxes for a given transpiration function. We validate the analytical solutions using a second order finite difference scheme. Next we use our solution formulas to tackle the inverse problem of determining spatial and temporal components of transpiration given a discrete set measurements of the trunk sap flux. Finally, we compare our results to some experimental data on radial variations of sap flux. As for the heat transport problem, previous work related to trees discuss special cases of the problem, while giving detailed accounts and specific formulas of the boundary conditions, like wind and solar radiation effects. Most of this work does not include the possible effects of advection owing to sap flux, and does not discuss the effects of spatial variation in saturation on the thermal diffusivity. Assuming local thermal equilibrium for porous media, we propose a simple advection-diffusion model, with general boundary conditions, and derive Fourier-Bessel series solutions for the various possible cases suggested by dimensionless parameters.

Document type: 
Thesis
File(s): 
Senior supervisor: 
John Stockie
Weiran Sun
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Coloring cayley tables of finite groups

Date created: 
2017-08-08
Abstract: 

The chromatic number of a latin square L, denoted χ(L), is defined as the minimum number of partial transversals needed to cover all of its cells. It has been conjectured that every latin square L satisfies χ(L) ≤ |L| + 2. If true, this would resolve a longstanding conjecture, commonly attributed to Brualdi, that every latin square has a partial transversal of length |L|−1. Restricting our attention to Cayley tables of finite groups, we prove two results. First, we constructively show that all finite Abelian groups G have Cayley tables with chromatic number |G|+2. Second, we give an upper bound for the chromatic number of Cayley tables of arbitrary finite groups. For |G| ≥ 3, this improves the best-known general upper bound from 2|G| to 3 |G|, while yielding an even stronger result in infinitely many cases.

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

Solving multivariate diophantine equations and their role in multivariate polynomial factorization

Date created: 
2017-08-14
Abstract: 

Multivariate polynomial factorization over integers via multivariate Hensel lifting (MHL) is one of the central areas of research in computer algebra. Most computer algebra platforms, such as Maple, Magma and Singular, implement Wang's incremental design of MHL which lifts the factors one variable at a time and one degree at a time. At each step MHL must solve a multivariate diophantine problem (MDP) which Wang solves using the same idea; lifting the solutions one variable and one degree at a time. Although this performs well when the evaluation points are mostly zero, it performs poorly when there are many non-zero evaluation points as the number of MDP problems to be solved can be exponential in the number of variables. In this thesis we introduce a new non-recursive solution to the MDP which explicitly exploits the sparsity of the solutions to the MDP. We use sparse interpolation techniques and exploit the fact that at each step of MHL, the solutions to MDP's are structurally related. We design a probabilistic sparse Hensel lifting algorithm (MTSHL) and give a complete average case complexity analysis for it. We describe a series of experiments based on our implementation of MTSHL, compare its efficiency with Wang's algorithm, and show that MTSHL performs better for many practical applications. We also show that previous probabilistic approaches proposed for MHL as an alternative to Wang's algorithm are not practical whereas MTSHL is practical and the running time is predictable.

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

The Multiplicative Assignment Problem

Author: 
Date created: 
2017-07-06
Abstract: 

The quadratic assignment problem (QAP) is an extensively studied combinatorial optimization problem. The special case of QAP where the cost matrix is of rank one is called the multiplicative assignment problem (MAP). MAP is not well studied in literature, particularly in terms of experimental analysis of algorithms. In this thesis we present some mixed integer linear programming formulations and compare their selective strength using experimental analysis. We also present exact and heuristic algorithms to solve MAP. Our heuristic algorithms include improvements in existing FPTAs, as well as local search and tabu search enhancements. Results of extensive experimental analyses are also reported.

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

The realisability of γ-graphs

Date created: 
2017-08-14
Abstract: 

The γ-graph γ·G of a graph G is the graph whose vertices are labelled by the minimum dominating sets of G, in which two vertices are adjacent when their corresponding minimum dominating sets differ in exactly one element. We give an explicit construction of a graph having an arbitrary prescribed set of minimum dominating sets. We show as a corollary that "labellable implies realisable for γ-graphs": if the vertices of a graph H can be labelled by distinct sets of the same size, in a manner consistent with the adjacency condition for γ-graphs, then H = γ·G for some graph G. We use this corollary to extend the classification of γ-graphs, due to Lakshmanan and Vijayakumar, to all graphs on at most six vertices. We also use this corollary to relate γ-graphs both to induced subgraphs of Johnson graphs and to optimal dominating codes in graphs.

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

Resolving Zero-Divisors of Radical Triangular Sets Using Hensel Lifting and Applications

Date created: 
2017-08-16
Abstract: 

This thesis aims to create efficient algorithms for computing in the ring R = Q[z1,...,zn]/T where T is a zero-dimensional triangular set. The presence of zero-divisors in R makes it a computational challenge to use modular algorithms. In particular, there has never been a proper modular algorithm for computing greatest common divisors of polynomials in R[x]. We present two new ways of resolving zero-divisors: Hensel lifting and fault tolerant rational reconstruction, which allows us to create a new modular gcd algorithm for R[x] as well as a new inversion algorithm for R. We have implemented our algorithms in Maple using the RECDEN library, and we show that they outperform the methods currently implemented in Maple's RegularChains package. The method of Hensel lifting for resolving zero-divisors should give rise to other new modular algorithms for computing modulo triangular sets and our applications show that this approach is fruitful.

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

Stability in stochastic language change models

Date created: 
2017-07-24
Abstract: 

Exemplar models are a popular class of models used to describe language change. Exemplars are detailed memories of stimuli people are exposed to, and when modelling language change are represented as vectors where each component is a phonetic variable. Each exemplar is given a category label, representing what that sound is identified as. New sounds are categorized based on how close they are to the exemplars in each category. Newly categorized exemplars become a part of the system and affect how the future sounds are produced and perceived. It is possible in certain situations in language for a category of sound to become extinct, such as a pronunciation of a word. One of the successes of exemplar models has been to model extinction of sound categories. The focus of this dissertation will be to determine whether categories become extinct in certain exemplar models and why. The first model we look at is an exemplar model which is an altered version of a k-means clustering algorithm by MacQueen. It models how the category regions in phonetic space vary over time among a population of language users. For this particular model, we show that the categories of sound will not become extinct: all categories will be maintained in the system for all time. Furthermore, we show that the boundaries between category regions fluctuate and we quantitatively study the fluctuations in a simple instance of the model. The second model we study is a simple exemplar model which can be used to model direct competition between categories of sound. Our aim in investigating this model is to determine how limiting the memory capacity of an individual in exemplar models affects whether categories become extinct. We will prove for this model that all the sound categories but one will always become extinct, whether memory storage is limited or not. Lastly, we create a new model that implements a bias which helps align all the categories in the phonetic space, using the framework of an earlier exemplar model. We make an argument that this exemplar model does not have category extinction.

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

Linking systems of difference sets

Date created: 
2017-08-11
Abstract: 

A linking system of difference sets is a collection of mutually related group difference sets, whose advantageous properties have been used to extend classical constructions of systems of linked symmetric designs. The central problems are to determine which groups contain a linking system of difference sets, and how large such a system can be. All previous results are constructive, and are restricted to 2-groups. We use an elementary projection argument to show that neither the McFarland nor the Spence construction of difference sets can give rise to a linking system of difference sets in non-2-groups. We then give a new construction for linking systems of difference sets in 2-groups, taking advantage of a previously unrecognized connection with group difference matrices. This construction simplifies and extends prior results, producing larger systems than before in certain 2-groups and new linking systems in other 2-groups for which no system was previously known.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Jonathan Jedwab
Marni Mishna
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.