The hierarchical (<i>H-</i>) matrix format allows storing a variety of dense matrices from certain applications in a special data-sparse way with linear-polylogarithmic complexity. Many operations from linear algebra like matrix-matrix and matrix-vector products, matrix inversion and LU decomposition can be implemented efficiently using the <i>H</i>-matrix format. Due to its importance in solving many problems in numerical linear algebra like least-squares problems, it is also desirable to have an efficient QR decomposition of <i>H</i>-matrices. In the past, two different approaches for this task have been suggested. We will review the resulting methods and suggest a new algorithm to compute the QR decomposition of an <i>H</i>-matrix. Like other <i>H</i>-arithmetic operations the <i>H</i>QR decomposition is of linear-polylogarithmic complexity. We will compare our new algorithm with the older ones by using two series of test examples and discuss benefits and drawbacks of the new approach.

Dans cette thèse, nous étudions comment les méthodes d'apprentissage de représentations peuvent être appliquées à des données générées par l'utilisateur. Nos contributions couvrent trois applications différentes, mais partagent un dénominateur commun: l'extraction des représentations d'utilisateurs concernés. Notre première application est la tâche de recommandation de produits, où les systèmes existant créent des profils utilisateurs et objets qui reflètent les préférences des premiers et les caractéristiques des derniers, en utilisant l'historique. De nos jours, un texte accompagne souvent cette note et nous proposons de l'utiliser pour enrichir les profils extraits. Notre espoir est d'en extraire une connaissance plus fine des goûts des utilisateurs. Nous pouvons, en utilisant ces modèles, prédire le texte qu'un utilisateur va écrire sur un objet. Notre deuxième application est l'analyse des sentiments et, en particulier, la classification de polarité. Notre idée est que les systèmes de recommandation peuvent être utilisés pour une telle tâche. Les systèmes de recommandation et classificateurs de polarité traditionnels fonctionnent sur différentes échelles de temps. Nous proposons deux hybridations de ces modèles: la première a de meilleures performances en classification, la seconde exhibe un vocabulaire de surprise. La troisième et dernière application que nous considérons est la mobilité urbaine. Elle a lieu au-delà des frontières d'Internet, dans le monde physique. Nous utilisons les journaux d'authentification des usagers du métro, enregistrant l'heure et la station d'origine des trajets, pour caractériser les utilisateurs par ses usages et habitudes temporelles. / In this thesis, we study how representation learning methods can be applied to user-generated data. Our contributions cover three different applications but share a common denominator: the extraction of relevant user representations. Our first application is the item recommendation task, where recommender systems build user and item profiles out of past ratings reflecting user preferences and item characteristics. Nowadays, textual information is often together with ratings available and we propose to use it to enrich the profiles extracted from the ratings. Our hope is to extract from the textual content shared opinions and preferences. The models we propose provide another opportunity: predicting the text a user would write on an item. Our second application is sentiment analysis and, in particular, polarity classification. Our idea is that recommender systems can be used for such a task. Recommender systems and traditional polarity classifiers operate on different time scales. We propose two hybridizations of these models: the former has better classification performance, the latter highlights a vocabulary of surprise in the texts of the reviews. The third and final application we consider is urban mobility. It takes place beyond the frontiers of the Internet, in the physical world. Using authentication logs of the subway users, logging the time and station at which users take the subway, we show that it is possible to extract robust temporal profiles.

In the paper [HSS] Herrlich, Salicrup and Strecker were able to show that Kuratowski / Mrowka's Theorem concerning compactness for topological spaces could be applied to a wider setting. In this dissertation, which is based on the paper [F subscript 1], we interpret Kuratowski / Mrowka's result in the category R-Mod. Chapter One deals mainly with the preliminary definitions and results and we also show that there is a 1-1 correspondence between torsion theories and standard factorisation systems. In Chapter Two we, obtain for every torsion theory T, a theory of T-compactness which is an extension of the definition of compactness found in [HSS]. We then obtain a characterisation of T-compactness under certain conditions on the ring R and torsion theory T. In Chapter Three we examine the class of T-compact R-modules more closely when the ring R is T-hereditary and T-noetherian. We also obtain further characterisation of T-compactness under these additional conditions. In Chapter Four we show that many topological results have analogues in R-Mod. / Mathematical Sciences / M. Sc. (Mathematics)

