Academic literature on the topic 'Approximations par matrices faible rang'

Cette étude évalue le potentiel des modèles de texture SIRV sur ondelettes pour la détection de parcelles viticoles dans les images à très haute résolution de type PLEIADES et compare les performances de ces modèles avec des méthodes de référence telles que les matrices de co-occurrence de niveaux de gris et une approche de segmentation par filtre de Gabor. Les résultats obtenus montrent que les modèles SIRV permettent à la fois une bonne détection des parcelles tout en limitant le taux de faux positifs par rapport aux autres approches. Ces modèles font également preuve d'une plus grande robustesse à des effets d'atténuation de texture liés au faible rapport entre distance inter-rang et résolution spatiale propre aux appellations viticoles étudiées.

International audience Connection matrices for graph parameters with values in a field have been introduced by M. Freedman, L. Lovász and A. Schrijver (2007). Graph parameters with connection matrices of finite rank can be computed in polynomial time on graph classes of bounded tree-width. We introduce join matrices, a generalization of connection matrices, and allow graph parameters to take values in the tropical rings (max-plus algebras) over the real numbers. We show that rank-finiteness of join matrices implies that these graph parameters can be computed in polynomial time on graph classes of bounded clique-width. In the case of graph parameters with values in arbitrary commutative semirings, this remains true for graph classes of bounded linear clique-width. B. Godlin, T. Kotek and J.A. Makowsky (2008) showed that definability of a graph parameter in Monadic Second Order Logic implies rank finiteness. We also show that there are uncountably many integer valued graph parameters with connection matrices or join matricesof fixed finite rank. This shows that rank finiteness is a much weaker assumption than any definability assumption. Les matrices de connexion pour des fonctions sur les graphes à valeurs dans un corps ont été introduites par M. Freedman, L. Lovász and A. Schrijver (2007). Une fonctions sur les graphes ayant des matrices de connexion de rang fini peut être calculée en temps polynomial sur toute famille de graphes de largeur arborescente (”tree-width”) bornée. Nous introduisons des matrices de jointure (”join matrices”) qui généralisent les matrices deconnexion, et nous permettons aux fonctions sur les graphes de prendre leurs valeurs dans des semianneaux tropicaux réels. Nous montrons qu’une fonction sur les graphes ayant des matrices de jointure de rang fini peut être calculée en temps polynomial sur des graphes de largeur de clique (”clique-width”) bornée. Dans le cas des semi-anneaux commutatifs, cela reste vrai pour les graphes de largeur de clique linéaire bornée. B. Godlin, T. Kotek and J.A. Makowsky (2008) ont montré que certaines hypothèses de definissabilité en Logique du Second Ordre Monadique concernant desopérations sur les graphes entraine la finitude des rangs. Nous exhibons un ensemble non dénombrable d’opérations ayant une matrice de connexion et des matrices de jointure de rang fini. Cela démontre que l’hypothèse de rang fini est beaucoup plus faible que l’hypothèse de definissabilité.

