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

Receive updates for this collection

Three Problems Involving Permutations

Date created: 
2016-12-05
Abstract: 

We study three problems involving permutations: the n-card problem, inv-Wilf-equivalence, and suitable sets of permutations. The n-card problem is to determine the minimal intervals [u, v] such that for every n times n stochastic matrix A there is an n times n permutation matrix P (depending on A) such that tr(PA) belongs to [u, v]. The minimal intervals for the n-card problem are known only for n <= 4. We answer a question posed by Sands, by showing that [1, 2] is a solution to the n-card problem for all n >= 2. We also show that each closed interval of length n/(n−1) contained in [0, 2) is a solution to the n-card problem for all n >= 2. Wilf-equivalence is one of the central concepts of pattern-avoiding permutations. The two known infinite families of Wilf-equivalent permutation pairs both satisfy the stronger condition of shape-Wilf-equivalence. Dokos et al. studied a different strengthening of Wilf-equivalence called inv-Wilf-equivalence. They conjectured that all inv-Wilf-equivalent permutation pairs arise from trivial symmetries. We disprove this conjecture with an infinite family of counterexamples, obtained by generalizing simultaneously the concepts of shape-Wilf-equivalence and inv-Wilf-equivalence. We also prove the Baxter-Jaggard conjecture on even-shape-Wilf-equivalent permutation pairs. A set of N permutations of {1, 2, . . . , v} is (N, v, t)-suitable if each symbol precedes each subset of t − 1 others in at least one permutation. We give examples of suitable sets of permutations for new parameter triples (N, v, t). We relate certain suitable sets of permutations with parameter t to others with parameter t + 1, thereby showing that one of the two infinite families presented by Colbourn can be constructed directly from the other. We prove an exact nonexistence result for suitable sets of permutations using elementary combinatorial arguments. We then establish an asymptotic nonexistence result using Ramsey’s theorem.

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

Linearly stabilized schemes for the time integration of stiff nonlinear PDEs

Date created: 
2016-12-09
Abstract: 

In many applications, the governing PDE to be solved numerically will contain a stiff component. When this component is linear, an implicit time stepping method that is unencumbered by stability restrictions is preferred. On the other hand, if the stiff component is nonlinear, the complexity and cost per step of using an implicit method is heightened, and explicit methods may be preferred for their simplicity and ease of implementation. In this thesis, we analyze new and existing linearly stabilized schemes for the purpose of integrating stiff nonlinear PDEs in time. These schemes compute the nonlinear term explicitly and, at the cost of solving a linear system with a matrix that is fixed throughout, are unconditionally stable, thus combining the advantages of explicit and implicit methods. Applications are presented to illustrate the use of these methods.

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

The closest point method for the numerical solution of partial differential equations on moving surfaces

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

Partial differential equations (PDEs) on surfaces arise in a wide range of applications. The closest point method is a recent embedding method that has been used to solve a variety of PDEs on smooth surfaces using a closest point representation of the surface and standard Cartesian grid methods in the embedding space. The original closest point method (CPM) was designed for problems posed on static surfaces, however the solution of PDEs on moving surfaces is of considerable interest as well. Here we propose two different approaches for solving PDEs on moving surfaces using a combination of the CPM and a grid based particle method. The grid based particle method (GBPM) represents and tracks surfaces using meshless particles and an Eulerian reference grid. In our first approach, a modification of the GBPM is introduced to ensure that all the grid points within a computational tube surrounding the surface are active. The modified GBPM is tested in geometric motions of surfaces to verify the correctness of the new algorithm. A coupled method is proposed combining the modified GBPM and the CPM and tested on a number of numerical examples. Our second approach uses generalized finite difference schemes derived from radial basis functions (RBF-FD) in the implementation of the closest point method. An explicit and an implicit formulation of the CPM using RBF-FD are presented along with numerical experiments for the convergence of the method, including the approximation of the solution of reaction-diffusion equations and the Cahn-Hilliard equation on a variety of surfaces. Finally, a coupled method of the CPM that uses RBF-FD and the original GBPM is proposed and used to solve PDEs on moving surfaces.

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

