For sequences of related linear systems, the computation of a preconditioner for every system can be expensive. Often a fixed preconditioner is used, but this may not be effective as the matrix changes. This research examines the benefits of both reusing and recycling preconditioners, with special focus on ILUTP and factorized sparse approximate inverses and proposes an update that we refer to as a sparse approximate map or SAM update. Analysis of the residual and eigenvalues of the map will be provided. Applications include the Quantum Monte Carlo method, model reduction, oscillatory hydraulic tomography, diffuse optical tomography, and Helmholtz-type problems. / Master of Science

Recent advances in linear programming solution methodology have focused on interior point algorithms. These are powerful new methods, achieving significant reductions in computer time for large LPs and solving problems significantly larger than previously possible. This dissertation describes the implementation of interior point algorithms. It focuses on applications of direct sparse matrix methods to sparse symmetric positive definite systems of linear equations on scalar computers and vector supercomputers. The most computationally intensive step in each iteration of any interior point algorithm is the numerical factorization of a sparse symmetric positive definite matrix. In large problems or relatively dense problems, 80-90% or more of computational time is spent in this step. This study concentrates on solution methods for such linear systems. It is based on modifications and extensions of graph theory applied to sparse matrices. The row and column permutation of a sparse symmetric positive definite matrix dramatically affects the performance of solution algorithms. Various reordering methods are considered to find the best ordering for various numerical factorization methods and computer architectures. It is assumed that the reordering method will follow the fill-preserving rule, i.e., not allow additional fill-ins beyond that provided by the initial ordering. To follow this rule, a modular approach is used. In this approach, the matrix is first permuted by using any minimum degree heuristic, and then the permuted matrix is again reordered according to a specific reordering objective. Results of different reordering methods are described. There are several ways to compute the Cholesky factor of a symmetric positive definite matrix. A column Cholesky algorithm is a popular method for dense and sparse matrix factorization on serial and parallel computers. Applying this algorithm to a sparse matrix requires the use of sparse vector operations. Graph theory is applied to reduce sparse vector computations. A second and relatively new algorithm is the multifrontal algorithm. This method uses dense operations for sparse matrix computation at the expense of some data manipulation. The performance of the column Cholesky and multifrontal algorithms in the numerical factorization of a sparse symmetric positive definite matrix on an IBM 3090 vector supercomputer is described.

Hardware texture mapping is essential for real-time rendering. Unfortunately the memory bandwidth and latency often bounds performance in current graphics architectures. Bandwidth consumption can be reduced by compressing the texture map or by using a cache. However, the way a texture map occupies memory and how it is accessed affects the pattern of memory accesses, which in turn affects cache performance. Thus texture compression schemes and cache architectures must be designed in conjunction with each other. We define a sparse texture to be a texture where a substantial percentage of the texture is constant. Sparse textures are of interest as they occur often, and they are used as parts of more general texture compression schemes. We present a hardware compatible implementation of sparse textures based on B-tree indexing and explore cache designs for it. We demonstrate that it is possible to have the bandwidth consumption and miss rate due to the texture data alone scale with the area of the region of interest. We also show that the additional bandwidth consumption and hideable latency due to the B-tree indices are low. Furthermore, the caches necessary for these textures can be quite small.

The ionosphere is a dynamic and ionized medium. Specification of the ionospheric electron density is important for radio systems operating up to a few GHz. Such systems include communication, navigation and surveillance operations. Computerized Ionospheric Tomography (CIT) is a technique that allows specification of the electron density in the ionosphere. CIT, unlike medical tomography, has geometric limitations such as uneven and sparse distribution of ground-based receivers and limited-angle observations. The inversion is therefore underdetermined and to overcome the geometric limitations of the problem, regularization techniques need to be used. In this thesis the horizontal variation of the ionosphere is represented using wavelet basis functions. Wavelets are chosen because the ground based ionospheric instrumentation is unevenly distributed and hence there is an expectation that the resolution of the tomographic image will change across a large region of interest. Wavelets are able to represent structures with different scale and position efficiently, which is known as Multi Resolution Analysis (MRA). The theory of sparse regularization allows the usage of a small number of basis functions with minimum loss of information. Furthermore, sparsity through wavelets can better differentiate between noise and actual information. This is advantageous because it increases the efficacy to resolve the structures of the ionosphere at different spatial horizontal scale sizes. The basis set is also extended to incorporate time dependence in the tomographic images by means of three-dimensional wavelets. The methods have been tested using both simulated and real observations from the Global Navigation Satellite System (GNSS). The simulation was necessary in order to have a controllable environment where the ability to resolve different scale structures would be tested. The further analysis of the methods required also the use of real observations. They tested the technique under conditions of temporal dynamics that would be more difficult to reproduce with simulations, which often tend to be valid in quiet ionospheric behaviors. Improvements in the detection and reconstruction of ionospheric structures were illustrated with sparse regularization. The comparison was performed against two standard methods. The first one was based on spherical harmonics in space, whilst the second relied on a time-dependent smoothing regularization. In simulation, wavelets showed the possibility to resolve small-scale structures better than spherical harmonics and illustrated the potential of creating ionospheric maps at high resolution. In reality, GNSS satellite orbits allow satellite to receiver datasets that traverse the ionosphere at a few hundred km per second and hence a long time window of typically half an hour may be required to provide observations. The assumption of an unchanging ionosphere is only valid at some locations under very quiet geomagnetic conditions and at certain times of day. For this reason the theory was extended to include time dependence in the wavelet method. This was obtained by considering two approaches: a time-smooth regularization and three-dimensional wavelets. The wavelet method was illustrated on a European dataset and demonstrated some improvements in the reconstructions of the main trough. In conclusion wavelets and sparse regularization were demonstrated to be a valid alternative to more standard methods.