L'objet de cette thèse est d'établir des théorèmes limites locaux pour des marches aléatoires réfléchies sur N. La théorie des fluctuations des marches aléatoires et la factorisation de Wiener-Hopf y jouent un rôle important. On développera dans la première partie une approche classique que l'on appliquera à l'étude des marches aléatoires sur R+ avec réflexions non élastiques en 0. Dans la deuxième partie, on explicitera une méthode différente qui fait intervenir des outils algébriques, d'analyse complexe et des techniques de factorisation utilisant de manière essentielle les fonctions génératrices. Cette approche a été développée il y a une cinquantaine d'année pour l'étude de marches de Markov, elle sera présentée dans cette partie dans le cas des marches aléatoires à pas i.i.d. où un certain nombre de simplifications apparaissent et sera ensuite utilisée pour étudier les marches aléatoires sur N avec réflexions élastiques ou non élastiques en zéro. Finalement, dans la dernière partie, nous mettons en place les outils nécessaires pour établir une factorisation de Wiener-Hopf dans un cadre markovien afin d'étudier les fluctuations des marches de Markov sur Z ; nous reprenons des travaux anciens dont les démonstrations méritaient d'être détaillées, l'objectif à moyen terme étant d'appliquer les méthodes algébriques décrites ci-dessus pour l'étude de marches de Markov réfléchies sur N.

In the past two decades, there has been huge amount of interest in Multiresolution Analysis Algorithms (MAAs) and their applications. Processing some of their applications such as medical imaging are computationally intensive, power hungry and requires large amount of memory which cause a high demand for efficient algorithm implementation, low power architecture and acceleration. Recently, some MAAs such as Finite Ridgelet Transform (FRIT) Haar Wavelet Transform (HWT) are became very popular and they are suitable for a number of image processing applications such as detection of line singularities and contiguous edges, edge detection (useful for compression and feature detection), medical image denoising and segmentation. Efficient hardware implementation and acceleration of these algorithms particularly when addressing large problems are becoming very chal-lenging and consume lot of power which leads to a number of issues including mobility, reliability concerns. To overcome the computation problems, Field Programmable Gate Arrays (FPGAs) are the technology of choice for accelerating computationally intensive applications due to their high performance. Addressing the power issue requires optimi- sation and awareness at all level of abstractions in the design flow. The most important achievements of the work presented in this thesis are summarised here. Two factorisation methodologies for HWT which are called HWT Factorisation Method1 and (HWTFM1) and HWT Factorasation Method2 (HWTFM2) have been explored to increase number of zeros and reduce hardware resources. In addition, two novel efficient and optimised architectures for proposed methodologies based on Distributed Arithmetic (DA) principles have been proposed. The evaluation of the architectural results have shown that the proposed architectures results have reduced the arithmetics calculation (additions/subtractions) by 33% and 25% respectively compared to direct implementa-tion of HWT and outperformed existing results in place. The proposed HWTFM2 is implemented on advanced and low power FPGA devices using Handel-C language. The FPGAs implementation results have outperformed other existing results in terms of area and maximum frequency. In addition, a novel efficient architecture for Finite Radon Trans-form (FRAT) has also been proposed. The proposed architecture is integrated with the developed HWT architecture to build an optimised architecture for FRIT. Strategies such as parallelism and pipelining have been deployed at the architectural level for efficient im-plementation on different FPGA devices. The proposed FRIT architecture performance has been evaluated and the results outperformed some other existing architecture in place. Both FRAT and FRIT architectures have been implemented on FPGAs using Handel-C language. The evaluation of both architectures have shown that the obtained results out-performed existing results in place by almost 10% in terms of frequency and area. The proposed architectures are also applied on image data (256 £ 256) and their Peak Signal to Noise Ratio (PSNR) is evaluated for quality purposes. Two architectures for cyclic convolution based on systolic array using parallelism and pipelining which can be used as the main building block for the proposed FRIT architec-ture have been proposed. The first proposed architecture is a linear systolic array with pipelining process and the second architecture is a systolic array with parallel process. The second architecture reduces the number of registers by 42% compare to first architec-ture and both architectures outperformed other existing results in place. The proposed pipelined architecture has been implemented on different FPGA devices with vector size (N) 4,8,16,32 and word-length (W=8). The implementation results have shown a signifi-cant improvement and outperformed other existing results in place. Ultimately, an in-depth evaluation of a high level power macromodelling technique for design space exploration and characterisation of custom IP cores for FPGAs, called func-tional level power modelling approach have been presented. The mathematical techniques that form the basis of the proposed power modeling has been validated by a range of custom IP cores. The proposed power modelling is scalable, platform independent and compares favorably with existing approaches. A hybrid, top-down design flow paradigm integrating functional level power modelling with commercially available design tools for systematic optimisation of IP cores has also been developed. The in-depth evaluation of this tool enables us to observe the behavior of different custom IP cores in terms of power consumption and accuracy using different design methodologies and arithmetic techniques on virous FPGA platforms. Based on the results achieved, the proposed model accuracy is almost 99% true for all IP core's Dynamic Power (DP) components.

