CS Theses & Dissertations 2019

For 2019 graduation dates (in alphabetical order by last name):

Learning locomotion: symmetry and torque limit considerations
Abdolhosseini, Farzad
DOI : 10.14288/1.0383251
URI : http://hdl.handle.net/2429/71825
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. van de Panne

Machine learning of lineaments from magnetic, gravity and elevation maps
Aghaee Rad, Mohammad Amin
DOI : 10.14288/1.0376558
URI : http://hdl.handle.net/2429/68438
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Poole

Practical optimization for structured machine learning problems
Ahmed, Mohamed Osama
DOI : 10.14288/1.0376046
URI : http://hdl.handle.net/2429/68240
Degree : Doctor of Philosophy - PhD
Graduation Date : 2019-05
Supervisor : Dr. Schmidt

Recent years have witnessed huge advances in machine learning (ML) and its applications, especially in image, speech, and language applications. Optimization in ML is a key ingredient in both the training and hyperparameter tuning steps, and it also influences the test phase. In this thesis, we make improvements to optimization of all of these three problems. The first part of the thesis considers the training problem. We present the first linearly-convergent stochastic gradient method to train conditional random fields (CRFs) using the stochastic average gradient (SAG) method. Our method addresses the memory issues required for SAG and proposes a better non-uniform sampling (NUS) technique. The second part of the thesis deals with memory-free linearly-convergent stochastic gradient method for training ML models. We consider the stochastic variance reduced gradient (SVRG) algorithm, which normally requires occasional full-gradient evaluations. We show that we can decrease the number of gradient evaluations using growing batches (which improves performance in the early iterations) and support vectors (which improves performance in the later iterations). The third part of this thesis switches to the problem of hyper-parameter tuning. Although it is a lower dimensional problem, it can be more difficult as it is a non-convex global optimization problem. First, we propose a harmless global optimization algorithm to ensure that the performance is not worse than using random search. Moreover, we explore the use of gradient-based Bayesian optimization (BO) to improve the performance. We propose the use of directional derivatives to address the memory issues of BO. Finally, in the fourth part of this thesis, we propose a novel optimization method that combines the advantages of BO and Lipschitz optimization (LO).

Finding all DC operating points using interval-arithmetic-based verification algorithms
Akhter, Itrat Ahmed
DOI : 10.14288/1.0374943
URI : http://hdl.handle.net/2429/67954
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisors : Dr. Greenstreet, Dr. Hu

Incidence networks for Geometric Deep Learning
Albooyeh, Marjan
DOI : 10.14288/1.0384585
URI : http://hdl.handle.net/2429/72006
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Sigal

Graph-based language grounding
Bajaj, Mohit
DOI : 10.14288/1.0380482
URI : http://hdl.handle.net/2429/71323
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Sigal

On the core of the multicommodity flow game without side payments
Beeson, Coulter Donald
DOI : 10.14288/1.0380540
URI : http://hdl.handle.net/2429/71389
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Shepherd

Scalable deep reinforcement learning for physics-based motion control
Berseth, Glen Paul
DOI : 10.14288/1.0378079
URI : http://hdl.handle.net/2429/69572
Degree : Doctor of Philosophy - PhD
Graduation Date : 2019-05
Supervisor : Dr. van de Panne

This thesis studies the broad problem of learning robust control policies for difficult physics-based motion control tasks such as locomotion and navigation. A number of avenues are explored to assist in learning such control. In particular, are there underlying structures in the motor-learning system that enable learning solutions to complex tasks? How are animals able to learn new skills so efficiently? Animals may be learning and using implicit models of their environment to assist in planning and exploration. These potential structures motivate the design of learning systems and in this thesis, we study their effectiveness on physically simulated and robotic motor-control tasks. Five contributions that build on motion control using deep reinforcement learning are presented. First, a case study on the motion control problem of brachiation, the movement of gibbons through trees is presented. This work compares parametric and non-parametric models for reinforcement learning. The difficulty of this motion control problem motivates separating the control problem into multiple levels. Second, a hierarchical decomposition is presented that enables efficient learning by operating across multiple time scales for a complex locomotion and navigation task. First, reinforcement learning is used to acquire a low-level, high-frequency policy for joint actuation, used for bipedal footstep-directed walking. Subsequently, an additional policy is learned that provides directed footstep plans to the first level of control in order to navigate through the environment. Third, improved action exploration methods are investigated. An explicit action valued function is constructed using the learned model. Using this action-valued function we can compute actions that increase the value of future states. Fourth, a new algorithm is designed to progressively learn and integrate new skills producing a robust and multi-skilled physics-based controller. This algorithm combines the skills of experts and then applies transfer learning methods to initialize and accelerate the learning of new skills. In the last chapter, the importance of good benchmarks for improving reinforcement learning research is discussed. The computer vision community has benefited from large carefully processed collections of data, and, similarly, reinforcement learning needs well constructed and interesting environments to drive progress.