Principal Components Analysis (PCA) is a statistical procedure commonly used for the purpose of analyzing high dimensional data. It is often used for dimensionality reduction, which is accomplished by determining orthogonal components that contribute most to the underlying variance of the data. While PCA is widely used for identifying patterns and capturing variability of data in lower dimensions, it has some known limitations. In particular, PCA represents its results as linear combinations of data attributes. PCA is therefore, often seen as difficult to interpret and because of the underlying optimization problem that is being solved it is not robust to outliers. In this thesis, we examine extensions to PCA that address these limitations. Specific techniques researched in this thesis include variations of Robust and Sparse PCA as well as novel combinations of these two methods which result in a structured low-rank approximation that is robust to outliers. Our work is inspired by the well known machine learning methods of Least Absolute Shrinkage and Selection Operator (LASSO) as well as pointwise and group matrix norms. Practical applications including robust and non-linear methods for anomaly detection in Domain Name System network data as well as interpretable feature selection with respect to a website classification problem are discussed along with implementation details and techniques for analysis of regularization parameters.

In this thesis, we perform analysis and prediction for community structures in graphs using unsupervised learning. The methods we use require the data matrices to be of low rank, and such matrices appear quite often in real world problems across a broad range of domains. Such a modelling assumption is widely considered by classical algorithms such as principal component analysis (PCA), and the same assumption is often used to achieve dimensionality reduction. Dimension reduction, which is a classic method in unsupervised learning, can be leveraged in a wide array of problems, including prediction of strength of connection between communities from unlabeled or partially labeled data. Accordingly, a low rank assumption addresses many real world problems, and a low rank assumption has been used in this thesis to predict the strength of connection between communities in Amazon product data. In particular, we have analyzed real world data across retail and cyber domains, with the focus being on the retail domain. Herein, our focus is on analyzing the strength of connection between the communities in Amazon product data, where each community represents a group of products, and we are given the strength of connection between the individual products but not between the product communities. We call the strength of connection between individual products first order data and the strength of connection between communities second order data. This usage is inspired by [1] where first order time series are used to compute second order covariance matrices where such covariance matrices encode the strength of connection between the time series. In order to find the strength of connection between the communities, we define various metrics to measure this strength, and one of the goals of this thesis is to choose a good metric, which supports effective predictions. However, the main objective is to predict the strength of connection between most of the communities, given measurements of the strength of connection between only a few communities. To address this challenge, we use modern extensions of PCA such as eRPCA that can provide better predictions and can be computationally efficient for large problems. However, the current theory of eRPCA algorithms is not designed to treat problems where the initial data (such as the second order matrix of communities strength) is both low rank and sparse. Therefore, we analyze the performance of eRPCA algorithm on such data and modify our approaches for the particular structure of Amazon product communities to perform the necessary predictions.

