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

## Solvability of ternary equations of signature (3,3,2)

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

In this thesis we examine the primitive solvability of Diophantine equations of the form ax^3 + by^3 = cz^2. For square-free a, b, c, we identify various criteria necessary for the existence of primitive solutions, including a sufficient one. We also present a relatively efficient algorithm to determine whether this criterion is satisfied. Using the algorithm, we compute some data on the relative distribution of the occurrence of various obstructions to the existence of primitive solutions.

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

## An efficient parallel immersed boundary algorithm, with application to the suspension of flexible fibers

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

We design an efficient algorithm for studying problems in fluid-structure interaction on distributed-memory computer clusters using the standard and generalized immersed boundary (IB) equations. The algorithm utilizes a pseudo-compressibility method recently proposed by Guermond and Minev that uses a directional splitting strategy to discretize the incompressible Navier-Stokes equations, thereby reducing the linear systems to a series of one-dimensional tridiagonal systems. This endows our algorithm with the computational complexity of a completely explicit method and excellent parallel scaling properties. We demonstrate the effectiveness of our IB algorithm through detailed numerical and performance studies. For several model problems, we report the accuracy and convergence rates of our algorithm in two and three dimensions. These results are then compared with alternate projection-based IB algorithms. The execution time and scaling properties of our algorithm are then investigated and we discuss the performance benefits over alternative approaches. We conclude with an investigation of the dynamics of flexible fibers in a shear flow using the generalized IB method. In our simulations, we reproduce the orbit classes observed experimentally by S. G. Mason and co-workers. Lastly, using parallel tiling techniques, we simulate dilute suspensions that contain as many as 256 fibers.

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

## Modelling and numerical methods for state-dependent diffusions

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

When modelling diffusive systems with stochastic differential equations, a question about interpretations of the stochastic integral often arises. Using simulations of a random Lorentz gas model, we show that given only the diffusion coefficient, for a diffusive system without external force, the system is underdetermined. By varying one free parameter, the prediction from different interpretations can hold true. However, for a diffusive system satisfying detailed balance condition, we show that it is uniquely determined by the equilibrium distribution in addition to the diffusion coefficient. We propose an explicit method for simulating stochastic differential equations in this formulation. Our numerical scheme introduces Metropolis-Hastings step-rejections to preserve the exact equilibrium distribution and works directly with the diffusion coefficient rather than the drift coefficient. We show that the numerical scheme is weakly convergent with order 1/2 for such systems with smooth coefficients. We perform numerical experiments demonstrating the convergence of the method for systems not covered by our theorem, including systems with discontinuous coefficients.

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

## A generating tree approach to k-nonnesting arc diagrams

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

This thesis describes a strategy for exhaustively generating series information and enumerating combinatorial classes that can be represented using arc diagrams. We focus on k-nonnesting set partitions, permutations, matchings and tangled diagrams. Results are new functional equations, counting sequences, bijections and asymptotic results for these classes. Our key innovation is a generalized arc diagram in which arcs may have left endpoints, but not right endpoints, and our main tool is generating trees.

Document type:
Thesis
File(s):
Senior supervisor:
Marni Mishna
Lily Yen
Department:
Science: Department of Mathematics
Thesis type:
(Dissertation) Ph.D.

## Variants of the Kernel Method for Lattice Path Models

Author:
Date created:
2014-05-05
Abstract:

The kernel method has proved to be an extremely versatile tool for exact and asymptotic enumeration. Recent applications in the study of lattice walks have linked combinatorial properties of a model to algebraic conditions on its generating function, demonstrating how to extract additional information from the process. This thesis details two new results. In the first, we apply the iterated kernel method to determine asymptotic information about a family of models in the quarter plane, finding their generating functions explicitly and classifying them as non D-finite. The second considers d-dimensional walks restricted to an octant whose step sets are symmetric over every axis. A generalized version of the orbit sum method allows for a representation of their generating functions as diagonals of multivariate rational functions, proving they are D-finite. In combination with current developments from analytic combinatorics in several variables, this yields dominant asymptotics for all such models.

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

## Cluster Restricted Maximum Weight Clique Problem and Linkages with Satellite Image Acquisition Scheduling

Author:
Date created:
2014-04-15
Abstract:

We consider the cluster-restricted maximum weight clique problem (CRCP), a variation of the well-known maximum weight clique problem. While CRCP itself is mathematically interesting, our motivation to study the problem primarily comes from its application in the area of Satellite Image Acquisition Scheduling. Earth observing satellites revolve around the earth in specific orbits and takes images of prescribed areas requested by the clients. Not every region can be fully acquired in a single satellite pass. This necessitates the division of the region into multiple strips. There might be several image acquisition opportunities for each strip as the satellites have agility in their rolling angles. Then the Satellite Image Acquisition Scheduling Problem (SIASP) is to select the opportunities to acquire as many images as possible, without repetition, within a planning horizon while considering the image priorities and energy constraints. SIASP has a piecewise linear objective function to favor the completion of an image acquisition request and try to avoid partial acquisition of many requests. Extensive experimental study is provided on randomly generated instances based on the predicted statistics given by MDA, Richmond, Canada. These experiments are intended as a preliminary investigation on image acquisition scheduling for the Canadian RADARSAT Constellation Mission (RCM), a constellation of three satellites, which is planned to be launched in 2018.SIASP can be modeled as a CRCP with piecewise linear objective function. We provide integer programming (IP) formulations for CRCP with linear and piecewise linear objective function. We also suggest heuristic (metaheuristic) algorithms that exploit the power of modern IP solvers such as CPLEX. Experimental results using the heuristic algorithms on DIMACS and BOSHLIB benchmark instances for the clique problem are reported. Finally, an exact algorithm for CRCP along with some theoretical analysis is presented.

