This dissertation is devoted to studying a fast and analytic approximation method, called the variational Bayesian (VB) method, and aims to give insight into its general applicability and usefulness, and explore its applications to various real-world problems. This work has three main foci: 1) The general applicability and properties; 2) Diagnostics for VB approximations; 3) Variational applications. Generally, the variational inference has been developed in the context of the exponential family, which is open to further development. First, it usually consider the cases in the context of the conjugate exponential family. Second, the variational inferences are developed only with respect to natural parameters, which are often not the parameters of immediate interest. Moreover, the full factorization, which assumes all terms to be independent of one another, is the most commonly used scheme in the most of the variational applications. We show that VB inferences can be extended to a more general situation. We propose a special parameterization for a parametric family, and also propose a factorization scheme with a more general dependency structure than is traditional in VB. Based on these new frameworks, we develop a variational formalism, in which VB has a fast implementation, and not be limited to the conjugate exponential setting. We also investigate its local convergence property, the effects of choosing different priors, and the effects of choosing different factorization scheme. The essence of the VB method relies on making simplifying assumptions about the posterior dependence of a problem. By definition, the general posterior dependence structure is distorted. In addition, in the various applications, we observe that the posterior variances are often underestimated. We aim to develop diagnostics test to assess VB approximations, and these methods are expected to be quick and easy to use, and to require no sophisticated tuning expertise. We propose three methods to compute the actual posterior covariance matrix by only using the knowledge obtained from VB approximations: 1) To look at the joint posterior distribution and attempt to find an optimal affine transformation that links the VB and true posteriors; 2) Based on a marginal posterior density approximation to work in specific low dimensional directions to estimate true posterior variances and correlations; 3) Based on a stepwise conditional approach, to construct and solve a set of system of equations that lead to estimates of the true posterior variances and correlations. A key computation in the above methods is to calculate a uni-variate marginal or conditional variance. We propose a novel way, called the VB Adjusted Independent Metropolis-Hastings (VBAIMH) method, to compute these quantities. It uses an independent Metropolis-Hastings (IMH) algorithm with proposal distributions configured by VB approximations. The variance of the target distribution is obtained by monitoring the acceptance rate of the generated chain. One major question associated with the VB method is how well the approximations can work. We particularly study the mean structure approximations, and show how it is possible using VB approximations to approach model selection tasks such as determining the dimensionality of a model, or variable selection. We also consider the variational application in Bayesian nonparametric modeling, especially for the Dirichlet process (DP). The posterior inference for DP has been extensively studied in the context of MCMC methods. This work presents a a full variational solution for DP with non-conjugate settings. Our solution uses a truncated stick-breaking representation. We propose an empirical method to determine the number of distinct components in a finite dimensional DP. The posterior predictive distribution for DP is often not available in a closed form. We show how to use the variational techniques to approximate this quantity. As a concrete application study, we work through the VB method on regime-switching lognormal models and present solutions to quantify both the uncertainty in the parameters and model specification. Through a series numerical comparison studies with likelihood based methods and MCMC methods on the simulated and real data sets, we show that the VB method can recover exactly the model structure, gives the reasonable point estimates, and is very computationally efficient.