Les processeurs multi-cœurs sont considérés de nos jours comme l'avenir des calculateurs et auront un impact important dans le calcul scientifique. Cette thèse présente une nouvelle approche de résolution des grands systèmes linéaires creux et denses, qui soit adaptée à l'exécution sur les futurs machines pétaflopiques et en particulier celles ayant un nombre important de cœurs. Compte tenu du coût croissant des communications comparé au temps dont les processeurs mettent pour effectuer les opérations arithmétiques, notre approche adopte le principe de minimisation des communications au prix de quelques calculs redondants et utilise plusieurs adaptations pour atteindre de meilleures performances sur les machines multi-cœurs. Nous décomposons le problème à résoudre en plusieurs phases qui sont ensuite mises en œuvre séparément. Dans la première partie, nous présentons un algorithme basé sur le partitionnement d'hypergraphe qui réduit considérablement le remplissage ("fill-in") induit lors de la factorisation LU des matrices creuses non symétriques. Dans la deuxième partie, nous présentons deux algorithmes de réduction de communication pour les factorisations LU et QR qui sont adaptés aux environnements multi-cœurs. La principale contribution de cette partie est de réorganiser les opérations de la factorisation de manière à réduire la sollicitation du bus tout en utilisant de façon optimale les ressources. Nous étendons ensuite ce travail aux clusters de processeurs multi-cœurs. Dans la troisième partie, nous présentons une nouvelle approche d'ordonnancement et d'optimisation. La localité des données et l'équilibrage des charges représentent un sérieux compromis pour le choix des méthodes d'ordonnancement. Sur les machines NUMA par exemple où la localité des données n'est pas une option, nous avons observé qu'en présence de perturbations systèmes (" OS noise"), les performances pouvaient rapidement se dégrader et devenir difficiles à prédire. Pour cela, nous présentons une approche combinant un ordonnancement statique et dynamique pour ordonnancer les tâches de nos algorithmes. Nos résultats obtenues sur plusieurs architectures montrent que tous nos algorithmes sont efficaces et conduisent à des gains de performances significatifs. Nous pouvons atteindre des améliorations de l'ordre de 30 à 110% par rapport aux correspondants de nos algorithmes dans les bibliothèques numériques bien connues de la littérature. / Multicore processors are considered to be nowadays the future of computing, and they will have an important impact in scientific computing. In this thesis, we study methods and algorithms for solving efficiently sparse and dense large linear systems on future petascale machines and in particular these having a significant number of cores. Due to the increasing communication cost compared to the time the processors take to perform arithmetic operations, our approach embrace the communication avoiding algorithm principle by doing some redundant computations and uses several adaptations to achieve better performance on multicore machines.We decompose the problem to solve into several phases that would be then designed or optimized separately. In the first part, we present an algorithm based on hypergraph partitioning and which considerably reduces the fill-in incurred in the LU factorization of sparse unsymmetric matrices. In the second part, we present two communication avoiding algorithms that are adapted to multicore environments. The main contribution of this part is to reorganize the computations such as to reduce bus contention and using efficiently resources. Then, we extend this work for clusters of multi-core processors. In the third part, we present a new scheduling and optimization approach. Data locality and load balancing are a serious trade-off in the choice of the scheduling strategy. On NUMA machines for example, where the data locality is not an option, we have observed that in the presence of noise, performance could quickly deteriorate and become difficult to predict. To overcome this bottleneck, we present an approach that combines a static and a dynamic scheduling approach to schedule the tasks of our algorithms.Our results obtained on several architectures show that all our algorithms are efficient and lead to significant performance gains. We can achieve from 30 up to 110% improvement over the corresponding routines of our algorithms in well known libraries.