Interfacial numerics for the mathematical modeling of cloud edge dynamics

Date created: 
2016-12-08
Abstract: 

In this thesis we present a two-dimensional thermodynamic model for cloud edge dynamics. We use the incompressible Euler equations to describe the atmospheric fluid dynamics and link these to the theory of moist thermodynamics through a constitutive law. This leads to a free boundary model for the interface separating clear and cloudy air. The model is further specialized to linearized disturbance equations about conditions that are critically saturated with zero liquid cloud water. Due to the presence of discontinuous derivatives induced by the clear/cloudy interface we adapt the immersed interface method (IIM) for computing the pressure in the system to second order accuracy. In addition, we investigate the unforeseen second order convergence of a "naive" method without the IIM. We conduct an analysis of local and global errors for the naive method leveraging off our analysis of the IIM and present numerical verification of the results when necessary.

Document type: 
Thesis
File(s): 
Senior supervisor: 
David Muraki
John Stockie
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Arithmetic aspects of the Burkhardt quartic threefold

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

The Burkhardt quartic is a 3-dimensional projective hypersurface defined over the rational numbers. It is known that sufficiently general points on the Burkhardt quartic parameterize abelian surfaces with a full level 3 structure. Furthermore, it is classical that the Burkhardt quartic is birational to 3-dimensional projective space after adjoining a cube root of unity. In this thesis we will show that the Burkhardt quartic is birational to 3-dimensional projective space over the rational numbers, and describe a geometric method of constructing a generic family of hyperelliptic curves corresponding to points on the Burkhardt quartic, whose Jacobians have a full level 3 structure. Specifically, we give an explicit family of hyperelliptic curves which contain almost all complex genus 2 curves with a full level 3 structure.

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

Robust Chaos in Two-Dimensional Discontinuous Maps with One and Two Switching Manifolds

Author: 
Date created: 
2016-07-04
Abstract: 

This dissertation concerns a new approach to determining the structure of robust chaos in two-dimensional (2D) piecewise smooth discontinuous maps and an extension to the case of two switching manifolds. The study of chaotic dynamics has found many applications in various disciplines in science and engineering. Extensive research has been carried out to identify and analyze the dynamical behaviour of chaos. This dissertation centres on those chaotic attractors which are robust to small parameter changes and do not contain periodic windows or coexisting attractors. This behaviour is termed robust chaos. In recent years, the problem of understanding and predicting robust chaos in the real world has attracted many researchers. In this dissertation, we focus on hyperbolic dissipative piecewise smooth discontinuous maps in the plane. First, we consider a 2D piecewise linear discontinuous normal form map with one switching manifold, restricting to real eigenvalues, and determine regions of parameter space where a bifurcation leading to robust chaos might occur. We study the intricate structure of the chaotic attractors and present detailed analytical heuristics for determining parameter values for boundary crises leading the onset or termination of robust chaos. We also show the existence of unusual basins of attraction for some chaotic attractors and provide a strategy to determine the basin boundaries.Next, we propose an extension to a new map with an added second switching manifold and three linear branches. This map has application to a simple financial market model. We discuss our normal form map, under the assumption that the outer branches are the same, and present a systematic analysis of bifurcations leading to robust chaos. We develop analytical procedures to identify the underlying generating mechanism of robust chaos in the vicinity of each of the switching manifolds and determine associated parameter space regimes. We also illustrate conditions under which robust chaos occurs near both the switching manifolds simultaneously.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Ralf W. Wittenberg
Alexander R. Rutherford
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

On Chudnovsky-Ramanujan Type Formulae

Author: 
Date created: 
2016-06-14
Abstract: 

In his well-known 1914 paper, Ramanujan gave a number of rapidly converging series for $1/\pi$ which involve modular functions of higher level. D. V. and G. V. Chudnovsky have derived an analogous series representing $1/\pi$ using the modular function $J$ of level 1, which results in highly convergent series for $1/\pi$, often used in practice. In 2013, $12.1 \times 10^{12}$ digits of $\pi$ were calculated by A. J. Yee and S. Kondo using the Chudnovsky series for $\pi$. The purpose of this work is to explain the method of D. V. and G. V. Chudnovsky and show how it can be generalised to derive formulae for transcendental constants starting from a one-parameter family of elliptic curves. We find all such closed-form Chudnovsky-Ramanujan type formulae for the family of elliptic curves parameterised by $J$ of level 1, where $J$ is the absolute $j$-invariant.

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