Compiling distributed system specifications into implementations
Costa, Renato Mascarenhas
DOI : 10.14288/1.0378287
URI : http://hdl.handle.net/2429/69745
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Beschastnikh

Visualizing heterogeneous data in genomic epidemiology
Crisan, Anamaria
DOI : 10.14288/1.0380812
URI : http://hdl.handle.net/2429/71631
Degree : Doctor of Philosophy - PhD
Graduation Date : 2019-11
Supervisors : Dr. Munzner, Dr. Gardy (SPPH)

Technological innovations have allowed for a greater variety of data, most notably microbial genomic data, to be collected, integrated, analyzed, and visualized for epidemiological investigations. While analytic methods have evolved in light of this technological change, data visualizations systems have lagged behind. I take a novel approach that integrates methods from information visualization, human computer interaction, machine learning, and statistics to address unmet data visualization needs in microbial genomic epidemiology (genEpi). This approach also enables me to generate study artifacts that can be used to address regulatory and organizational constraints arising in domains where the use of data is highly restricted. I first present a mixed methods approach to understand the needs, data, tasks, and constraints of public health stakeholders that are charged with interpreting the findings of these data. I demonstrate how this approach can be used to communicate new and heterogeneous types of data in a clinical report that is read by stakeholders in different roles. I next present a novel method for systematically reviewing data visualizations that I use to develop a Genomic Epidemiology Visualization Typology (GEViT), which enables others to explore and characterize the way the data could be visualized. Finally, I use these collective findings to inform the design and implementation of data visualization tools: Adjutant, the GEViT Gallery, minCombinR, and GEViTRec. Adjutant enables rapid and unsupervised topic clustering of PubMed article corpuses to aid systematic and literature reviews. The GEViT gallery is a browsable interface for exploring data visualizations specific to the microbial genEpi domain. minCombinR lowers the burden to stakeholders for generating combinations of data visualizations for heterogeneous data. Finally, GEViTRec takes a novel approach to the automatic generation of data visualizations that can help stakeholders familiarize themselves with new data. All of these tools integrate with analytic methods. This research makes novel contributions to the design and implementation of data visualization systems that impact microbial genomic epidemiological data collected for public health investigations. The challenges addressed here are not unique to this domain and my contributions are extensible to other domains grappling with heterogeneous, multidimensional, and restricted data.

Corresponding formal specifications with distributed systems
Do, Minh Nhat
DOI : 10.14288/1.0378335
URI : http://hdl.handle.net/2429/69795
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Beschastnikh

Affective interpretations of assisted driving interventions on a smart-wheelchair: an exploratory study
Estrada Gaspar, Ariadna Maria
DOI : 10.14288/1.0375817
URI : http://hdl.handle.net/2429/68126
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Mitchell

Bundle-type methods for dual atomic pursuit
Fan, Zhenan
DOI : 10.14288/1.0380495
URI : http://hdl.handle.net/2429/71339
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Friedlander

OCTVis: ontology-based comparison of topic models
Ge, Amon Dongfang
DOI : 10.14288/1.0378428
URI : http://hdl.handle.net/2429/69898
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisors : Dr. Carenini, Dr. Murray (University of Fraser Valley)

Beyond submodular maximization: one-sided smoothness and meta-submodularity
Ghadiri, Mehrdad
DOI : 10.14288/1.0380597
URI : http://hdl.handle.net/2429/71447
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisors : Dr. Shepherd, Dr. Schmidt

CodeShovel: constructing robust source code history
Grund, Felix
DOI : 10.14288/1.0379647
URI : http://hdl.handle.net/2429/70831
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Holmes

[no title]
He, Siyuan
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Yoon

Perception-driven semi-structured boundary vectorization
Hoshyari, Shayan
DOI : 10.14288/1.0376350
URI : http://hdl.handle.net/2429/68337
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Sheffer