Long term data generated at four rural stations are compared to determine similarities and differences in aerosol compositions and factors contributing to observed differences at different regions in Turkey. The stations used in this study are located at Mediterranean coast (20 km to the west of Antalya city), Black Sea coast (20 km to the east of Amasra town), Central Anatolia (&Ccedil / ubuk, Ankara) and Northeastern part of the Anatolian Plateau (at Mt. Uludag). Data used in comparisons were generated in previous studies. However, some re-analysis of data were also performed / (1) to improve the similarities of the parameters compared and (2) to be able to apply recently-developed methodologies to data sets. Data from Mediterranean and Black Sea stations were identical in terms of parameters measured and were suitable for extensive comparison. However, fewer parameters were measured at &Ccedil / ubuk and Uludag stations, which limited the comparisons involving these two stations. Comparison included levels of major ions and elements, short-term and seasonal variations in concentrations, background (baseline) concentrations of elements, flow climatology of regions, correlations between elements, potential source areas affecting regions, and source types affecting chemical composition of particles. Comparison of levels of measured parameters in four regions showed that there are some differences in concentrations that arise from differences in the local characteristics of the sampling points. For example very high concentrations of elements such as Na and Cl in the Mediterranean region is attributed to closer proximity of the Antalya station to coast and not a general feature of the Mediterranean aerosol. There are also significant regional differences in the concentrations of measured elements and ions as well. Concentrations of anthropogenic elements are very similar at two coastal stations (Antalya and Amasra), but they are approximately a factor of two smaller at the two stations that are located on the Anatolian Plateau. This difference between coastal and high altitude plateau stations, which is common to all anthropogenic species, is attributed to different source regions and transport mechanisms influencing coastal regions and Anatolian Plateau. Some statistically significant differences were also observed in the temporal variations of elements and ions measured in different stations. The elements with crustal origin showed similar seasonal pattern at all stations, with higher concentrations in summer and lower concentrations in winter. This difference between summer and winter is attributed to suppression of re-suspension of crustal aerosol from wet or ice-covered surface soil in winter. Concentrations of anthropogenic elements, on the other hand, did not show a statistically significant seasonal trend at Amasra, &Ccedil / ubuk and Uludag stations, but they have higher concentrations during summer months at the Antalya station. This difference between Mediterranean aerosol and aerosol at the Central and Northern Turkey is due to influence of more local sources on &Ccedil / ubuk, Amasra and Uludag stations and domination of more distant source in determining aerosol composition at the Mediterranean region. A similar conclusion of strong influence of local sources on chemical composition of particles at the Central Anatolia was also suggested by the comparison of baseline concentrations in each station. General features in flow climatology (residence times of upper atmospheric air masses) in each region are found to be similar with more frequent flow from W, WNW, NW and NNW wind sectors. Since these are the sectors that include high emitting countries in Eastern and Western Europe and Russia, transport from these sectors are expected to bring pollution from both distant European countries and more local Balkan countries and western parts of Turkey. Flow climatology in stations showed small, but statistically significant, differences between summer and winter seasons. These variations suggested that the station at the Central Anatolia and Black Sea (&Ccedil / ubuk Amasra and Uludag stations) are affected from sources located at the Western Europe in winter season and from sources located at the Eastern Europe in summer. Mediterranean aerosol, on the other hand, are affected from sources at the Western Europe and do not show any seasonal differences. This variation in flow climatology between summer and winter seasons (and lack of variation at the Mediterranean station) is supported by the seasonal variation (and lack of variation at the Mediterranean station) in SO42-/NO3- ratio measured at the stations. Potential source contribution function (PSCF) values are calculated for selected elements and ions in each station. Statistical significance of calculated PSCF values is tested using bootstrapping technique. Results showed that specific grids at Russia and at Balkan countries are common source regions affecting concentrations of anthropogenic elements at all four regions in Turkey. However, each station is also affected from specific source regions as well. Aerosol composition at the Anatolian Plateau are affected from sources closer to the sampling points whereas Mediterranean and Black Sea aerosol are affected from source regions that farther away from the receptors. It should be noted that the same conclusion is also reached in comparison of seasonal patterns and baseline concentrations at these stations. Types of sources affecting aerosol composition at Black Sea, Mediterranean and Central Anatolia are also compared. Source types affecting atmospheric composition in these regions were calculated using positive matrix factorization (PMF). The results showed that aerosol at the Black Sea, Central Anatolia and Mediterranean atmosphere consists of 8, 6 and 7 components, respectively. Two of these components, namely a crustal component and a long-range transport component are common in all three stations. The chemical compositions of these common components are shown to the same within 95% statistical significance interval. Three factors, namely a fertilizer factor, which is highly enriched in NH4+ ion, a sea salt component and an arsenic factor are common in the Mediterranean and Black Sea aerosol but not observed at the Central Anatolia. Other factors found in the regions are specific for that region.