Algorithmic aspects of some vertex ordering problems

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

Combinatorial Optimization problems play central role in applied mathematics and computer science. A particular class of combinatorial optimization problems is vertex ordering problems whose goal is to find an ordering on vertices of an input graph in such way that a certain objective cost is optimized. This thesis focuses on three different vertex ordering problems. First, we consider a variant of Directed Feedback Arc Set problem with applications in computational biology. We present an efficient heuristic algorithm for this problem. Next, we concentrate on parameterized complexity of Minimum Linear Arrangement problem while the parameter is size of vertex cover. We formulate the problem as Quadratic Integer Programming and propose two new techniques to tackle the problem. Finally, we introduce a vertex ordering problem on bipartite graphs with applications in different areas. We give a general algorithmic strategy for the problem, as well as, polynomial-time algorithms for three classes of graphs.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Ladislav Stacho
Cedric Chauve
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Vectorial Bent Functions in Characteristic Two

Date created: 
2016-02-02
Abstract: 

We study Dillon-type vectorial bent functions of the monomial and multinomial varieties. We also study Kloosterman sums, which relate to the construction of Dillon-type monomial bent functions. For Dillon-type monomial functions we give sufficient conditions for vectorial bentness, leading to the construction of several new examples. We give useful necessary conditions for functions from GF(2^(4m)) to GF(4). We give new restrictions on the maximum output dimension of Dillon-type monomial bent functions on GF(2^(4m)). We subsequently show that certain Dillon-type multinomial bent functions do not meet the Nyberg bound. We give computational results regarding Dillon-type functions from GF(2^(4m)) to GF(4), suggesting that while bent monomials of this type appear to be rare, their binomial counterparts seem to be relatively abundant. Finally, we give divisibility results on Kloosterman sums valued on cosets of certain subfields of GF(2^m), leading to explicit constructions of Kloosterman zeros and Dillon-type monomial bent functions.

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

4D Reconstruction of dynamic studies with the discovery NM 530c SPECT Camera

Author: 
Date created: 
2016-02-25
Abstract: 

Single photon emission computed tomography (SPECT) is a nuclear medicine imaging technique. Functional imaging allows doctors to study the physiology and function of living organs. As physiological processes in a human body are dynamic, studying changes of their temporal characteristics and spatial distribution may provide important diagnostic information. This thesis investigates various aspects of dynamic functional SPECT imaging. The algorithms are tailored for a dedicated cardiac camera system, namely the GE Discovery NM530c, a pinhole camera that can acquire views from different angles simultaneously. A fundamental feature of dynamic reconstruction is that the problem is highly underdetermined. Hence, any given consistent dataset allows infinitely many solutions. The existing dSPECT method “regularizes” the solutions by introducing constraints based on the underlying physics; it reconstructs the dynamic activity by solving one large system, as opposed to the frame-by-frame static reconstruction approach. Therefore, dSPECT reconstruction maintains temporal correlations. In this thesis, the dSPECT method was used to reconstruct images that had been scanned with the Discovery NM530c. The time activity curves of reconstructed images obtained from dSPECT are smoother than those obtained from static reconstructions. A new method, dSPECTpv, was developed to allow for successful reconstruction of dynamic behaviour that had not been observed previously in dynamic SPECT studies. Although the time activity curves of reconstructed images are much smoother, little or no improvement is observed when those reconstructions are used to estimate kinetic parameters. In this thesis, the Discovery NM530c acquisition process was modeled with the Monte Carlo method, using the simulation software GATE. Hence, computer simulations can be used to investigate the camera geometry. Our software is a useful tool in optimizing camera setup and the acquisition protocol.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Manfred Trummer
Anna Celler
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.