Priority-based parameter propagation for distributed deep neural network training
Jayarajan, Anand
DOI : 10.14288/1.0380523
URI : http://hdl.handle.net/2429/71375
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisors : Dr. Fedorova (EECE), Dr. Beschastnikh

NJM-Vis: applying and interpreting neural network joint models in natural language processing applications
Johnson, David
DOI : 10.14288/1.0383321
URI : http://hdl.handle.net/2429/71864
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisors : Dr. Carenini, Dr. Murray (adjunct professor)

Representing and learning relations and properties under uncertainty
Kazemi, Seyed Mehran
DOI : 10.14288/1.0375812
URI : http://hdl.handle.net/2429/68134
Degree : Doctor of Philosophy - PhD
Graduation Date : 2019-05
Supervisor : Dr. Poole

The world around us is composed of entities, each having various properties and participating in relationships with other entities. Consequently, data is often inherently relational. This dissertation studies probabilistic relational representations, reasoning and learning with a focus on three common prediction problems for relational data: link prediction, property prediction, and joint prediction. For link prediction, we develop a tensor factorization model called SimplE which is simple, interpretable, fully-expressive, and integratable with certain types of domain expert knowledge. On two standard benchmarks for knowledge graph completion, we show how SimplE outperforms the state-of-the-art models. For property prediction, first we study the limitations of the existing StaRAI models when being used for property prediction. Based on this study, we develop relational neural networks which combine ideas from lifted relational models with deep learning and perform well empirically. We base the joint prediction on lifted relational models for which parameter learning typically requires inference over a highly-connected graphical model. The inference step is usually the bottleneck for learning. We study a class of inference algorithms known as lifted inference which makes inference tractable by exploiting both conditional independence and symmetries. We study two ways of speeding up lifted inference algorithms: 1- through proposing heuristics for elimination ordering and 2- through compiling the lifted operations to low-level languages. We also expand the largest known class of models for which we know how to do efficient lifted inference. Thus, structure learning algorithms for lifted relational models that restrict the search space to models for which efficient inference algorithms exist can perform their search over a larger space

Enforcing structure in visual attention
Khandelwal, Siddhesh Shyam
DOI : 10.14288/1.0384602
URI : http://hdl.handle.net/2429/71953
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Sigal

Hierarchical summaries of change in multidimensional data
Kim, Alexandra
DOI : 10.14288/1.0376120
URI : http://hdl.handle.net/2429/68278
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Lakshmanan

Exploring neural models for predicting dementia from language
Kong, Weirui
DOI : 10.14288/1.0380363
URI : http://hdl.handle.net/2429/71274
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisors : Dr. Carenini & Dr. Field (Faculty of Medicine)

Automated reasoning in first-order real vector spaces
Kwan, Carl
DOI : 10.14288/1.0380600
URI : http://hdl.handle.net/2429/71452
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisors : Dr. Greenstreet, Dr. Evans

[no title]
Li, Liran
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Friedlander

[no title]
Liu, Qiuyan
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Pottinger

Augmenting source code editors with external information
Liu, Xinhong
DOI : 10.14288/1.0381006
URI : http://hdl.handle.net/2429/71778
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Holmes

[no title]
Lundy, Taylor Paul
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisors : Dr. Fu, Dr. Leyton-Brown

Algorithms for large-scale multi-codebook quantization
Martinez-Covarrubias, Julieta
DOI : 10.14288/1.0375712
URI : http://hdl.handle.net/2429/68041
Degree : Doctor of Philosophy - PhD
Graduation Date : 2019-05
Supervisors : Dr. Little, Dr. Hoos

Combinatorial vector compression is the task of expressing a set of vectors as accurately as possible in terms of discrete entries in multiple bases. The problem is of interest in the context of large-scale similarity search, as it provides a memory-efficient, yet ready-to-use compact representation of high-dimensional data on which vector similarities such as Euclidean distances and dot products can be efficiently approximated. Combinatorial compression poses a series of challenging optimization problems that are often a barrier to its deployment on very large scale systems (e.g., of over a billion entries). In this thesis we explore algorithms and optimization techniques that make combinatorial compression more accurate and efficient in practice, and thus provide a practical alternative to current methods for large-scale similarity search.