Πολλά κρυπτογραφικά σχήματα δημόσιου κλειδιού βασίζονται στο γεγονός ότι είναι υπολογιστικά δύσκολο να παραγοντοποιήσουμε μεγάλους ακέραιους αριθμούς. Ο ταχύτερος, και ταυτόχρονα πολυπλοκότερος, κλασσικός αλγόριθμος που είναι γνωστός μέχρι σήμερα για την παραγοντοποίηση ακεραίων μήκους άνω των 110 δεκαδικών ψηφίων είναι ο General Number Field Sieve (GNFS). Ο αλγόριθμος αυτός είναι ο καρπός πολλών ετών έρευνας, κατά τη διάρκεια της οποίας παράγονταν ολοένα και ταχύτεροι αλγόριθμοι για να καταλήξουμε μέχρι στιγμής στον αλγόριθμο GNFS. Πρωταρχικός σκοπός της παρούσης μεταπτυχιακής εργασίας είναι η παρουσίαση του θεωρητικού μαθηματικού υπόβαθρου πάνω στο οποίο βασίζεται ο GNFS καθώς και η ακολουθιακή υλοποίηση της βασικής εκδοχής του αλγορίθμου. Ως γλώσσα υλοποίησης επιλέχθηκε η C++. Η υλοποίηση έγινε σε συνεργασία με τον συμφοιτητή μου και αγαπητό φίλο Χρήστο Μπακογιάννη, όπου στα πλαίσια της μεταπτυχιακής του εργασίας πραγματοποιήθηκε η μεταφορά της ακολουθιακής υλοποίησης του αλγορίθμου σε παράλληλο κατανεμημένο περιβάλλον χρησιμοποιώντας το Message Passing Interface (MPI). Ο πηγαίος κώδικας της υλοποίησης καθώς και σχετικές πληροφορίες υπάρχουν online στη σελίδα http://kmgnfs.cti.gr. Σημειώνεται πως για την ευκολότερη και απρόσκοπτη ανάγνωση της εργασίας αυτής, ο αναγνώστης θα πρέπει να έχει ένα βαθμό εξοικείωσης με βασικές έννοιες της θεωρίας αριθμών, της αλγεβρικής θεωρίας αριθμών και της γραμμικής άλγεβρας. / Many public-key cryptosystems build their security on our inability to factor very large integers. The General Number Field Sieve (GNFS) is the most efficient, and at the same time most complex, classical known algorithm for factoring integers larger than 110 digits. This algorithm is the result of many years of research, during which, faster and faster algorithms were developed finally winding up to the development of the GNFS. The main purpose of this master thesis is the presentation of the mathematical ideas, on which the GNFS was developed, as well as a sequential implementation of the basic version of the algorithm. C++ was the language of choice. The implementation took place in collaboration with my colleague and dear friend Christos Bakogiannis, where as part of his master thesis, a distributed implementation of the algorithm using Message Passing Interface (MPI) was also developed. The source code of the implementations is publicly available and can be found online at http://kmgnfs.cti.gr. It is presumed that the reader is familiar with basic concepts of number theory, algebraic number theory and linear algebra.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-04-11T14:50:08Z No. of bitstreams: 1 CAIO SANTOS BEZERRA NÓBREGA - DISSERTAÇÃO PPGCC 2014..pdf: 983246 bytes, checksum: 5eca7651706ce317dc514ec2f1aa10c3 (MD5) / Made available in DSpace on 2018-04-11T14:50:08Z (GMT). No. of bitstreams: 1 CAIO SANTOS BEZERRA NÓBREGA - DISSERTAÇÃO PPGCC 2014..pdf: 983246 bytes, checksum: 5eca7651706ce317dc514ec2f1aa10c3 (MD5) Previous issue date: 2014-07-30 / Capes / Sugerir os produtos mais apropriados aos diversos tipos de consumidores não é uma tarefa trivial, apesar de ser um fator chave para aumentar satisfação e lealdade destes. Devido a esse fato, sistemas de recomendação têm se tornado uma ferramenta importante para diversas aplicações, tais como, comércio eletrônico, sites personalizados e redes sociais. Recentemente, a fatoração de matrizes se tornou a técnica mais bem sucedida de implementação de sistemas de recomendação. Os parâmetros do modelo de fatoração de matrizes são tipicamente aprendidos por meio de métodos numéricos, tal como o gradiente descendente. O desempenho do gradiente descendente está diretamente relacionada à configuração da taxa de aprendizagem, a qual é tipicamente configurada para valores pequenos, com o objetivo de não perder um mínimo local. Consequentemente, o algoritmo pode levar várias iterações para convergir. Idealmente,é desejada uma taxa de aprendizagem que conduza a um mínimo local nas primeiras iterações, mas isto é muito difícil de ser realizado dada a alta complexidade do espaço de valores a serem pesquisados. Começando com um estudo exploratório em várias bases de dados de sistemas de recomendação, observamos que, para a maioria das bases, há um padrão linear entre a taxa de aprendizagem e o número de iterações necessárias para atingir a convergência. A partir disso, propomos utilizar modelos de regressão lineares simples para predizer, para uma base de dados desconhecida, um bom valor para a taxa de aprendizagem inicial. A ideia é estimar uma taxa de aprendizagem que conduza o gradiente descendenteaummínimolocalnasprimeirasiterações. Avaliamosnossatécnicaem8bases desistemasderecomendaçãoreaisecomparamoscomoalgoritmopadrão,oqualutilizaum valorfixoparaataxadeaprendizagem,ecomtécnicasqueadaptamataxadeaprendizagem extraídas da literatura. Nós mostramos que conseguimos reduzir o número de iterações até em 40% quando comparados à abordagem padrão. / Suggesting the most suitable products to different types of consumers is not a trivial task, despite being a key factor for increasing their satisfaction and loyalty. Due to this fact, recommender systems have be come an important tool for many applications, such as e-commerce, personalized websites and social networks. Recently, Matrix Factorization has become the most successful technique to implement recommendation systems. The parameters of this model are typically learned by means of numerical methods, like the gradient descent. The performance of the gradient descent is directly related to the configuration of the learning rate, which is typically set to small values, in order to do not miss a local minimum. As a consequence, the algorithm may take several iterations to converge. Ideally, one wants to find a learning rate that will lead to a local minimum in the early iterations, but this is very difficult to achieve given the high complexity of search space. Starting with an exploratory study on several recommendation systems datasets, we observed that there is an over all linear relationship between the learnin grate and the number of iterations needed until convergence. From this, we propose to use simple linear regression models to predict, for a unknown dataset, a good value for an initial learning rate. The idea is to estimate a learning rate that drives the gradient descent as close as possible to a local minimum in the first iteration. We evaluate our technique on 8 real-world recommender datasets and compared it with the standard Matrix Factorization learning algorithm, which uses a fixed value for the learning rate over all iterations, and techniques fromt he literature that adapt the learning rate. We show that we can reduce the number of iterations until at 40% compared to the standard approach.

