School of Computational Science and Engineering Theses and Dissertationshttp://hdl.handle.net/1853/459802023-03-27T09:59:24Z2023-03-27T09:59:24ZData Tiling for Sparse ComputationAn, Xiaojinghttp://hdl.handle.net/1853/701292023-02-27T21:39:36Z2022-11-11T00:00:00ZData Tiling for Sparse Computation
An, Xiaojing
Many real-world data contain internal relationships. Efficient analysis of these relationship data is crucial for important problems including genome alignment, network vulnerability analysis, ranking web pages, among others. Such relationship data is frequently sparse and analysis on it is called sparse computation. We demonstrate that the important technique of data tiling is more powerful than previously known by broadening its application space. We focus on three important sparse computation areas: graph analysis, linear algebra, and bioinformatics. We demonstrate data tiling's power by addressing key issues and providing significant improvements---to both runtime and solution quality---in each area. For graph analysis, we focus on fast data tiling techniques that can produce well-structured tiles and demonstrate theoretical hardness results. These tiles are suitable for graph problems as they reduce data movement and ultimately improve end-to-end runtime performance. For linear algebra, we introduce a new cache-aware tiling technique and apply it to the key kernel of sparse matrix by sparse matrix multiplication. This technique tiles the second input matrix and then uses a small, summary matrix to guide access to the tiles during computation. Our approach results in the fastest known implementation across three distinct CPU architectures. In bioinformatics, we develop a tiling based de novo genome assembly pipeline. We start with reads and develop either a graph or hypergraph that captures internal relationships between reads. This is then tiled to minimize connections while maintaining balance. We then treat each resulting tile independently as the input to an existing, shared-memory assembler. Our pipeline improves existing state-of-the-art de novo genome assemblers and brings both runtime and quality improvements to them on both real-world and simulated datasets.
2022-11-11T00:00:00ZAn, XiaojingMany real-world data contain internal relationships. Efficient analysis of these relationship data is crucial for important problems including genome alignment, network vulnerability analysis, ranking web pages, among others. Such relationship data is frequently sparse and analysis on it is called sparse computation. We demonstrate that the important technique of data tiling is more powerful than previously known by broadening its application space. We focus on three important sparse computation areas: graph analysis, linear algebra, and bioinformatics. We demonstrate data tiling's power by addressing key issues and providing significant improvements---to both runtime and solution quality---in each area. For graph analysis, we focus on fast data tiling techniques that can produce well-structured tiles and demonstrate theoretical hardness results. These tiles are suitable for graph problems as they reduce data movement and ultimately improve end-to-end runtime performance. For linear algebra, we introduce a new cache-aware tiling technique and apply it to the key kernel of sparse matrix by sparse matrix multiplication. This technique tiles the second input matrix and then uses a small, summary matrix to guide access to the tiles during computation. Our approach results in the fastest known implementation across three distinct CPU architectures. In bioinformatics, we develop a tiling based de novo genome assembly pipeline. We start with reads and develop either a graph or hypergraph that captures internal relationships between reads. This is then tiled to minimize connections while maintaining balance. We then treat each resulting tile independently as the input to an existing, shared-memory assembler. Our pipeline improves existing state-of-the-art de novo genome assemblers and brings both runtime and quality improvements to them on both real-world and simulated datasets.Extracting Signals and Graphical Models from Compressed MeasurementsZhang, Hanghttp://hdl.handle.net/1853/700302023-01-23T21:49:43Z2021-12-08T00:00:00ZExtracting Signals and Graphical Models from Compressed Measurements
Zhang, Hang
The thesis is to give an integrated approach to efficiently learn the interdependency relation among high dimensional signal components and reconstruct signals from observations collected in a linear sensing system, Broadly speaking, the research topics consists of three parts: (i) interdependency relation learning; (ii) sensing system design; and (iii) signal reconstruction. In the interdependency relation learning part, we considered both the parametric and non-parametric methods to learn the graphical structure under the noisy indirect measurements. In the sensing system design part, we introduced a density evolution framework to design sensing systems for compressive sensing for the first time. In the signal reconstruction part, we focused on the signal reconstruction with a given sensing system, which consists of three parts: signal reconstruction with inexact knowledge of the sensing system; signal reconstruction with the signal being contaminated by undesired noise; signal reconstruction with the signal belonging to a union of convex sets.
2021-12-08T00:00:00ZZhang, HangThe thesis is to give an integrated approach to efficiently learn the interdependency relation among high dimensional signal components and reconstruct signals from observations collected in a linear sensing system, Broadly speaking, the research topics consists of three parts: (i) interdependency relation learning; (ii) sensing system design; and (iii) signal reconstruction. In the interdependency relation learning part, we considered both the parametric and non-parametric methods to learn the graphical structure under the noisy indirect measurements. In the sensing system design part, we introduced a density evolution framework to design sensing systems for compressive sensing for the first time. In the signal reconstruction part, we focused on the signal reconstruction with a given sensing system, which consists of three parts: signal reconstruction with inexact knowledge of the sensing system; signal reconstruction with the signal being contaminated by undesired noise; signal reconstruction with the signal belonging to a union of convex sets.Scalable Data Mining via Constrained Low Rank ApproximationEswar, Srinivashttp://hdl.handle.net/1853/673342023-01-23T21:55:45Z2022-08-01T00:00:00ZScalable Data Mining via Constrained Low Rank Approximation
Eswar, Srinivas
Matrix and tensor approximation methods are recognised as foundational tools for modern data analytics. Their strength lies in their long history of rigorous and principled theoretical foundations, judicious formulations via various constraints, along with the availability of fast computer programs. Multiple Constrained Low Rank Approximation (CLRA) formulations exist for various commonly encountered tasks like clustering, dimensionality reduction, anomaly detection, amongst others. The primary challenge in modern data analytics is the sheer volume of data to be analysed, often requiring multiple machines to just hold the dataset in memory. This dissertation presents CLRA as a key enabler of scalable data mining in distributed-memory parallel machines.
Nonnegative Matrix Factorisation (NMF) is the primary CLRA method studied in this dissertation. NMF imposes nonnegativity constraints on the factor matrices and is a well studied formulation known for its simplicity, interpretability, and clustering prowess. The major bottleneck in most NMF algorithms is a distributed matrix-multiplication kernel. We develop the Parallel Low rank Approximation with Nonnegativity Constraints (PLANC) software package, building on the earlier MPI-FAUN library, which includes an efficient matrix-multiplication kernel tailored to the CLRA case. It employs carefully designed parallel algorithms and data distributions to avoid unnecessary computation and communication.
We extend PLANC to include several optimised Nonnegative Least-Squares (NLS) solvers and symmetric constraints, effectively employing the optimised matrix-multiplication kernel. We develop a parallel inexact Gauss-Newton algorithm for Symmetric Nonnegative Matrix Factorisation (SymNMF). In particular PLANC is able to efficiently utilise second-order information when imposing symmetry constraints without incurring the prohibitive memory and computational costs associated with these methods. We are able to observe 70% efficiency while scaling up these methods.
We develop new parallel algorithms for fusing and analysing data with multiple modalities in the Joint Nonnegative Matrix Factorisation (JointNMF) context. JointNMF is capable of knowledge discovery when both feature-data and data-data information is present in a data source. We extend PLANC to handle this case of simultaneously approximating two different large input matrices and study the various trade-offs encountered in the bottleneck matrix-multiplication kernel.
We show that these ideas translate naturally to the multilinear setting when data is presented in the form of a tensor. A bottleneck computation analogous to the matrix-multiply, the Matricised-Tensor Times Khatri-Rao Product (MTTKRP) kernel, is implemented. We conclude by describing some avenues for future research which extend the work and ideas in this dissertation. In particular, we consider the notion of structured sparsity, where the user has some control over the nonzero pattern, which appears in computations for various tasks like cross-validation, working with missing values, robust CLRA models, and in the semi-supervised setting.
2022-08-01T00:00:00ZEswar, SrinivasMatrix and tensor approximation methods are recognised as foundational tools for modern data analytics. Their strength lies in their long history of rigorous and principled theoretical foundations, judicious formulations via various constraints, along with the availability of fast computer programs. Multiple Constrained Low Rank Approximation (CLRA) formulations exist for various commonly encountered tasks like clustering, dimensionality reduction, anomaly detection, amongst others. The primary challenge in modern data analytics is the sheer volume of data to be analysed, often requiring multiple machines to just hold the dataset in memory. This dissertation presents CLRA as a key enabler of scalable data mining in distributed-memory parallel machines.
Nonnegative Matrix Factorisation (NMF) is the primary CLRA method studied in this dissertation. NMF imposes nonnegativity constraints on the factor matrices and is a well studied formulation known for its simplicity, interpretability, and clustering prowess. The major bottleneck in most NMF algorithms is a distributed matrix-multiplication kernel. We develop the Parallel Low rank Approximation with Nonnegativity Constraints (PLANC) software package, building on the earlier MPI-FAUN library, which includes an efficient matrix-multiplication kernel tailored to the CLRA case. It employs carefully designed parallel algorithms and data distributions to avoid unnecessary computation and communication.
We extend PLANC to include several optimised Nonnegative Least-Squares (NLS) solvers and symmetric constraints, effectively employing the optimised matrix-multiplication kernel. We develop a parallel inexact Gauss-Newton algorithm for Symmetric Nonnegative Matrix Factorisation (SymNMF). In particular PLANC is able to efficiently utilise second-order information when imposing symmetry constraints without incurring the prohibitive memory and computational costs associated with these methods. We are able to observe 70% efficiency while scaling up these methods.
We develop new parallel algorithms for fusing and analysing data with multiple modalities in the Joint Nonnegative Matrix Factorisation (JointNMF) context. JointNMF is capable of knowledge discovery when both feature-data and data-data information is present in a data source. We extend PLANC to handle this case of simultaneously approximating two different large input matrices and study the various trade-offs encountered in the bottleneck matrix-multiplication kernel.
We show that these ideas translate naturally to the multilinear setting when data is presented in the form of a tensor. A bottleneck computation analogous to the matrix-multiply, the Matricised-Tensor Times Khatri-Rao Product (MTTKRP) kernel, is implemented. We conclude by describing some avenues for future research which extend the work and ideas in this dissertation. In particular, we consider the notion of structured sparsity, where the user has some control over the nonzero pattern, which appears in computations for various tasks like cross-validation, working with missing values, robust CLRA models, and in the semi-supervised setting.Robust Reservoir Computing Approaches for Predicting Cardiac Electrical DynamicsShahi, Shahrokhhttp://hdl.handle.net/1853/672862023-02-27T21:39:36Z2022-07-29T00:00:00ZRobust Reservoir Computing Approaches for Predicting Cardiac Electrical Dynamics
Shahi, Shahrokh
Computational modeling of cardiac electrophysiological signaling is of vital importance in understanding, preventing, and treating life-threatening arrhythmias. Traditionally, mathematical models incorporating physical principles have been used to study cardiac dynamical systems and can generate mechanistic insights, but their predictions are often quantitatively inaccurate due to model complexity, the lack of observability in the system, and variability within individuals and across the population. In contrast, machine-learning techniques can learn directly from training data, which in this context are time series of observed state variables, without prior knowledge of the system dynamics. The reservoir computing framework, a learning paradigm derived from recurrent neural network concepts and most commonly realized as an echo state network (ESN), offers a streamlined training process and holds promise to deliver more accurate predictions than mechanistic models. Accordingly, this research aims to develop robust ESN-based forecasting approaches for nonlinear cardiac electrodynamics, and thus presents the first application of machine-learning, and deep-learning techniques in particular, for modeling the complex electrical dynamics of cardiac cells and tissue.
To accomplish this goal, we completed a set of three projects. (i) We compared the performance of available mainstream techniques for prediction with that of the baseline ESN approach along with several new ESN variants we proposed, including a physics-informed hybrid ESN. (ii) We proposed a novel integrated approach, the autoencoder echo state network (AE-ESN), that can accurately forecast the long-term future dynamics of cardiac electrical activity. This technique takes advantage of the best characteristics of both gated recurrent neural networks and ESNs by integrating a long short-term memory (LSTM) autoencoder into the ESN framework to improve reliability and robustness. (iii) We extended the long-term prediction of cardiac electrodynamics from a single cardiac cell to the tissue level, where, in addition to the temporal information, the data includes spatial dimensions and diffusive coupling. Building on the main design idea of the AE-ESN, a convolutional autoencoder was equipped with an ESN to create the Conv-ESN technique, which can process the spatiotemporal data and effectively capture the temporal dependencies between samples of data.
Using these techniques, we forecast cardiac electrodynamics for a variety of datasets obtained in both in silico and in vitro experiments. We found that the proposed integrated approaches provide robust and computationally efficient techniques that can successfully predict the dynamics of electrical activity in cardiac cells and tissue with higher prediction accuracy than mainstream deep-learning approaches commonly used for predicting temporal data. On the application side, our approaches provide accurate forecasts over clinically useful time periods that could allow prediction of electrical problems with sufficient time for intervention and thus may support new types of treatments for some kinds of heart disease.
2022-07-29T00:00:00ZShahi, ShahrokhComputational modeling of cardiac electrophysiological signaling is of vital importance in understanding, preventing, and treating life-threatening arrhythmias. Traditionally, mathematical models incorporating physical principles have been used to study cardiac dynamical systems and can generate mechanistic insights, but their predictions are often quantitatively inaccurate due to model complexity, the lack of observability in the system, and variability within individuals and across the population. In contrast, machine-learning techniques can learn directly from training data, which in this context are time series of observed state variables, without prior knowledge of the system dynamics. The reservoir computing framework, a learning paradigm derived from recurrent neural network concepts and most commonly realized as an echo state network (ESN), offers a streamlined training process and holds promise to deliver more accurate predictions than mechanistic models. Accordingly, this research aims to develop robust ESN-based forecasting approaches for nonlinear cardiac electrodynamics, and thus presents the first application of machine-learning, and deep-learning techniques in particular, for modeling the complex electrical dynamics of cardiac cells and tissue.
To accomplish this goal, we completed a set of three projects. (i) We compared the performance of available mainstream techniques for prediction with that of the baseline ESN approach along with several new ESN variants we proposed, including a physics-informed hybrid ESN. (ii) We proposed a novel integrated approach, the autoencoder echo state network (AE-ESN), that can accurately forecast the long-term future dynamics of cardiac electrical activity. This technique takes advantage of the best characteristics of both gated recurrent neural networks and ESNs by integrating a long short-term memory (LSTM) autoencoder into the ESN framework to improve reliability and robustness. (iii) We extended the long-term prediction of cardiac electrodynamics from a single cardiac cell to the tissue level, where, in addition to the temporal information, the data includes spatial dimensions and diffusive coupling. Building on the main design idea of the AE-ESN, a convolutional autoencoder was equipped with an ESN to create the Conv-ESN technique, which can process the spatiotemporal data and effectively capture the temporal dependencies between samples of data.
Using these techniques, we forecast cardiac electrodynamics for a variety of datasets obtained in both in silico and in vitro experiments. We found that the proposed integrated approaches provide robust and computationally efficient techniques that can successfully predict the dynamics of electrical activity in cardiac cells and tissue with higher prediction accuracy than mainstream deep-learning approaches commonly used for predicting temporal data. On the application side, our approaches provide accurate forecasts over clinically useful time periods that could allow prediction of electrical problems with sufficient time for intervention and thus may support new types of treatments for some kinds of heart disease.