Les thèmes principaux de ce mémoire sont la parcimonie et la discrimination pour la modélisation de données complexes. Dans un première partie de ce mémoire, nous nous plaçons dans un contexte de modèle de mélanges gaussiens: nous introduisons une nouvelle famille de modèles probabilistes qui simultanément classent et trouvent un espace discriminant tel que cet espace discrimine au mieux les groupes. Une famille de 12 modèles est introduite et se base sur deux idées clefs: tout d'abord, les données réelles vivent dans un sous-espace latent de dimension intrinsèque plus petite que celle de l'espace observé; deuxièmement, un sous-espace de dimensions K-1 est suffisant pour discriminer K groupes; enfin, l'espace observé et celui latent sont liés par une transformation linéaire. Une procédure d'estimation, appelée Fisher-EM, est proposée et améliore la plupart du temps les performances de clustering grâce à l'utilisation du sous-espace discriminant. Puisque chaque axe engendrant le sous-espace discriminant est une combinaison linéaire des variables d'origine, nous avons proposé trois méthodes différentes basées sur des critères pénalisés afin de faciliter l'interprétation des résultats. En particulier, ces méthodes permettent d'introduire de la parcimonie directement dans les composantes de la matrice de projection et peut se traduite comme une étape de sélection de variables discriminantes pour la classification. Dans une seconde partie, nous nous plaçons dans le contexte de la sériation. Nous proposons une mesure de dissimilarités basée sur le voisinage commun qui permet d'introduire de la parcimonie dans les données. Une procédure algorithmique appelée l'algorithme PB-Clus est introduite et permet d'obtenir une représentation diagonale par blocs des données. Cet outil permet de révéler la structure intrinsèque des données même dans le cas de données fortement bruitées ou de recouvrement de groupes. Ces deux méthodes ont été validées dans le cadre d'une application biologique basée sur la détection de cellules cancéreuses. / The main topics of this manuscript are sparsity and discrimination for modeling complex data. In a first part, we focus on the GMM context: we introduce a new family of probabilistic models which both clusters and finds a discriminative subspace chosen such as it best discriminates the groups. A family of 12 DLM models is introduced and is based on two three-ideas: firstly, the actual data live in a latent subspace with an intrinsic dimension lower than the dimension of the observed space; secondly, a subspace of K-1 dimensions is theoretically sufficient to discriminate K groups; thirdly, the observation and the latent spaces are linked by a linear transformation. An estimation procedure, named Fisher-EM is proposed and improves, most of the time, clustering performances owing to the use of a discriminative subspace. As each axis, spanning the discriminative subspace, is a linear combination of all original variables, we therefore proposed 3 different methods based on a penalized criterion in order to ease the interpretation results. In particular, it allows to introduce sparsity directly in the loadings of the projection matrix which enables also to make variable selection for clustering. In a second part, we deal with the seriation context. We propose a dissimilarity measure based on a common neighborhood which allows to deal with noisy data and overlapping groups. A forward stepwise seriation algorithm, called the PB-Clus algorithm, is introduced and allows to obtain a block representation form of the data. This tool enables to reveal the intrinsic structure of data even in the case of noisy data, outliers, overlapping and non-Gaussian groups. Both methods has been validated on a biological application based on the cancer cell detection.

There are a variety of chromosomal abnormalities such as translocation, duplication, deletion, insertion and inversion, which may cause severe diseases, e.g., cancers and birth defects. Multi-color fluorescence in-situ hybridization (M-FISH) is an imaging technique popularly used for simultaneously detecting and visualizing these complex abnormalities in a single hybridization. In spite of the advancement of fluorescence microscopy for chromosomal abnormality detection, the quality of the fluorescence images is still limited, due to the spectral overlap, uneven intensity level across multiple channels, variations of background and inhomogeneous intensity within intra-channels. Therefore, it is critical but challenging to distinguish the different types of chromosomes accurately in order to detect the chromosomal abnormalities from M-FISH images. The main contribution of this dissertation is to develop an M-FISH image analysis pipeline by taking full advantage of spatial and spectral information from M-FISH imaging. In addition, novel image analysis approaches such as the sparse representation are applied in this work. The pipeline starts with the image preprocessing to extract the background to improve the quality of the raw images by low-rank plus group lasso decomposition. Then, the image segmentation is performed by incorporating both spatial and spectral information by total variation (TV) and row-wise constraints. Finally image classification is conducted by considering the structural information of neighboring pixels with a row-wise sparse representation model. In each step, new methods and sophisticated algorithms were developed and compared with several popularly used methods, It shows that (1) the preprocessing model improves the quality of the raw images; (2) the segmentation model outperforms than both fuzzy c-means (FCM) and improved adaptive fuzzy c-means (IAFCM) models in terms of correct ratio and false rate; and (3) the classification model corrects the misclassification to improve the accuracy of chromosomal abnormalities detection, especially for the complex inter-chromosomal rearrangements. / 1 / Jingyao Li

1 / DONGDONG LIN

Research Doctorate - Doctor of Philosophy (PhD) / In this thesis, a number of new methods for constructing vertex-magic total-labelings of graphs are presented. These represent an advance on existing methods since they are general constructions rather than ad hoc constructions for specific families of graphs. Broadly, five new kinds of construction methods are presented. Firstly, we present a class of methods characterized by adding 2- or 4-factors to a labeled graph, reassigning vertex labels to the edges of these factors and then adding new vertex labels to create a VMTL of the new graph. The major result is a unified method for constructing VMTL of large families of regular graphs, providing strong evidence for MacDougall's conjecture that, apart from a few minor exceptions, all regular graphs possess vertex-magic total-labelings. Secondly, we present methods for obtaining a labeling of a union of two graphs, one of which possesses a strong labeling, and then building on this labeling to create a labeling of an irregular graph. These methods as well as results in the Appendices provide strong evidence against an early conjecture regarding labelings and vertex degrees. Thirdly, constructions are presented for a new kind of magic square, containing some zeroes, which can be used to build labelings of graphs from labeled spanning subgraphs. Next, constructions are presented for a new kind of anti-magic square, containing some zeroes, which is equivalent to a strong labeling of certain kinds of bipartite graphs which can in turn be built upon to produce labelings of graphs with more edges. Finally, we present a method of mutating a graph labeling by reassigning edges in a way that preserves the magic constant to obtain a labeling of a different graph. This method provides a prolific source of new labelings.