Which matrices can be written as sums or products of square-zero matrices? This question is the central premise of this dissertation. Over the past 25 years a signi - cant body of research on products and linear combinations of square-zero matrices has developed, and it is the aim of this study to present this body of research in a consolidated, holistic format, that could serve as a theoretical introduction to the subject. The content of the research is presented in three parts: rst results within the broader context of sums and products of nilpotent matrices are discussed, then products of square-zero matrices, and nally sums of square-zero matrices. / Mathematical Sciences / M. Sc. (Mathematics)

Les travaux de thèse effectués dans le cadre de la convention Cifre conclue entrele laboratoire de mathématiques de Besançon et Digital Surf, entreprise éditrice dulogiciel d’analyse métrologique Mountains, portent sur les techniques d’analyse hyperspectrale.Sujet en plein essor, ces méthodes permettent d’exploiter des imagesissues de micro-spectroscopie, et en particulier de spectroscopie Raman. Digital Surfambitionne aujourd’hui de concevoir des solutions logicielles adaptées aux imagesproduites par ces appareils. Ces dernières se présentent sous forme de cubes de valeurs,où chaque pixel correspond à un spectre. La taille importante de ces données,appelées images hyperspectrales en raison du nombre important de mesures disponiblespour chaque spectre, obligent à repenser certains des algorithmes classiquesd’analyse d’image.Nous commençons par nous intéresser aux techniques de partitionnement de données.L’idée est de regrouper dans des classes homogènes les différents spectres correspondantà des matériaux similaires. La classification est une des techniques courammentutilisée en traitement des données. Cette tâche fait pourtant partie d’unensemble de problèmes réputés trop complexes pour une résolution pratique : les problèmesNP-durs. L’efficacité des différentes heuristiques utilisées en pratique était jusqu’àrécemment mal comprise. Nous proposons des argument théoriques permettantde donner des garanties de succès quand les groupes à séparer présentent certainespropriétés statistiques.Nous abordons ensuite les techniques de dé-mélange. Cette fois, il ne s’agit plus dedéterminer un ensemble de pixels semblables dans l’image, mais de proposer une interprétationde chaque pixel comme un mélange linéaire de différentes signatures spectrales,sensées émaner de matériaux purs. Cette déconstruction de spectres compositesse traduit mathématiquement comme un problème de factorisation en matrices positives.Ce problème est NP-dur lui aussi. Nous envisageons donc certaines relaxations,malencontreusement peu convaincantes en pratique. Contrairement au problème declassification, il semble très difficile de donner de bonnes garanties théoriques sur laqualité des résultats proposés. Nous adoptons donc une approche plus pragmatique,et proposons de régulariser cette factorisation en imposant des contraintes sur lavariation totale de chaque facteur.Finalement, nous donnons un aperçu d’autres problèmes d’analyse hyperspectralerencontrés lors de cette thèse, problèmes parmi lesquels figurent l’analyse en composantesindépendantes, la réduction non-linéaire de la dimension et la décompositiond’une image par rapport à une librairie regroupant un nombre important de spectresde référence. / This dissertation addresses hyperspectral image analysis, a set of techniques enabling exploitation of micro-spectroscopy images. Images produced by these sensors constitute cubic arrays, meaning that every pixel in the image is actually a spectrum.The size of these images, which is often quite large, calls for an upgrade for classical image analysis algorithms.We start out our investigation with clustering techniques. The main idea is to regroup every spectrum contained in a hyperspectralimage into homogeneous clusters. Spectrums taken across the image can indeed be generated by similar materials, and hence display spectral signatures resembling each other. Clustering is a commonly used method in data analysis. It belongs nonetheless to a class of particularly hard problems to solve, named NP-hard problems. The efficiency of a few heuristics used in practicewere poorly understood until recently. We give theoretical arguments guaranteeing success when the groups studied displaysome statistical property.We then study unmixing techniques. The objective is no longer to decide to which class a pixel belongs, but to understandeach pixel as a mix of basic signatures supposed to arise from pure materials. The mathematical underlying problem is again NP-hard.After studying its complexity, and suggesting two lengthy relaxations, we describe a more practical way to constrain the problemas to obtain regularized solutions.We finally give an overview of other hyperspectral image analysis methods encountered during this thesis, amongst whomare independent component analysis, non-linear dimension reduction, and regression against a spectrum library.