Cross-device access control with Trusted Capsules
Mehrotra, Puneet
DOI : 10.14288/1.0384608
URI : http://hdl.handle.net/2429/71952
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Beschastnikh

Operator, number please: mediating access to shared resources for efficiency and isolation
Nanavati, Mihir
DOI : 10.14288/1.0376084
URI : http://hdl.handle.net/2429/68264
Degree : Doctor of Philosophy - PhD
Graduation Date : 2019-05
Supervisors : Dr. Warfield, Dr. Aiello

The performance density of modern hardware has forced the sharing of hardware resources across applications for better utilization and efficiency. Shared infrastructure, however, weakens isolation and risks interference, which can result in degraded performance and security breaches. This thesis explores the tension between isolation and sharing with three prototype systems: Xoar, Plastic, and Decibel. All three of these systems demonstrate the value of software mediation in providing isolation on shared hardware without sacrificing either hardware resource utilization or the performance of the underlying devices. Xoar, Plastic, and Decibel provide isolation for different hardware resources: Xoar strengthens isolation between virtual machines, thereby allowing underutilized processors to be shared; Plastic transparently mitigates poor cache utilization and the performance artifacts caused by insufficient cache line isolation across cores; and Decibel provides isolation in shared non-volatile storage and guarantees throughput, even in the face of competing workloads.

Erlay: efficient transaction relay in Bitcoin
Naumenko, Hlib
DOI : 10.14288/1.0378175
URI : http://hdl.handle.net/2429/69641
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Beschastnikh

XSnare: application-specific, cross-site scripting protection
Pazos, Jose Carlos
DOI : 10.14288/1.0384040
URI : http://hdl.handle.net/2429/72015
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Beschastnikh

Supporting focused work on window-based desktops
Pilzer, Jan Matthias
DOI : 10.14288/1.0384561
URI : http://hdl.handle.net/2429/72049
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisors : Dr. Holmes, Dr. Fritz

Data-driven data center traffic control
Ruffy Varga, Fabian Nikolaus Trutz
DOI : 10.14288/1.0378362
URI : http://hdl.handle.net/2429/69869
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Beschastnikh

3D Biomechanical Simulation and Control of the Human Hand
Sachdeva, Prashant
DOI : 10.14288/1.0381004
URI : http://hdl.handle.net/2429/71777
Degree : Doctor of Philosophy - PhD
Graduation Date : 2019-11
Supervisors : Dr. Pai, Dr. Sueda (external)

The goal of this thesis is to develop novel computational tools and software for detailed modelling of dynamics of biomechanical systems such as the human hand, with potential applications in prosthetics, surgery, robotics, and virtual reality. We study the effect of the finger extensor mechanism, and musculotendon control on the kinematic and dynamic function of the hand. Hand tendons form a complex network of sheaths, pulleys, and branches. A three dimensional model capturing its detailed anatomy would help simulate the coordination and internal dynamics of the musculoskeletal system. Previous approaches include resource-intensive cadaver studies and mathematical force-transmission models, which cannot compute hand motion under muscle action. We developed a modelling and control framework for hand musculotendon dynamics to overcome these limitations. This approach uses Eulerian-on-Lagrangian discretization of tendons with a selective quasistatic assumption, eliminating unnecessary degrees of freedom and the need for generic collision detection. Unlike previous approaches, our approach efficiently and accurately handles constrained musculotendon dynamics. Using this framework, two control approaches were developed for precise fingertip trajectory tracking. To apply these techniques, software tools were developed with goals of interactive design, experimentation, and control of hand biomechanics. They overcome limitations of other available biomechanics software, enabling modelling of complex tendon arrangements, such as the finger extensor assembly. These tools can simulate all musculoskeletal elements of the hand, and allow closed-loop simulation control. With these software tools, we built a detailed anatomical model of the lumbrical muscle of the finger and simulated its role in reshaping finger flexion. The lumbrical plays an important role in determining the flexion order for the interphalangeal and metacarpophalageal joints. Prior cadaver studies have recorded this role, providing an opportunity for model validation. The in vitro experiments were reproduced successfully, establishing its role in increasing the grasp reach of the hand. We also modelled the in vivo function of the activated lumbrical, overcoming the limitations of cadaver experiments. Finally, a preliminary model of the full hand was constructed with the thumb and the wrist, and simulations of tenodesis grasp and simple thumb motions are presented.