L'objectif de ce travail était de tester des méthodes de SAS pour la séparation des spectres complexes RMN de mélanges dans les plus simples des composés purs. Dans une première partie, les méthodes à savoir JADE et NNSC ont été appliqué es dans le cadre de la DOSY , une application aux données CPMG était démontrée. Dans une deuxième partie, on s'est concentré sur le développement d'un algorithme efficace "beta-SNMF" . Ceci s'est montré plus performant que NNSC pour beta inférieure ou égale à 2. Etant donné que dans la littérature, le choix de beta a été adapté aux hypothèses statistiques sur le bruit additif, une étude statistique du bruit RMN de la DOSY a été faite pour obtenir une image plus complète de nos données RMN étudiées. / The objective of the work was to test BSS methods for the separation of the complex NMR spectra of mixtures into the simpler ones of the pure compounds. In a first part, known methods namely JADE and NNSC were applied in conjunction for DOSY , performing applications for CPMG were demonstrated. In a second part, we focused on developing an effective algorithm "beta- SNMF ". This was demonstrated to outperform NNSC for beta less or equal to 2. Since in the literature, the choice of beta has been adapted to the statistical assumptions on the additive noise, a statistical study of NMR DOSY noise was done to get a more complete picture about our studied NMR data.

Dans la limite des hautes énergies, la petite valeur de la constante de couplage de l'interaction forte peut être compensée par l'apparition de grands logarithmes de l'énergie dans le centre de masse. Toutes ces contributions peuvent être du même ordre de grandeur et sont resommées par l'équation de Balitsky-Fadin-Kuraev-Lipatov (BFKL). De nombreux processus ont été proposés pour étudier cette dynamique. L'un des plus prometteurs, proposé par Mueller et Navelet, est l'étude de la production de deux jets vers l'avant séparés par un grand intervalle en rapidité dans les collisions de hadrons. Un calcul BFKL ne prenant en compte que les termes dominants (approximation des logarithmes dominants ou LL) prédit une augmentation rapide de la section efficace avec l'augmentation de l'intervalle en rapidité entre les jets ainsi qu'une faible corrélation angulaire. Cependant, des calculs basés sur cette approximation ne purent pas décrire correctement les mesures expérimentales de ces observables au Tevatron. Dans cette thèse, nous étudions ce processus à l'ordre des logarithmes sous-dominants, ou NLL, en prenant en compte les corrections NLL aux facteurs d'impact, qui décrivent la transition d'un hadron initial vers un jet, et à la fonction de Green, qui décrit le couplage entre les facteurs d'impact. Nous étudions l'importance de ces corrections NLL et trouvons qu'elles sont très importantes, ce qui conduit à des résultats très différents de ceux obtenus à l'ordre des logarithmes dominants. De plus, ces résultats dépendent fortement du choix des échelles présentes dans ce processus. Nous comparons nos résultats avec des données récentes de la collaboration CMS sur les corrélations angulaires des jets Mueller-Navelet au LHC et ne trouvons pas un bon accord. Nous montrons que cela peut être corrigé en utilisant la procédure de Brodsky-Lepage-Mackenzie pour fixer le choix de l'échelle de renormalisation. Cela conduit à des résultats plus stables et une très bonne description des données de CMS. Finalement, nous montrons que, à l'ordre des logarithmes sous-dominants, l'absence de conservation stricte de l'énergie-impulsion (qui est un effet négligé dans un calcul BFKL) devrait être un problème beaucoup moins important qu'à l'ordre des logarithmes dominants. / In the high energy limit of QCD, the smallness of the strong coupling due to the presence of a hard scale can be compensated by large logarithms of the center of mass energy. All these logarithmically-enhanced contributions can be resummed by the Balitsky-Fadin-Kuraev-Lipatov (BFKL) equation. Many processes have been proposed to study these dynamics. Among the most promising ones is the production of two forward jets separated by a large interval of rapidity at hadron colliders, proposed by Mueller and Navelet. A BFKL calculation taking into account only dominant contributions (leading logarithmic, or LL, accuracy) predicts a strong rise of the cross section with increasing rapidity separation between the jets and a large decorrelation of their azimuthal angles. However, such LL calculations could not successfully describe measurements of these observables performed at the Tevatron. In this thesis, we study this process at next-to-leading logarithmic (NLL) accuracy, taking into account NLL corrections both to the impact factors, which describe the transition from an incoming hadron to a jet, and to the Green's function, which describes the coupling between the impact factors. We investigate the magnitude of these NLL corrections and find that they are very large, leading to very different results compared with a LL calculation. In addition, we find that these results are very dependent on the choice of the scales involved in the process. We compare our results with recent data from the CMS collaboration on the azimuthal correlations of Mueller-Navelet jets at the LHC and find a rather poor agreement. We show that this can be cured by using the Brodsky-Lepage-Mackenzie procedure to fix the renormalization scale. This leads to more stable results and a very good description of CMS data. Finally, we show that at NLL accuracy the absence of strict energy-momentum conservation (which is a subleading effect in a BFKL calculation) should be a much less severe issue than at LL accuracy.