Document type:
Thesis
File(s):
Senior supervisor:
Abraham P. Punnen
Snezana Mitrovic-Minic
Department:
Science: Department of Mathematics
Thesis type:
(Thesis) M.Sc.

## Path Selection Problem in Network Design

Author:
Date created:
2014-04-10
Abstract:

In this thesis we study several models for the Path Selection Problem associated with the construction of fibre optic networks. Four different variations of the problem are studied: Greedy Path Selection Problem (GPSP), Benevolent Path Selection Problem (BPSP), Discounted Path Selection Problem (DPSP) and Path Selection with capacity expansion (EPSP). All the variations are NP-hard and polynomially solvable special cases are identified for GPSP and BPSP. We also present detailed complexity analysis and integer programming formulations for these problems. Heuristic algorithms including greedy algorithm, semi-greedy algorithm and multi-start local search algorithm are developed for each problem. Extensive computational results are provided with the algorithm performance analysis. We also present some future directions for research.

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

## The spectral domain embedding method for partial differential equations on irregular domains

Author:
Date created:
2013-06-27
Abstract:

When the solution of a partial differential equation (PDE) is analytic in a regular computational domain, spectral methods are known to yield spectral convergence. However, standard spectral methods have great difficulties in handling a complex irregular computational domain $\Omega$ with boundary $\partial\Omega$.In the spectral domain embedding method, the irregular physical domain $\Omega$ is embedded into a rectangular computational domain $R$. This allows the application of spectral methods in the extended domain $R$ provided that the coefficient and the source terms can be extended smoothly from $\Omega$ to $R$.The rectangular domain $R$ is discretized with Chebyshev or Legendre collocation methods. Robin (mixed) boundary conditions on $\partial\Omega$ are enforced by a chosen set of control nodes distributed along $\partial\Omega$ in some fashion. The solution of the PDE at these control nodes satisfies the given boundary conditions forming a set of complementary constraint equations. Together with the solving operator, they form a global system of linear equations.

Document type:
Graduating extended essay / Research project
File(s):
Senior supervisor:
Steve Ruuth
Department:
Science: Department of Mathematics
Thesis type:
(Research Project) M.Sc.

## Constructions of Complex Equiangular Lines

Author:
Date created:
2013-12-03
Abstract:

A set of unit vectors in $\C^d$ represents equiangular lines if the magnitudes of the inner product of every pair of distinct vectors in the set are equal. The maximum size of such a set is $d^2$, and it is conjectured that sets of this maximum size exist in $\C^d$ for every $d\geq 2$. In this thesis we describe evidence supporting the conjecture. We explain the fiducial vector method of construction, outlining the methods of approach and combining the viewpoints of several authors responsible for known examples of maximum-sized sets of equiangular lines. We also identify several milestone publications and note specific examples of maximum-sized sets of equiangular lines which we believe to be key in eventually resolving the conjecture.Furthermore we give two new maximum-sized sets of equiangular lines in dimension 8; one set is simpler than all previously known examples and the other illuminates previously unrecognized underlying structure through connections with other dimensions. Using these sets of lines we are able to demonstrate some important connections between equiangular lines and other combinatorial objects, including Hadamard matrices, mutually unbiased bases and relative difference sets.

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

## Rossby Wave Propagation in the Tropics and Midlatitudes

Author:
Date created:
2013-01-18
Abstract:

Rossby waves are the slow atmospheric waves that propagate thousands of kilometres on the time scale of days and are associated with weather. The small amplitude linear theory of Rossby waves on the sphere goes back over two centuries to Laplace’s tidal equations and is today considered thoroughly understood. However, with a more realistic background flow that includes both the tropical trade winds and the midlatitude jetstream, the global wave theory has not been fully established. To study this problem, this thesis uses the rotating shallow water (RSW) equations on the sphere as a model for Earth’s atmosphere. The spectrum of the RSW equations is numerically computed using a Galerkin method. It is found that the Rossby spectrum of this global model consists of two parts that naturally correspond respectively to local tropical and midlatitude theories. The first part of the spectrum is the countably infinite set of discrete eigenmodes with arbitrarily small wavelength near the equator, consistent with the local tropical β-plane theory. These discrete modes however achieve only a finite limiting wavelength in the midlatitudes. To account for smaller scales in the midlatitudes, it is necessary to consider the continuous spectrum that results from regular singular points in the RSW operator arising from shear in the background flow. The regular singular points correspond to critical latitudes, which prevent wave propagation from the midlatitudes into the tropics. The numerical results are complemented by small wavelength asymptotics of ray theory and Wentzel–Kramers–Brillouin (WKB) analysis to gain an understanding of the local wave- length, amplitude and group velocity for Rossby waves. The global understanding of Rossby waves presented in this thesis is used to provide some explanation of the small number of Rossby modes found in long-term climatological observations of theatmosphere.

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