Automatic conceptual window grouping with frequent pattern matching
Scholtz, Anna
DOI : 10.14288/1.0384599
URI : http://hdl.handle.net/2429/71996
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Holmes

The unbalancing act: proxy preservation for censorship resistance systems
Spacek, Jodi
DOI : 10.14288/1.0378365
URI : http://hdl.handle.net/2429/69845
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Beschastnikh

Graph neural network for situation recognition
Suhail, Mohammed
DOI : 10.14288/1.0384601
URI : http://hdl.handle.net/2429/71937
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Sigal

Group event recognition in ice hockey
Tian, Sijia
DOI : 10.14288/1.0375801
URI : http://hdl.handle.net/2429/68116
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisor : Dr. Little

User characteristics and eye tracking to inform the design of user-adaptive information visualizations
Toker, Dereck James
DOI : 10.14288/1.0380857
URI : http://hdl.handle.net/2429/71661
Degree : Doctor of Philosophy - PhD
Graduation Date : 2019-11
Supervisor : Dr. Conati

Amidst an ever-increasing amount of digital information, information visualizations have become a fundamental tool to support tasks for discovering, presenting, and understanding the many underlying trends in this data. Ongoing effort to improve the effectiveness of visualizations however has been typically limited to their design and evaluation following a one size-fits-all model, meaning that they do not take into account the individual differences of their users. There is mounting evidence though, that user differences such as cognitive abilities, personality traits, learning abilities, and preferences can significantly influence user performance and satisfaction during information visualization tasks, thus motivating a need for personalization. In this thesis, our primary goal is to inform the design of user-adaptive visualizations, namely, visualizations that aim to recognize and adapt to each user’s specific needs. We conducted three different user studies to address several key questions for designing user-adaptive visualizations: i) What characteristics of the user should be considered to drive adaptation? ii) How can a visualization system adequately adapt to these user characteristics? and iii) When should adaptations be delivered in order to maximize effectiveness and reduce intrusiveness? In our first study, we tested the effectiveness of highlighting interventions on bar chart visualizations and examined the role that several cognitive abilities may have on visualization processing. Results from this study provide contributions showing that: highlighting relevant information in real-time can be beneficial to bar chart processing; certain user characteristics may only warrant adaptation as task complexity increases; users with low Verbal Working Memory may need interventions that facilitate processing of the visualization’s legend; and adapting to users’ level of Evolving Skill with a visualization is possible using eye tracking to make real-time predictions of this user characteristic. In our second and third study, we investigate visualizations embedded in narrative text, referred to as Magazine Style Narrative Visualization (MSNV). Results from these two studies provide contributions showing that: Verbal Working Memory and English Reading Ability can impact users’ ability to effectively process MSNVs supporting a need for adaptation; and in particular low Reading Ability users might benefit from adaptations helping them locate relevant information in the visualizations.

Structured bandits and applications: exploiting problem structure for better decision-making under uncertainty
Vaswani, Sharan
DOI : 10.14288/1.0375850
URI : http://hdl.handle.net/2429/68166
Degree : Doctor of Philosophy - PhD
Graduation Date : 2019-05
Supervisors : Dr. Schmidt, Dr. Lakshmanan

We study the problem of decision-making under uncertainty in the bandit setting. This thesis goes beyond the well-studied multi-armed bandit model to consider structured bandit settings and their applications. In particular, we learn to make better decisions by leveraging the application-specific problem-structure in the form of features or graph information. We investigate the use of structured bandits in two practical applications: online recommender systems with an available network of users and viral marketing in social networks. For each of these applications, we design efficient bandit algorithms and theoretically characterize their performance. We experimentally evaluate the efficiency and effectiveness of these algorithms on real-world datasets. For applications that require modelling complex non-linear feature-reward relationships, we propose a bootstrapping approach and establish theoretical regret bounds for it. Furthermore, we consider the application of multi-class classification with bandit feedback as a test-bed for evaluating our bootstrapping approach.

Machine learning hyperparameter tuning via Bayesian optimization exploiting monotonicity
Wang, Wenyi
DOI : 10.14288/1.0378254
URI : http://hdl.handle.net/2429/69727
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisors : Dr. Welch (Dept of Statistics), Dr. Wagner

Preconditioners for incompressible magnetohydrodynamics
Wathen, Michael
DOI : 10.14288/1.0375762
URI : http://hdl.handle.net/2429/68092
Degree : Doctor of Philosophy - PhD
Graduation Date : 2019-05
Supervisor : Dr. Greif