Nous considérons deux classes de systèmes fractionnaires linéaires invariants dans le temps avec des ordres commensurables et des retards discrets. La première est composée de systèmes fractionnaires à entrées multiples et à une sortie avec des retards en entrées ou en sortie. La seconde se compose de systèmes fractionnaires de type neutre avec retards commensurables. Nous étudions la stabilisation de la première classe de systèmes à l'aide de l'approche de factorisation. Nous obtenons des factorisations copremières à gauche et à droite et les facteurs de Bézout associés: ils permettent de constituer l'ensemble des contrôleurs stabilisants. Pour la deuxième classe de systèmes, nous nous sommes intéressés au cas critique où certaines chaînes de pôles sont asymptotiques à l'axe imaginaire. Tout d'abord, nous réalisons une approximation des pôles asymptotiques afin de déterminer leur emplacement par rapport à l'axe. Le cas échéant, des conditions nécessaires et suffisantes de stabilité H-infini sont données. Cette analyse de stabilité est ensuite étendue aux systèmes à retard classiques ayant la même forme. Enfin, nous proposons une approche unifiée pour les deux classes de systèmes à retards commensurables de type neutre (standards et fractionnaires). Ensuite, la stabilisation d'une sous-classe de systèmes neutres fractionnaires est étudiée. Premièrement, l'ensemble de tous les contrôleurs stabilisants est obtenu. Deuxièmement, nous prouvons que pour une grande classe de contrôleurs fractionnaires à retards il est impossible d'éliminer dans la boucle fermée les chaînes de pôles asymptotiques à l'axe imaginaire si de telles chaînes sont présentes dans les systèmes à contrôler. / We consider two classes of linear time-invariant fractional systems with commensurate orders and discrete delays. The first one consists of multi-input single-output fractional systems with output or input delays. The second one consists of single-input single-output fractional neutral systems with commensurate delays. We study the stabilization of the first class of systems using the factorization approach. We derive left and right coprime factorizations and Bézout factors, which are the elements to constitute the set of all stabilizing controllers. For the second class of systems, we are interested in the critical case where some chains of poles are asymptotic to the imaginary axis. First, we approximate asymptotic poles in order to determine their location relative to the axis. Then, when appropriate, necessary and sufficient conditions for H-infinity-stability are derived. This stability analysis is then extended to classical delay systems of the same form and finally a unified approach for both classes of neutral delay systems with commensurate delays (standard and fractional) is proposed. Next, the stabilization of a subclass of fractional neutral systems is studied. First, the set of all stabilizing controllers is derived. Second, we prove that a large class of fractional controllers with delays cannot eliminate in the closed loop chains of poles asymptotic to the imaginary axis if such chains are present in the controlled systems.