Pour l’auscultation d’ouvrages, les capteurs à fibre optique sont généralement utilisés puisqu’ils présentent l’avantage de fournir des mesures réparties. Plus particulièrement, le capteur basé sur la technologie Brillouin permet d’acquérir un profil de fréquence Brillouin, sensible à la température et la déformation dans une fibre optique sur une dizaine de kilomètres avec un pas de l’ordre de la dizaine de centimètres. La première problématique est d’obtenir un profil centimétrique sur la même longueur d’auscultation. Nous y répondons en s’appuyant sur des méthodes de séparation de sources, de déconvolution et de résolution de problèmes inverses. Ensuite, nous souhaitons estimer la déformation athermique dans l’ouvrage. Pour cela, plusieurs algorithmes de filtrage adaptatif sont comparés. Finalement, un procédé pour quantifier le déplacement de l’ouvrage à partir des mesures de déformation est proposé. Toutes ces méthodes sont testés sur des données simulées et réelles acquises dans des conditions contrôlées. / For structural health monitoring, optical fiber sensors are mostly used thanks their capacity to provide distributed measurements. Based on the principle of Brillouin scattering, optical fiber sensors measure Brillouin frequency profile, sensitive to strain and temperature into the optical fiber, with a meter spatial resolution over several kilometers. The first problem is to obtain a centimeter spatial resolution with the same sensing length. To solve it, source separation, deconvolution and resolution of inverse problem methodologies are used. Then, the athermal strain into the structure is searched. Several algorithms based on adaptative filter are tested to correct the thermal effect on strain measurements. Finally, several methods are developed to quantify structure displacements from the athermal strain measurements. They have been tested on simulated and controlled-conditions data