The main goal of this thesis is to design efficient numerical solutions to incompressible magnetohydrodynamics (MHD) problems, with focus on the solution of the large and sparse linear systems that arise. The MHD model couples the Navier-Stokes equations that govern fluid dynamics and Maxwell's equations which govern the electromagnetic effects. We consider a mixed finite element discretization of an MHD model problem. Upon discretization and linearization, a large block 4-by-4 nonsymmetric linear system needs to be (repeatedly) solved. One of the principal challenges is the presence of a skew-symmetric term that couples the fluid velocity with the magnetic field. We propose two distinct preconditioning techniques. The first approach relies on utilizing and combining effective solvers for the mixed Maxwell and the Navier-Stokes sub-problems. The second approach is based on algebraic approximations of the inverse of the matrix of the linear system. Both approaches exploit the block structure of the discretized MHD problem. We perform a spectral analysis for ideal versions of the proposed preconditioners, and develop and test practical versions. Large-scale numerical results for linear systems of dimensions up to 10⁷ in two and three dimensions validate the effectiveness of our techniques. We also explore the use of the Conjugate Gradient (CG) method for saddle-point problems with an algebraic structure similar to the time-harmonic Maxwell problem. Specifically, we show that for a nonsingular saddle-point matrix with a maximally rank-deficient leading block, there are two sufficient conditions that allow for CG to be used. An important part of the contributions of this thesis is the development of numerical software that utilizes state-of-the-art software packages. This software is highly modular, robust, and flexible.

Skinprobe 2.0: development of a system for low-cost measurement of human soft tissues
Wick, Alistair Charles
DOI : 10.14288/1.0383333
URI : http://hdl.handle.net/2429/71876
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Pai

Extractive summarization of long documents by combining global and local context
Xiao, Wen
DOI : 10.14288/1.0380504
URI : http://hdl.handle.net/2429/71354
Degree : Master of Science – MSc
Graduation Date : 2019-11
Supervisor : Dr. Carenini

Infrequent discourse relation identification using Data Programming
Zeng, Xing
DOI : 10.14288/1.0375383
URI : http://hdl.handle.net/2429/67968
Degree : Master of Science – MSc
Graduation Date : 2019-05
Supervisors : Dr. Carenini, Dr. Ng

Optimal mapping with topology change for animation and geometry problems
Zhu, Yufeng
DOI : 10.14288/1.0375785
URI : http://hdl.handle.net/2429/68102
Degree : Doctor of Philosophy - PhD
Graduation Date : 2019-05
Supervisors : Dr. Greif, Dr. Bridson

This thesis investigates several aspects of the optimal mapping problem, finding a bijective function between two shapes which minimizes some metric, and its many applications in computer graphics such as finding planar embeddings of curved surface meshes, image warping, mesh deformation, elastoplastic simulation, and more. We highlight in particular problems where differences in topology between the shapes—which necessitate discontinuities in the mapping—play a crucial role, e.g. due to animation decisions or physical fracture. Our first project presents an approach to extend discrete variational shape interpolation to create keyframe animation involving extreme deformation, topology change and dynamics. To construct correspondence between keyframe shapes as well as satisfying feature matching constraints, we introduce a consistent multimesh structure that is able to resolve topological in-equivalence between shapes and a Comesh Optimization algorithm that optimizes our multimesh for both intra and inter-mesh quality. To further speed up the total solving time, we then develop three new improvements to the state of the art nonlinear optimization techniques that are frequently used in this field, including a barrier-aware line-search filter that cures blocked descent steps due to element barrier terms; an energy proxy model that adaptively blends the Sobolev gradient and L-BFGS descent to gain the advantages of both; and a characteristic gradient norm providing a robust and largely mesh- and energy independent convergence criterion. Finally, we demonstrate another related interesting graphics application, brittle fracture simulation. In particular, we investigate whether we can sidestep the volumetric optimal mapping problem for solving elastic deformation and instead use a boundary element discretization which only requires a surface mesh. We will show how the computational cost of such problems can be alleviated using a boundary integral formulation and kernel-independent Fast Multipole Method. By combining with an explicit surface tracking framework, we further avoid the expensive volumetric mesh construction and maintenance during fracture propagation and shape topology change.