Dans cette thèse, nous nous concentrons sur le développement des méthodes d'optimisation pour résoudre certaines classes de problèmes d'apprentissage avec la parcimonie et/ou avec l'incertitude des données. Nos méthodes sont basées sur la programmation DC (Difference of Convex functions) et DCA (DC Algorithms) étant reconnues comme des outils puissants d'optimisation. La thèse se compose de deux parties : La première partie concerne la parcimonie tandis que la deuxième partie traite l'incertitude des données. Dans la première partie, une étude approfondie pour la minimisation de la norme zéro a été réalisée tant sur le plan théorique qu'algorithmique. Nous considérons une approximation DC commune de la norme zéro et développons quatre algorithmes basées sur la programmation DC et DCA pour résoudre le problème approché. Nous prouvons que nos algorithmes couvrent tous les algorithmes standards existants dans le domaine. Ensuite, nous étudions le problème de la factorisation en matrices non-négatives (NMF) et fournissons des algorithmes appropriés basés sur la programmation DC et DCA. Nous étudions également le problème de NMF parcimonieuse. Poursuivant cette étude, nous étudions le problème d'apprentissage de dictionnaire où la représentation parcimonieuse joue un rôle crucial. Dans la deuxième partie, nous exploitons la technique d'optimisation robuste pour traiter l'incertitude des données pour les deux problèmes importants dans l'apprentissage : la sélection de variables dans SVM (Support Vector Machines) et le clustering. Différents modèles d'incertitude sont étudiés. Les algorithmes basés sur DCA sont développés pour résoudre ces problèmes. / In this thesis, we focus on developing optimization approaches for solving some classes of optimization problems in sparsity and robust optimization for data uncertainty. Our methods are based on DC (Difference of Convex functions) programming and DCA (DC Algorithms) which are well-known as powerful tools in optimization. This thesis is composed of two parts: the first part concerns with sparsity while the second part deals with uncertainty. In the first part, a unified DC approximation approach to optimization problem involving the zero-norm in objective is thoroughly studied on both theoretical and computational aspects. We consider a common DC approximation of zero-norm that includes all standard sparse inducing penalty functions, and develop general DCA schemes that cover all standard algorithms in the field. Next, the thesis turns to the nonnegative matrix factorization (NMF) problem. We investigate the structure of the considered problem and provide appropriate DCA based algorithms. To enhance the performance of NMF, the sparse NMF formulations are proposed. Continuing this topic, we study the dictionary learning problem where sparse representation plays a crucial role. In the second part, we exploit robust optimization technique to deal with data uncertainty for two important problems in machine learning: feature selection in linear Support Vector Machines and clustering. In this context, individual data point is uncertain but varies in a bounded uncertainty set. Different models (box/spherical/ellipsoidal) related to uncertain data are studied. DCA based algorithms are developed to solve the robust problems