Hierarchical Bayesian Models and Matrix factorization methods provide an unsupervised way to learn latent components of data from the grouped or sequence data. For example, in document data, latent component corn-responds to topic with each topic as a distribution over a note vocabulary of words. For many applications, there exist sparse relationships between the domain entities and the latent components of the data. Traditional approaches for topic modelling do not take into account these sparsity considerations. Modelling these sparse relationships helps in extracting relevant information leading to improvements in topic accuracy and scalable solution. In our thesis, we explore these sparsity relationships for di errant applications such as text segmentation, topical analysis and entity resolution in dyadic data through the Bayesian and Matrix tri-factorization approaches, propos-in scalable solutions. In our rest work, we address the problem of segmentation of a collection of sequence data such as documents using probabilistic models. Existing state-of-the-art Hierarchical Bayesian Models are connected to the notion of Complete Exchangeability or Markov Exchangeability. Bayesian Nonpareil-metric Models based on the notion of Markov Exchangeability such as HDP-HMM and Sticky HDP-HMM, allow very restricted permutations of latent variables in grouped data (topics in documents), which in turn lead to com-mutational challenges for inference. At the other extreme, models based on Complete Exchangeability such as HDP allow arbitrary permutations within each group or document, and inference is significantly more tractable as a result, but segmentation is not meaningful using such models. To over-come these problems, we explored a new notion of exchangeability called Block Exchangeability that lies between Markov Exchangeability and Com-plate Exchangeability for which segmentation is meaningful, but inference is computationally less expensive than both Markov and Complete Exchange-ability. Parametrically, Block Exchangeability contains sparser number of transition parameters, linear in number of states compared to the quadratic order for Markov Exchangeability that is still less than that for Complete Exchangeability and for which parameters are on the order of the number of documents. For this, we propose a nonparametric Block Exchangeable model (BEM) based on the new notion of Block Exchangeability, which we have shown to be a superclass of Complete Exchangeability and subclass of Markov Exchangeability. We propose a scalable inference algorithm for BEM to infer the topics for words and segment boundaries associated with topics for a document using the collapsed Gibbs Sampling procedure. Empirical results show that BEM outperforms state-of-the-art nonparametric models in terms of scalability and generalization ability and shows nearly the same segmentation quality on News dataset, Product review dataset and on a Synthetic dataset. Interestingly, we can tune the scalability by varying the block size through a parameter in our model for a small trade-o with segmentation quality. In addition to exploring the association between documents and words, we also explore the sparse relationships for dyadic data, where associations between one pair of domain entities such as (documents, words) and as-associations between another pair such as (documents, users) are completely observed. We motivate the analysis of such dyadic data introducing an additional discrete dimension, which we call topics, and explore sparse relation-ships between the domain entities and the topic, such as of user-topic and document-topic respectively. In our second work, for this problem of sparse topical analysis of dyadic data, we propose a formulation using sparse matrix tri-factorization. This formulation requires sparsity constraints, not only on the individual factor matrices, but also on the product of two of the factors. To the best of our knowledge, this problem of sparse matrix tri-factorization has not been stud-ide before. We propose a solution that introduces a surrogate for the product of factors and enforces sparsity on this surrogate as well as on the individual factors through L1-regularization. The resulting optimization problem is e - cogently solvable in an alternating minimization framework over sub-problems involving individual factors using the well-known FISTA algorithm. For the sub-problems that are constrained, we use a projected variant of the FISTA algorithm. We also show that our formulation leads to independent sub-problems towards solving a factor matrix, thereby supporting parallel implementation leading to a scalable solution. We perform experiments over bibliographic and product review data to show that the proposed framework based on sparse tri-factorization formulation results in better generalization ability and factorization accuracy compared to baselines that use sparse bi-factorization. Even though the second work performs sparse topical analysis for dyadic data, ending sparse topical associations for the users, the user references with di errant names could belong to the same entity and those with same names could belong to different entities. The problem of entity resolution is widely studied in the research community, where the goal is to identify real users associated with the user references in the documents. Finally, we focus on the problem of entity resolution in dyadic data, where associations between one pair of domain entities such as documents-words and associations between another pair such as documents-users are ob.-served, an example of which includes bibliographic data. In our nil work, for this problem of entity resolution in bibliographic data, we propose a Bayesian nonparametric `Sparse entity resolution model' (SERM) exploring the sparse relationships between the grouped data involving grouping of the documents, and the topics/author entities in the group. Further, we also exploit the sparseness between an author entity and the associated author aliases. Grouping of the documents is achieved with the stick breaking prior for the Dirichlet processes (DP). To achieve sparseness, we propose a solution that introduces separate Indian Bu et process (IBP) priors over topics and the author entities for the groups and k-NN mechanism for selecting author aliases for the author entities. We propose a scalable inference for SERM by appropriately combining partially collapsed Gibbs sampling scheme in Focussed topic model (FTM), the inference scheme used for parametric IBP prior and the k-NN mechanism. We perform experiments over bibliographic datasets, Cite seer and Rexa, to show that the proposed SERM model imp-proves the accuracy of entity resolution by ending relevant author entities through modelling sparse relationships and is scalable, when compared to the state-of-the-art baseline

La complexité algorithmique est l'étude des ressources nécessaires — le temps, la mémoire, … — pour résoudre un problème de manière algorithmique. Dans ce cadre, la théorie de la complexité algébrique est l'étude de la complexité algorithmique de problèmes de nature algébrique, concernant des polynômes.Dans cette thèse, nous étudions différents aspects de la complexité algébrique. D'une part, nous nous intéressons à l'expressivité des déterminants de matrices comme représentations des polynômes dans le modèle de complexité de Valiant. Nous montrons que les matrices symétriques ont la même expressivité que les matrices quelconques dès que la caractéristique du corps est différente de deux, mais que ce n'est plus le cas en caractéristique deux. Nous construisons également la représentation la plus compacte connue du permanent par un déterminant. D'autre part, nous étudions la complexité algorithmique de problèmes algébriques. Nous montrons que la détection de racines dans un système de n polynômes homogènes à n variables est NP-difficile. En lien avec la question « VP = VNP ? », version algébrique de « P = NP ? », nous obtenons une borne inférieure pour le calcul du permanent d'une matrice par un circuit arithmétique, et nous exhibons des liens unissant ce problème et celui du test d'identité polynomiale. Enfin nous fournissons des algorithmes efficaces pour la factorisation des polynômes lacunaires à deux variables. / Computational complexity is the study of the resources — time, memory, …— needed to algorithmically solve a problem. Within these settings, algebraic complexity theory is the study of the computational complexity of problems of algebraic nature, concerning polynomials. In this thesis, we study several aspects of algebraic complexity. On the one hand, we are interested in the expressiveness of the determinants of matrices as representations of polynomials in Valiant's model of complexity. We show that symmetric matrices have the same expressiveness as the ordinary matrices as soon as the characteristic of the underlying field in different from two, but that this is not the case anymore in characteristic two. We also build the smallest known representation of the permanent by a determinant.On the other hand, we study the computational complexity of algebraic problems. We show that the detection of roots in a system of n homogeneous polynomials in n variables in NP-hard. In line with the “VP = VNP ?”question, which is the algebraic version of “P = NP?” we obtain a lower bound for the computation of the permanent of a matrix by an arithmetic circuit, and we point out the links between this problem and the polynomial identity testing problem. Finally, we give efficient algorithms for the factorization of lacunary bivariate polynomials.

The effective use of GPUs for accelerating applications depends on a number of factors including effective asynchronous use of heterogeneous resources, reducing data transfer between CPU and GPU, increasing occupancy of GPU kernels, overlapping data transfers with computations, reducing GPU idling and kernel optimizations. Overcoming these challenges require considerable effort on the part of the application developers. Most optimization strategies are often proposed and tuned specifically for individual applications. Message-driven executions with over-decomposition of tasks constitute an important model for parallel programming and provide multiple benefits including communication-computation overlap and reduced idling on resources. Charm++ is one such message-driven language which employs over decomposition of tasks, computation-communication overlap and a measurement-based load balancer to achieve high CPU utilization. This research has developed an adaptive runtime framework for efficient executions of Charm++ message-driven parallel applications on GPU systems. In the first part of our research, we have developed a runtime framework, G-Charm with the focus primarily on optimizing regular applications. At runtime, G-Charm automatically combines multiple small GPU tasks into a single larger kernel which reduces the number of kernel invocations while improving CUDA occupancy. G-Charm also enables reuse of existing data in GPU global memory, performs GPU memory management and dynamic scheduling of tasks across CPU and GPU in order to reduce idle time. In order to combine the partial results obtained from the computations performed on CPU and GPU, G-Charm allows the user to specify an operator using which the partial results are combined at runtime. We also perform compile time code generation to reduce programming overhead. For Cholesky factorization, a regular parallel application, G-Charm provides 14% improvement over a highly tuned implementation. In the second part of our research, we extended our runtime to overcome the challenges presented by irregular applications such as a periodic generation of tasks, irregular memory access patterns and varying workloads during application execution. We developed models for deciding the number of tasks that can be combined into a kernel based on the rate of task generation, and the GPU occupancy of the tasks. For irregular applications, data reuse results in uncoalesced GPU memory access. We evaluated the effect of altering the global memory access pattern in improving coalesced access. We’ve also developed adaptive methods for hybrid execution on CPU and GPU wherein we consider the varying workloads while scheduling tasks across the CPU and GPU. We demonstrate that our dynamic strategies result in 8-38% reduction in execution times for an N-body simulation application and a molecular dynamics application over the corresponding static strategies that are amenable for regular applications.