Nous considérons la résolution de très grands systèmes linéaires creux à l'aide d'une méthode de factorisation directe appelée méthode multifrontale. Bien que numériquement robustes et faciles à utiliser (elles ne nécessitent que des informations algébriques : la matrice d'entrée A et le second membre b, même si elles peuvent exploiter des stratégies de prétraitement basées sur des informations géométriques), les méthodes directes sont très coûteuses en termes de mémoire et d'opérations, ce qui limite leur applicabilité à des problèmes de taille raisonnable (quelques millions d'équations). Cette étude se concentre sur l'exploitation des approximations de rang-faible dans la méthode multifrontale, pour réduire sa consommation mémoire et son volume d'opérations, dans des environnements séquentiel et à mémoire distribuée, sur une large classe de problèmes. D'abord, nous examinons les formats rang-faible qui ont déjà été développé pour représenter efficacement les matrices denses et qui ont été utilisées pour concevoir des solveur rapides pour les équations aux dérivées partielles, les équations intégrales et les problèmes aux valeurs propres. Ces formats sont hiérarchiques (les formats H et HSS sont les plus répandus) et il a été prouvé, en théorie et en pratique, qu'ils permettent de réduire substantiellement les besoins en mémoire et opération des calculs d'algèbre linéaire. Cependant, de nombreuses contraintes structurelles sont imposées sur les problèmes visés, ce qui peut limiter leur efficacité et leur applicabilité aux solveurs multifrontaux généraux. Nous proposons un format plat appelé Block Rang-Faible (BRF) basé sur un découpage naturel de la matrice en blocs et expliquons pourquoi il fournit toute la flexibilité nécéssaire à son utilisation dans un solveur multifrontal général, en terme de pivotage numérique et de parallélisme. Nous comparons le format BRF avec les autres et montrons que le format BRF ne compromet que peu les améliorations en mémoire et opération obtenues grâce aux approximations rang-faible. Une étude de stabilité montre que les approximations sont bien contrôlées par un paramètre numérique explicite appelé le seuil rang-faible, ce qui est critique dans l'optique de résoudre des systèmes linéaires creux avec précision. Ensuite, nous expliquons comment les factorisations exploitant le format BRF peuvent être efficacement implémentées dans les solveurs multifrontaux. Nous proposons plusieurs algorithmes de factorisation BRF, ce qui permet d'atteindre différents objectifs. Les algorithmes proposés ont été implémentés dans le solveur multifrontal MUMPS. Nous présentons tout d'abord des expériences effectuées avec des équations aux dérivées partielles standardes pour analyser les principales propriétés des algorithms BRF et montrer le potentiel et la flexibilité de l'approche ; une comparaison avec un code basé sur le format HSS est également fournie. Ensuite, nous expérimentons le format BRF sur des problèmes variés et de grande taille (jusqu'à une centaine de millions d'inconnues), provenant de nombreuses applications industrielles. Pour finir, nous illustrons l'utilisation de notre approche en tant que préconditionneur pour la méthode du Gradient Conjugué.

Dans cette thèse, nous considérons des images captées par une caméra multispectrale (MS) miniaturisée « snapshot ». Contrairement aux caméras RVB classiques, l’imagerie MS permet d’observer une scène sur des dizaines de longueurs d’onde différentes, permettant une analyse beaucoup plus précise du contenu observé. Alors que la plupart des caméras MS nécessitent un scan pour générer une image, les caméras MS snapshot peuvent fournir instantanément des images, voire des vidéos. Lorsque la caméra est miniaturisée, au lieu d’un cube de données 3D, elle fournit une image 2D, chaque pixel étant associé à une version filtrée du spectre théorique sensé être acquis. Un post-traitement, appelé «dématriçage », est alors nécessaire pour reconstruire le cube de données. De plus, dans chaque pixel de l’image, le spectre observé peut être considéré comme un mélange de spectres de matériaux purs présents dans le pixel. L’estimation de ces spectres nommés endmembers ainsi que leur distribution spatiale (appelée abondances) est appelée « démélange ». Alors qu’un pipeline classique pour traiter les images MS snapshot consiste d’abord à dématricer puis à démélanger les données, les travaux présentés dans cette thèse explorent des stratégies alternatives dans lesquelles le dématriçage et le démélange sont effectués conjointement. En étendant les hypothèsesclassiques rencontrées dans l’analyse des composantes parcimonieuses et dans le démélange MS utilisé en télédétection, nous proposons deux cadres différents pour restaurer et démélanger la scène acquise, basés respectivement sur la complétion de matrice de faible rang et la déconvolution, cette dernière étant spécifiquement conçue pour les filtres Fabry-Pérot utilisés dans la caméra considérée. Les quatre méthodes proposées présentent une bien meilleure qualité de démélange que les variantes qu’elles étendent lorsque ces dernières sont appliquées à des données dématricées. Néanmoins, elles permettent des performances de dématriçage similaires à celles des méthodes de l’état de l’art. La dernière partie de cette thèse introduit une approche de déconvolution pour restaurer les spectres de telles caméras. Notre contribution réside dans les poids du terme de pénalisation qui sont automatiquement fixés en utilisant l’entropie des harmoniques de Fabry-Pérot. La méthode proposéeprésente une meilleure restauration spectrale que la stratégie proposée par le fabricant de la caméra et que la technique de déconvolution classique qu’elle étend
In this thesis, we consider images sensed by a miniaturized multispectral (MS) snapshot camera. Contrary to classical RGB cameras, MS imaging allows to observe a scene on tens of different wavelengths, allowing a much more precise analysis of the observed content. While most MS cameras require a scan to generate an image, snapshot MS cameras can instantaneouslyprovide images, or even videos. When the camera is miniaturized, instead of a 3D data cube, it gets a 2D image, each pixel being associated with a filtered version of the theoretical spectrum it should acquire. Post-processing, called “demosaicing”, is then necessary to reconstruct a data cube. Furthermore, in each pixel of the image, the observed spectrum can be considered as a mixture of spectra of pure materials present in the pixel. Estimating these spectra named endmembers as well as their spatial distribution (named abundances) is called “unmixing”. While a classical pipeline to process MS snapshot images is to first demosaice and then unmix the data, the work introduced in this thesis explores alternative strategies in which demosaicing and unmixing are jointly performed. Extending classical assumptions met in sparse component analysis and in remote sensing MS unmixing, we propose two different frameworks to restore and unmixing the acquired scene, based on low-rank matrix completion and deconvolution, respectively, the latter being specifically designed for Fabry-Perot filters used in the considered camera. The four proposed methods exhibit a far better unmixing enhancement than the variants they extend when the latter are applied to demosaiced data. Still, they allow a similar demosaicing performance as state-of-the-art methods. The last part of this thesis introduces a deconvolution approach to restore the spectra of such cameras. Our contribution lies in the weights of the penalization term which are automatically set using the entropy of the Fabry-Perot harmonics. The proposed method exhibits a better spectrum restoration than the strategy proposed by the camera manufacturer and than the classical deconvolution technique it extends

Nous nous intéressons à l'utilisation d'approximations de rang faible pour réduire le coût des solveurs creux directs multifrontaux. Parmi les différents formats matriciels qui ont été proposés pour exploiter la propriété de rang faible dans les solveurs multifrontaux, nous nous concentrons sur le format Block Low-Rank (BLR) dont la simplicité et la flexibilité permettent de l'utiliser facilement dans un solveur multifrontal algébrique et généraliste. Nous présentons différentes variantes de la factorisation BLR, selon comment les mises à jour de rang faible sont effectuées, et comment le pivotage numérique est géré. D'abord, nous étudions la complexité théorique du format BLR qui, contrairement à d'autres formats comme les formats hiérarchiques, était inconnue jusqu'à présent. Nous prouvons que la complexité théorique de la factorisation multifrontale BLR est asymptotiquement inférieure à celle du solveur de rang plein. Nous montrons ensuite comment les variantes BLR peuvent encore réduire cette complexité. Nous étayons nos bornes de complexité par une étude expérimentale. Après avoir montré que les solveurs multifrontaux BLR peuvent atteindre une faible complexité, nous nous intéressons au problème de la convertir en gains de performance réels sur les architectures modernes. Nous présentons d'abord une factorisation BLR multithreadée, et analysons sa performance dans des environnements multicœurs à mémoire partagée. Nous montrons que les variantes BLR sont cruciales pour exploiter efficacement les machines multicœurs en améliorant l'intensité arithmétique et la scalabilité de la factorisation. Nous considérons ensuite à la factorisation BLR sur des architectures à mémoire distribuée. Les algorithmes présentés dans cette thèse ont été implémentés dans le solveur MUMPS. Nous illustrons l'utilisation de notre approche dans trois applications industrielles provenant des géosciences et de la mécanique des structures. Nous comparons également notre solveur avec STRUMPACK, basé sur des approximations Hierarchically Semi-Separable. Nous concluons cette thèse en rapportant un résultat sur un problème de très grande taille (130 millions d'inconnues) qui illustre les futurs défis posés par le passage à l'échelle des solveurs multifrontaux BLR
We investigate the use of low-rank approximations to reduce the cost of sparse direct multifrontal solvers. Among the different matrix representations that have been proposed to exploit the low-rank property within multifrontal solvers, we focus on the Block Low-Rank (BLR) format whose simplicity and flexibility make it easy to use in a general purpose, algebraic multifrontal solver. We present different variants of the BLR factorization, depending on how the low-rank updates are performed and on the constraints to handle numerical pivoting. We first investigate the theoretical complexity of the BLR format which, unlike other formats such as hierarchical ones, was previously unknown. We prove that the theoretical complexity of the BLR multifrontal factorization is asymptotically lower than that of the full-rank solver. We then show how the BLR variants can further reduce that complexity. We provide an experimental study with numerical results to support our complexity bounds. After proving that BLR multifrontal solvers can achieve a low complexity, we turn to the problem of translating that low complexity in actual performance gains on modern architectures. We first present a multithreaded BLR factorization, and analyze its performance in shared-memory multicore environments on a large set of real-life problems. We put forward several algorithmic properties of the BLR variants necessary to efficiently exploit multicore systems by improving the arithmetic intensity and the scalability of the BLR factorization. We then move on to the distributed-memory BLR factorization, for which additional challenges are identified and addressed. The algorithms presented throughout this thesis have been implemented within the MUMPS solver. We illustrate the use of our approach in three industrial applications coming from geosciences and structural mechanics. We also compare our solver with the STRUMPACK package, based on Hierarchically Semi-Separable approximations. We conclude this thesis by reporting results on a very large problem (130 millions of unknowns) which illustrates future challenges posed by BLR multifrontal solvers at scale

Cette thèse présente de nouveaux algorithmes numériques et effectue une étude approfondie de certaines méthodes numériques existantes pour relever les défis de haute dimension résultant de la résolution de l'équation de Schrödinger électronique en chimie quantique. En se concentrant sur deux problèmes spécifiques, notre approche implique l'identification et l'exploitation des symétries et des structures de rang faible au sein de matrices et de tenseurs. Le premier problème abordé dans cette thèse concerne l'évaluation numérique efficace de la composante à longue portée du potentiel de Coulomb à séparation de portée et des intégrales à deux électrons à longue portée, un tenseur du quatrième ordre qui intervient dans de nombreuses méthodes de chimie quantique. Nous présentons deux nouvelles méthodes d'approximation. Cela est réalisé en s'appuyant sur l'interpolation Chebyshev, des règles de quadrature Gaussienne combinées à des approximations de rang faible ainsi que des méthodes rapides multipolaires (FMM). Ce travail offre une explication détaillée de ces approches et algorithmes introduits, accompagnée d'une comparaison approfondie entre les méthodes nouvellement proposées. Le deuxième problème abordé concerne l'exploitation des symétries et des structures de rang faible pour dériver des représentations efficaces en train de tenseurs des opérateurs impliqués dans l'algorithme DMRG. Cet algorithme est une méthode d'optimisation itérative précise utilisée pour résoudre numériquement l'équation de Schrödinger indépendante du temps. Ce travail vise à comprendre et interpréter les résultats obtenus par les communautés de physique et de chimie, et cherche à offrir des perspectives théoriques nouvelles qui, selon nos connaissances, n'ont pas reçu une attention significative auparavant. Nous menons une étude approfondie et fournissons des démonstrations, si nécessaire, pour explorer l'existence d'une représentation particulière en train de tenseurs, creuse par blocs, de l'opérateur Hamiltonien et de sa fonction d'onde associée. Cela est réalisé tout en maintenant les lois de conservation physiques, manifestées sous forme de symétries de groupe dans les tenseurs, telles que la conservation du nombre de particules. La troisième partie de ce travail est dédiée à la réalisation d'une bibliothèque prototype en Julia, pour l'implémentation de DMRG qui est conçue pour le modèle d'opérateur Hamiltonien de la chimie quantique. Nous exploitons ici la représentation en train de tenseurs, creuse par blocs, de l'opérateur et de la fonction d'onde (fonction propre). Avec ces structures, notre objectif est d'accélérer les étapes les plus coûteuses de la DMRG, y compris les contractions de tenseurs, les opérations matrice-vecteur, et la compression de matrices par décomposition en valeurs singulières tronquée. De plus, nous fournissons des résultats issus de diverses simulations moléculaires, tout en comparant les performances de notre bibliothèque avec la bibliothèque ITensors de pointe, où nous démontrons avoir atteint une performance similaire
This thesis presents novel numerical algorithms and conducts a comprehensive study of some existing numerical methods to address high-dimensional challenges arising from the resolution of the electronic Schrödinger equation in quantum chemistry. Focusing on two specific problems, our approach involves the identification and exploitation of symmetries and low-rank structures within matrices and tensors, aiming to mitigate the curse of dimensionality. The first problem considered in this thesis is the efficient numerical evaluation of the long-range component of the range-separated Coulomb potential and the long-range two-electron integrals 4th-order tensor which occurs in many quantum chemistry methods. We present two novel approximation methods. This is achieved by relying on tensorized Chebyshev interpolation, Gaussian quadrature rules combined with low-rank approximations as well as Fast Multipole Methods (FMM). This work offers a detailed explanation of these introduced approaches and algorithms, accompanied by a thorough comparison between the newly proposed methods. The second problem of interest is the exploitation of symmetries and low-rank structures to derive efficient tensor train representations of operators involved in the Density Matrix Renormalization Group (DMRG) algorithm. This algorithm, referred to as the Quantum Chemical DMRG (QC-DMRG) when applied in the field of quantum chemistry, is an accurate iterative optimization method employed to numerically solve the time-independent Schrödinger equation. This work aims to understand and interpret the results obtained from the physics and chemistry communities and seeks to offer novel theoretical insights that, to the best of our knowledge, have not received significant attention before. We conduct a comprehensive study and provide demonstrations, when necessary, to explore the existence of a particular block-sparse tensor train representation of the Hamiltonian operator and its associated eigenfunction. This is achieved while maintaining physical conservation laws, manifested as group symmetries in tensors, such as the conservation of the particle number. The third part of this work is dedicated to the realization of a proof-of-concept Quantum Chemical DMRG (QC-DMRG) Julia library, designed for the quantum chemical Hamiltonian operator model. We exploit here the block-sparse tensor train representation of both the operator and the eigenfunction. With these structures, our goal is to speed up the most time-consuming steps in QC-DMRG, including tensor contractions, matrix-vector operations, and matrix compression through truncated Singular Value Decompositions (SVD). Furthermore, we provide empirical results from various molecular simulations, while comparing the performance of our library with the state-of-the-art ITensors library where we show that we attain a similar performance

We consider the solution of large sparse linear systems by means of direct factorization based on a multifrontal approach. Although numerically robust and easy to use (it only needs algebraic information: the input matrix A and a right-hand side b, even if it can also digest preprocessing strategies based on geometric information), direct factorization methods are computationally intensive both in terms of memory and operations, which limits their scope on very large problems (matrices with up to few hundred millions of equations). This work focuses on exploiting low-rank approximations on multifrontal based direct methods to reduce both the memory footprints and the operation count, in sequential and distributed-memory environments, on a wide class of problems. We first survey the low-rank formats which have been previously developed to efficiently represent dense matrices and have been widely used to design fast solutions of partial differential equations, integral equations and eigenvalue problems. These formats are hierarchical (H and Hierarchically Semiseparable matrices are the most common ones) and have been (both theoretically and practically) shown to substantially decrease the memory and operation requirements for linear algebra computations. However, they impose many structural constraints which can limit their scope and efficiency, especially in the context of general purpose multifrontal solvers. We propose a flat format called Block Low-Rank (BLR) based on a natural blocking of the matrices and explain why it provides all the flexibility needed by a general purpose multifrontal solver in terms of numerical pivoting for stability and parallelism. We compare BLR format with other formats and show that BLR does not compromise much the memory and operation improvements achieved through low-rank approximations. A stability study shows that the approximations are well controlled by an explicit numerical parameter called low-rank threshold, which is critical in order to solve the sparse linear system accurately. Details on how Block Low-Rank factorizations can be efficiently implemented within multifrontal solvers are then given. We propose several Block Low-Rank factorization algorithms which allow for different types of gains. The proposed algorithms have been implemented within the MUMPS (MUltifrontal Massively Parallel Solver) solver. We first report experiments on standard partial differential equations based problems to analyse the main features of our BLR algorithms and to show the potential and flexibility of the approach; a comparison with a Hierarchically SemiSeparable code is also given. Then, Block Low-Rank formats are experimented on large (up to a hundred millions of unknowns) and various problems coming from several industrial applications. We finally illustrate the use of our approach as a preconditioning method for the Conjugate Gradient.

Pour résoudre des systèmes linéaires creux de grande taille, on peut vouloir utiliser des méthodes directes, numériquement robustes, mais coûteuses en termes d'utilisation de la mémoire et de temps de résolution. C'est le cas de la méthode multifrontale, notamment implémentée par le solveur MUMPS. L’une des fonctionnalités disponibles dans ce solveur est l’utilisation de la compression Block Low-Rank (BLR), qui améliore les performances. L'objectif de cette thèse est d'explorer plusieurs pistes d'amélioration de cette compression BLR, de façon à améliorer les performances de la méthode multifrontale. En particulier, nous proposons une variante de la compression BLR utilisant simultanément plusieurs formats de nombres à virgule flottante (précision mixte). Notre démarche, basée sur une analyse d'erreur, permet dans un premier temps de réduire la complexité d'une factorisation LU de matrice dense, sans pour autant impacter l'erreur commise de façon significative. Dans un second temps, nous adaptons ces algorithmes à la méthode multifrontale. Une première implémentation utilise notre compression BLR en précision mixte comme format de stockage, et permet ainsi de réduire la consommation mémoire de MUMPS. Une seconde implémentation permet de combiner ces gains en mémoire avec des gains en temps lors de la phase de résolution de systèmes triangulaires, grâce à des calculs effectués en précision faible. Cependant, nous remarquons que cette étape n'est pas aussi performante que prévu en BLR, dans le cas d'un système linéaire à plusieurs seconds membres. Pour y remédier, nous proposons de nouvelles variantes BLR de la résolution de systèmes triangulaires, dans laquelle la localité mémoire a été améliorée. Nous justifions l'intérêt de cette approche grâce à une analyse de volume de communication. Nous implémentons nos algorithmes dans un prototype simplifié, puis dans MUMPS, et nous obtenons des gains en temps dans les deux cas
In order to solve large sparse linear systems, one may want to use a direct method, numerically robust but rather costly, both in terms of memory consumption and computation time. The multifrontal method belong to this class algorithms, and one of its high-performance parallel implementation is the solver MUMPS. One of the functionalities of MUMPS is the use of Block Low-Rank (BLR) matrix compression, that improves its performance. In this thesis, we present several new techniques aiming at further improving the performance of dense and sparse direct solvers, on top of using a BLR compression. In particular, we propose a new variant of BLR compression in which several floating-point formats are used simultaneously (mixed precision). Our approach is based on an error analysis, and it first allows to reduce the estimated cost of a LU factorization of a dense matrix, without having a significant impact on the error. Second, we adapt these algorithms to the multifrontal method. A first implementation uses our mixed-precision BLR compression as a storage format only, thus allowing to reduce the memory footprint of MUMPS. A second implementation allows to combine these memory gains with time reductions in the triangular solution phase, by switching computations to low precision. However, we notice performance issues related to BLR for this phase, in case the system has many right-hand sides. Therefore, we propose new BLR variants of triangular solution that improve the data locality and reduce data movements, as highlighted by a communication volume analysis. We implement our algorithms within a simplified prototype and within solver MUMPS. In both cases, we obtain time gains