Academic literature on the topic 'Décomposition en trains de tenseurs'

Cet article se veut un survol des réseaux de tenseurs et s'adresse aux débutants en la matière. Nous y mettons l’accent sur les outils nécessaires à l’implémentation concrète d’algorithmes. Quatre opérations de base (remodelage, permutation d’indices, contraction et décomposition) qui sont couramment utilisées dans les algorithmes de réseaux de tenseurs y sont décrites. Y seront aussi couverts la notation diagrammatique, intrication, les états en produit de matrices (MPS), les opérateurs en produit de matrices (MPO), état projeté de paires intriquées (PEPS), l'approche par renormalisation d’enchevêtrement multi-échelle (MERA), la décimation par bloc d’évolution temporelle (TEBD) et le groupe de renormalisation de tenseurs (TRG).

International audience Let $\mathcal{B}_n$ be the hyperoctahedral group acting on a complex vector space $\mathcal{V}$. We present a combinatorial method to decompose the tensor algebra $T(\mathcal{V})$ on $\mathcal{V}$ into simple modules via certain words in a particular Cayley graph of $\mathcal{B}_n$. We then give combinatorial interpretations for the graded dimension and the number of free generators of the subalgebra $T(\mathcal{V})^{\mathcal{B}_n}$ of invariants of $\mathcal{B}_n$, in terms of these words, and make explicit the case of the signed permutation module. To this end, we require a morphism from the Mantaci-Reutenauer algebra onto the algebra of characters due to Bonnafé and Hohlweg. Soit $\mathcal{B}_n$ le groupe hyperoctaédral agissant sur un espace vectoriel complexe $\mathcal{V}$. Nous présentons une méthode combinatoire donnant la décomposition de l'algèbre $T(\mathcal{V})$ des tenseurs sur $\mathcal{V}$ en modules simples via certains mots dans un graphe de Cayley donné. Nous donnons ensuite des interprétations combinatoires pour la dimension graduée et le nombre de générateurs libres de la sous-algèbre $T(\mathcal{V})^{\mathcal{B}_n}$ des invariants de $\mathcal{B}_n$, en termes de ces mots, et explicitons le cas du module de permutation signé. À cette fin, nous utilisons un morphisme entre l'algèbre de Mantaci-Reutenauer et l'algèbre des caractères introduit par Bonnafé et Hohlweg.

International audience Let $V$ be a complex vector space with basis $\{x_1,x_2,\ldots,x_n\}$ and $G$ be a finite subgroup of $GL(V)$. The tensor algebra $T(V)$ over the complex is isomorphic to the polynomials in the non-commutative variables $x_1, x_2, \ldots, x_n$ with complex coefficients. We want to give a combinatorial interpretation for the decomposition of $T(V)$ into simple $G$-modules. In particular, we want to study the graded space of invariants in $T(V)$ with respect to the action of $G$. We give a general method for decomposing the space $T(V)$ into simple $G$-module in terms of words in a particular Cayley graph of $G$. To apply the method to a particular group, we require a surjective homomorphism from a subalgebra of the group algebra into the character algebra. In the case of the symmetric group, we give an example of this homomorphism from the descent algebra. When $G$ is the dihedral group, we have a realization of the character algebra as a subalgebra of the group algebra. In those two cases, we have an interpretation for the graded dimensions of the invariant space in term of those words. Soit V un espace vectoriel complexe de base $\{x_1,x_2,\ldots,x_n\}$ et $G$ un sous-groupe fini de $GL(V)$. L'algèbre $T(V)$ des tenseurs de $V$ sur les complexes est isomorphe aux polynômes à coefficients complexes en variables non-commutatives $x_1, x_2, \ldots, x_n$. Nous voulons donner une décomposition de $T(V)$ en $G$-modules simples de manière combinatoire. Plus particulièrement, nous étudions l'espace gradué des invariants de $T(V)$ sous l'action de $G$. Nous présentons une méthode générale donnant la décomposition de $T(V)$ en modules simples via certains mots dans un graphe de Cayley donné. Pour appliquer la méthode à un groupe particulier, nous avons besoin d'un homomorphisme surjectif entre une sous-algèbre de l'algèbre de groupe et l'algèbre des caractères. Pour le cas du groupe symétrique, nous donnons un exemple de cet homomorphisme qui provient de la théorie de l'algèbre des descentes. Pour le groupe diédral, nous avons une réalisation de l'algèbre des caractères comme une sous-algèbre de l'algèbre de groupe. Dans ces deux cas, nous avons une interprétation des dimensions graduées de l'espace des invariants en terme de ces mots.

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

Cette thèse développe une méthodologie originale et non intrusive de construction de modèles de substitution applicable à des modèles physiques multiparamétriques.La méthodologie proposée permet d’approcher en temps réel, sur l’ensemble du domaine paramétrique, de multiples quantités d’intérêt hétérogènes issues de modèles physiques.Les modèles de substitution sont basés sur des représentations en train de tenseurs obtenues lors d'une phase hors ligne de calculs intensifs.L'idée essentielle de la phase d'apprentissage est de construire simultanément les approximations en se basant sur un nombre limité de résolutions du modèle physique lancées à la volée.L'exploration parcimonieuse du domaine paramétrique couplée au format compact de train de tenseurs permet de surmonter le fléau de la dimension.L'approche est particulièrement adaptée pour traiter des modèles présentant un nombre élevé de paramètres définis sur des domaines étendus.Les résultats numériques sur des lois élasto-viscoplastiques non linéaires montrent que des modèles de substitution compacts en mémoire qui approchent précisément les différentes variables mécaniques dépendantes du temps peuvent être obtenus à des coûts modérés.L'utilisation de tels modèles exploitables en temps réel permet la conception d'outils d'aide à la décision destinés aux experts métiers dans le cadre d'études paramétriques et visent à améliorer la procédure de calibration des lois matériaux
This thesis presents a novel non-intrusive methodology to construct surrogate models of parametric physical models.The proposed methodology enables to approximate in real-time, over the entire parameter space, multiple heterogeneous quantities of interest derived from physical models.The surrogate models are based on tensor train representations built during an intensive offline computational stage.The fundamental idea of the learning stage is to construct simultaneously all tensor approximations based on a reduced number of solutions of the physical model obtained on the fly.The parsimonious exploration of the parameter space coupled with the compact tensor train representation allows to alleviate the curse of dimensionality.The approach accommodates particularly well to models involving many parameters defined over large domains.The numerical results on nonlinear elasto-viscoplastic laws show that compact surrogate models in terms of memory storage that accurately predict multiple time dependent mechanical variables can be obtained at a low computational cost.The real-time response provided by the surrogate model for any parameter value allows the implementation of decision-making tools that are particularly interesting for experts in the context of parametric studies and aim at improving the procedure of calibration of material laws

Cette thèse est constituée de deux parties. La première regroupe les chapitres 2 et 3 et traite du schéma de Hilbert. Ces chapitres correspondent respectivement à des travaux en collaboration avec M.E. Alonso et B. Mourrain : [3] et avec P. Lella, B. Mourrain et M. Roggero : [10]. Nous nous intéresserons aux équations qui le définissent comme sous-schéma fermé de la grassmannienne et plus précisément à leur degré. Nous fournirons ainsi de nouvelles équations globales, plus simples que celles qui existent déjà. Le chapitre 2 se concentre sur le cas des polynômes de Hilbert constants égaux à μ. Après avoir rappelé les définitions et propriétés élémen- μ taires du foncteur de Hilbert associé à μ, noté HilbPn , nous montrerons que celui-ci est représentable. Nous adopterons pour cela une approche locale et construirons un recouvrement ouvert de sous-foncteurs représen- tables, dont les équations correspondent aux relations de commutation qui caractérisent les bases de bord. Son représentant s'appelle le schéma de Hilbert associé à μ, noté Hilbμ(Pn). Nous fournirons ensuite, grâce aux théorèmes de Persistance et de Régularité de Gotzmann, une description globale de ce schéma. Nous donne- rons un système d'équations homogènes de degré 2 en les coordonnées de Plücker qui caractérise Hilbμ(Pn) comme sous-schéma fermé de la Grassmannienne. Nous conclurons ce chapitre par une étude du plan tangent au schéma de hilbert en exploitant l'approche locale et les relations de commutation précédemment introduites. Le chapitre 3 traite le cas général du schéma de Hilbert associé à un polynôme P de degré d ≥ 0, noté HilbP (Pn). Nous généraliserons le chapitre précédent en fournissant des équations globales homogènes de degré d + 2 en les coordonnées de Plücker. La deuxième partie de cette thèse concerne la décomposition de tenseurs, chapitre 4. Nous commencerons par étudier le cas symétrique, qui correspond à l'article [9] en collaboration avec P. Comon, B. Mourrain et E. Tsi- garidas. Nous étendrons pour cela l'algorithme de Sylvester proposé pour le cas binaire. Nous utiliserons une approche duale et fournirons des conditions nécessaires et suffisantes pour l'existence d'une décomposition de rang donné, en utilisant les opérateurs de Hankel. Nous en déduirons un algorithme pour le cas symétrique. Nous aborderons aussi la question de l'unicité de la décomposition minimale. Enfin, nous conclurons en étu- diant le cas des tenseurs généraux qui correspond à un article en collaboration avec A. Bernardi, P. Comon et B. Mourrain : [6]. Nous montrerons en particulier comment le formalisme introduit pour le cas symétrique peut s'adapter pour résoudre le problème.

On étudie la décomposition de matrice de Hankel comme une somme des matrices de Hankel de rang faible en corrélation avec la décomposition de son symbole σ comme une somme des séries exponentielles polynomiales. On présente un nouvel algorithme qui calcule la décomposition d’un opérateur de Hankel de petit rang et sa décomposition de son symbole en exploitant les propriétés de l’algèbre quotient de Gorenstein . La base de est calculée à partir la décomposition en valeurs singuliers d’une sous-matrice de matrice de Hankel . Les fréquences et les poids se déduisent des vecteurs propres généralisés des sous matrices de Hankel déplacés de . On présente une formule pour calculer les poids en fonction des vecteurs propres généralisés au lieu de résoudre un système de Vandermonde. Cette nouvelle méthode est une généralisation de Pencil méthode déjà utilisée pour résoudre un problème de décomposition de type de Prony. On analyse son comportement numérique en présence des moments contaminés et on décrit une technique de redimensionnement qui améliore la qualité numérique des fréquences d’une grande amplitude. On présente une nouvelle technique de Newton qui converge localement vers la matrice de Hankel de rang faible la plus proche au matrice initiale et on montre son effet à corriger les erreurs sur les moments. On étudie la décomposition d’un tenseur multi-symétrique T comme une somme des puissances de produit des formes linéaires en corrélation avec la décomposition de son dual comme une somme pondérée des évaluations. On utilise les propriétés de l’algèbre de Gorenstein associée pour calculer la décomposition de son dual qui est définie à partir d’une série formelle τ. On utilise la décomposition d’un opérateur de Hankel de rang faible associé au symbole τ comme une somme des opérateurs indécomposables de rang faible. La base d’ est choisie de façon que la multiplication par certains variables soit possible. On calcule les coordonnées des points et leurs poids correspondants à partir la structure propre des matrices de multiplication. Ce nouvel algorithme qu’on propose marche bien pour les matrices de Hankel de rang faible. On propose une approche théorique de la méthode dans un espace de dimension n. On donne un exemple numérique de la décomposition d’un tenseur multilinéaire de rang 3 en dimension 3 et un autre exemple de la décomposition d’un tenseur multi-symétrique de rang 3 en dimension 3. On étudie le problème de complétion de matrice de Hankel comme un problème de minimisation. On utilise la relaxation du problème basé sur la minimisation de la norme nucléaire de la matrice de Hankel. On adapte le SVT algorithme pour le cas d’une matrice de Hankel et on calcule l’opérateur linéaire qui décrit les contraintes du problème de minimisation de norme nucléaire. On montre l’utilité du problème de décomposition à dissocier un modèle statistique ou biologique
We study the decomposition of a multivariate Hankel matrix as a sum of Hankel matrices of small rank in correlation with the decomposition of its symbol σ as a sum of polynomialexponential series. We present a new algorithm to compute the low rank decomposition of the Hankel operator and the decomposition of its symbol exploiting the properties of the associated Artinian Gorenstein quotient algebra . A basis of is computed from the Singular Value Decomposition of a sub-matrix of the Hankel matrix . The frequencies and the weights are deduced from the generalized eigenvectors of pencils of shifted sub-matrices of Explicit formula for the weights in terms of the eigenvectors avoid us to solve a Vandermonde system. This new method is a multivariate generalization of the so-called Pencil method for solving Pronytype decomposition problems. We analyse its numerical behaviour in the presence of noisy input moments, and describe a rescaling technique which improves the numerical quality of the reconstruction for frequencies of high amplitudes. We also present a new Newton iteration, which converges locally to the closest multivariate Hankel matrix of low rank and show its impact for correcting errors on input moments. We study the decomposition of a multi-symmetric tensor T as a sum of powers of product of linear forms in correlation with the decomposition of its dual as a weighted sum of evaluations. We use the properties of the associated Artinian Gorenstein Algebra to compute the decomposition of its dual which is defined via a formal power series τ. We use the low rank decomposition of the Hankel operator associated to the symbol τ into a sum of indecomposable operators of low rank. A basis of is chosen such that the multiplication by some variables is possible. We compute the sub-coordinates of the evaluation points and their weights using the eigen-structure of multiplication matrices. The new algorithm that we propose works for small rank. We give a theoretical generalized approach of the method in n dimensional space. We show a numerical example of the decomposition of a multi-linear tensor of rank 3 in 3 dimensional space. We show a numerical example of the decomposition of a multi-symmetric tensor of rank 3 in 3 dimensional space. We study the completion problem of the low rank Hankel matrix as a minimization problem. We use the relaxation of it as a minimization problem of the nuclear norm of Hankel matrix. We adapt the SVT algorithm to the case of Hankel matrix and we compute the linear operator which describes the constraints of the problem and its adjoint. We try to show the utility of the decomposition algorithm in some applications such that the LDA model and the ODF model

Dans cette thèse, nous nous focalisons sur le problème de la décomposition polyadique minimale de tenseurs de dimension trois, problème auquel on se réfère généralement sous différentes terminologies : " Polyadique Canonique " (CP en anglais), " CanDecomp ", ou encore " Parafac ". Cette décomposition s'avère très utile dans un très large panel d'applications. Cependant, nous nous concentrons ici sur la spectroscopie de fluorescence appliquée à des données environnementales particulières de type échantillons d'eau qui pourront avoir été collectés en divers endroits ou différents moments. Ils contiennent un mélange de plusieurs molécules organiques et l'objectif des traitements numériques mis en œuvre est de parvenir à séparer et à ré-estimer ces composés présents dans les échantillons étudiés. Par ailleurs, dans plusieurs applications comme l'imagerie hyperspectrale ou justement, la chimiométrie, il est intéressant de contraindre les matrices de facteurs recherchées à être réelles et non négatives car elles sont représentatives de quantités physiques réelles non négatives (spectres, fractions d'abondance, concentrations, ...etc.). C'est pourquoi tous les algorithmes développés durant cette thèse l'ont été dans ce cadre (l'avantage majeur de cette contrainte étant de rendre le problème d'approximation considéré bien posé). Certains de ces algorithmes reposent sur l'utilisation de méthodes proches des fonctions barrières, d'autres approches consistent à paramétrer directement les matrices de facteurs recherchées par des carrés.

Dans ce travail, on s'intéresse à des outils mathématiques spéciaux appelés tenseurs qui sont formellement définis comme des tableaux multidimensionnels définis sur le produit tensoriel d'espaces vectoriels (chaque espace vectoriel étant muni de son système de coordonnées), le nombre d'espaces vectoriels impliqués dans ce produit étant l'ordre du tenseur. L'intérêt pour les tenseurs est motivé par certains travaux expérimentaux qui ont prouvé, dans divers contextes, que traiter des données multidimensionnelles avec des tenseurs plutôt que des matrices donne un meilleur résultat aussi bien pour des tâches de régression que de classification. Dans le cadre de la thèse, nous nous sommes focalisés sur une décomposition dite de Tucker et avons mis en place une méthode pour l'apprentissage de dictionnaires, une technique pour l'apprentissage en ligne de dictionnaires, une approche pour la décomposition d'un tenseur de grandes tailles et enfin une méthodologie pour la décomposition d'un tenseur qui croît par rapport à tous les modes. De nouveaux résultats théoriques concernant la convergence et la vitesse de convergence sont établis et l'efficacité des algorithmes proposés, reposant soit sur la minimisation alternée, soit sur la descente de gradients par coordonnées, est démontrée sur des problèmes réels
In this work, we are interested in special mathematical tools called tensors, that are multidimensional arrays defined on tensor product of some vector spaces, each of which has its own coordinate system and the number of spaces involved in this product is generally referred to as order. The interest for these tools stem from some empirical works (for a range of applications encompassing both classification and regression) that prove the superiority of tensor processing with respect to matrix decomposition techniques. In this thesis framework, we focused on specific tensor model named Tucker and established new approaches for miscellaneous tasks such as dictionary learning, online dictionary learning, large-scale processing as well as the decomposition of a tensor evolving with respect to each of its modes. New theoretical results are established and the efficiency of the different algorithms, which are based either on alternate minimization or coordinate gradient descent, is proven via real-world problems

Les dernières décennies ont donné lieux à d'énormes progrès dans la simulation numérique des phénomènes physiques. D'une part grâce au raffinement des méthodes de discrétisation des équations aux dérivées partielles. Et d'autre part grâce à l'explosion de la puissance de calcul disponible. Pourtant, de nombreux problèmes soulevés en ingénierie tels que les simulations multi-physiques, les problèmes d'optimisation et de contrôle restent souvent hors de portée. Le dénominateur commun de ces problèmes est le fléau des dimensions. Un simple problème tridimensionnel requiert des centaines de millions de points de discrétisation auxquels il faut souvent ajouter des milliers de pas de temps pour capturer des dynamiques complexes. L'avènement des supercalculateurs permet de générer des simulations de plus en plus fines au prix de données gigantesques qui sont régulièrement de l'ordre du pétaoctet. Malgré tout, cela n'autorise pas une résolution ``exacte'' des problèmes requérant l'utilisation de plusieurs paramètres. L'une des voies envisagées pour résoudre ces difficultés est de proposer des représentations ne souffrant plus du fléau de la dimension. Ces représentations que l'on appelle séparées sont en fait un changement de paradigme. Elles vont convertir des objets tensoriels dont la croissance est exponentielle $n^d$ en fonction du nombre de dimensions $d$ en une représentation approchée dont la taille est linéaire en $d$. Pour le traitement des données tensorielles, une vaste littérature a émergé ces dernières années dans le domaine des mathématiques appliquées.Afin de faciliter leurs utilisations dans la communauté des mécaniciens et en particulier pour la simulation en mécanique des fluides, ce manuscrit présente dans un vocabulaire rigoureux mais accessible les formats de représentation des tenseurs et propose une étude détaillée des algorithmes de décomposition de données qui y sont associées. L'accent est porté sur l'utilisation de ces méthodes, aussi la bibliothèque de calcul texttt{pydecomp} développée est utilisée pour comparer l'efficacité de ces méthodes sur un ensemble de cas qui se veut représentatif. La seconde partie de ce manuscrit met en avant l'étude de l'écoulement dans une cavité entraînée à haut nombre de Reynolds. Cet écoulement propose une physique très riche (séquence de bifurcation de Hopf) qui doit être étudiée en amont de la construction de modèle réduit. Cette étude est enrichie par l'utilisation de la décomposition orthogonale aux valeurs propres (POD). Enfin une approche de construction ``physique'', qui diffère notablement des développements récents pour les modèles d'ordre réduit, est proposée. La connaissance détaillée de l'écoulement permet de construire un modèle réduit simple basé sur la mise à l'échelle des fréquences d'oscillation (time-scaling) et des techniques d'interpolation classiques (Lagrange,..)
Numerical simulation has experienced tremendous improvements in the last decadesdriven by massive growth of computing power. Exascale computing has beenachieved this year and will allow solving ever more complex problems. But suchlarge systems produce colossal amounts of data which leads to its own difficulties.Moreover, many engineering problems such as multiphysics or optimisation andcontrol, require far more power that any computer architecture could achievewithin the current scientific computing paradigm. In this thesis, we proposeto shift the paradigm in order to break the curse of dimensionality byintroducing decomposition and building reduced order models (ROM) for complexfluid flows.This manuscript is organized into two parts. The first one proposes an extendedreview of data reduction techniques and intends to bridge between appliedmathematics community and the computational mechanics one. Thus, foundingbivariate separation is studied, including discussions on the equivalence ofproper orthogonal decomposition (POD, continuous framework) and singular valuedecomposition (SVD, discrete matrices). Then a wide review of tensor formats andtheir approximation is proposed. Such work has already been provided in theliterature but either on separate papers or into a purely applied mathematicsframework. Here, we offer to the data enthusiast scientist a comparison ofCanonical, Tucker, Hierarchical and Tensor train formats including theirapproximation algorithms. Their relative benefits are studied both theoreticallyand numerically thanks to the python library texttt{pydecomp} that wasdeveloped during this thesis. A careful analysis of the link between continuousand discrete methods is performed. Finally, we conclude that for mostapplications ST-HOSVD is best when the number of dimensions $d$ lower than fourand TT-SVD (or their POD equivalent) when $d$ grows larger.The second part is centered on a complex fluid dynamics flow, in particular thesingular lid driven cavity at high Reynolds number. This flow exhibits a seriesof Hopf bifurcation which are known to be hard to capture accurately which iswhy a detailed analysis was performed both with classical tools and POD. Oncethis flow has been characterized, emph{time-scaling}, a new ``physics based''interpolation ROM is presented on internal and external flows. This methodsgives encouraging results while excluding recent advanced developments in thearea such as EIM or Grassmann manifold interpolation

Cette thèse présente de nouveaux algorithmes de diagonalisation conjointe par similitude. Cesalgorithmes permettent, entre autres, de résoudre le problème de décomposition canonique polyadiquede tenseurs. Cette décomposition est particulièrement utilisée dans les problèmes deséparation de sources. L’utilisation de la diagonalisation conjointe par similitude permet de paliercertains problèmes dont les autres types de méthode de décomposition canonique polyadiquesouffrent, tels que le taux de convergence, la sensibilité à la surestimation du nombre de facteurset la sensibilité aux facteurs corrélés. Les algorithmes de diagonalisation conjointe par similitudetraitant des données complexes donnent soit de bons résultats lorsque le niveau de bruit est faible,soit sont plus robustes au bruit mais ont un coût calcul élevé. Nous proposons donc en premierlieu des algorithmes de diagonalisation conjointe par similitude traitant les données réelles etcomplexes de la même manière. Par ailleurs, dans plusieurs applications, les matrices facteursde la décomposition canonique polyadique contiennent des éléments exclusivement non-négatifs.Prendre en compte cette contrainte de non-négativité permet de rendre les algorithmes de décompositioncanonique polyadique plus robustes à la surestimation du nombre de facteurs ou lorsqueces derniers ont un haut degré de corrélation. Nous proposons donc aussi des algorithmes dediagonalisation conjointe par similitude exploitant cette contrainte. Les simulations numériquesproposées montrent que le premier type d’algorithmes développés améliore l’estimation des paramètresinconnus et diminue le coût de calcul. Les simulations numériques montrent aussi queles algorithmes avec contrainte de non-négativité améliorent l’estimation des matrices facteurslorsque leurs colonnes ont un haut degré de corrélation. Enfin, nos résultats sont validés à traversdeux applications de séparation de sources en télécommunications numériques et en spectroscopiede fluorescence
This thesis introduces new joint eigenvalue decomposition algorithms. These algorithms allowamongst others to solve the canonical polyadic decomposition problem. This decomposition iswidely used for blind source separation. Using the joint eigenvalue decomposition to solve thecanonical polyadic decomposition problem allows to avoid some problems whose the others canonicalpolyadic decomposition algorithms generally suffer, such as the convergence rate, theoverfactoring sensibility and the correlated factors sensibility. The joint eigenvalue decompositionalgorithms dealing with complex data give either good results when the noise power is low, orthey are robust to the noise power but have a high numerical cost. Therefore, we first proposealgorithms equally dealing with real and complex. Moreover, in some applications, factor matricesof the canonical polyadic decomposition contain only nonnegative values. Taking this constraintinto account makes the algorithms more robust to the overfactoring and to the correlated factors.Therefore, we also offer joint eigenvalue decomposition algorithms taking advantage of thisnonnegativity constraint. Suggested numerical simulations show that the first developed algorithmsimprove the estimation accuracy and reduce the numerical cost in the case of complexdata. Our numerical simulations also highlight the fact that our nonnegative joint eigenvaluedecomposition algorithms improve the factor matrices estimation when their columns have ahigh correlation degree. Eventually, we successfully applied our algorithms to two blind sourceseparation problems : one concerning numerical telecommunications and the other concerningfluorescence spectroscopy

De nos jours, les grandes masses de données se retrouvent dans de nombreux domaines relatifs aux applications multimédia, sociologiques, biomédicales, radio astronomiques, etc. On parle alors du phénomène ‘Big Data’ qui nécessite le développement d’outils appropriés pour la manipulation et l’analyse appropriée de telles masses de données. Ce travail de thèse est dédié au développement de méthodes efficaces pour la décomposition rapide et adaptative de tenseurs ou matrices de grandes tailles et ce pour l’analyse de données multidimensionnelles. Nous proposons en premier une méthode d’estimation de sous espaces qui s’appuie sur la technique dite ‘divide and conquer’ permettant une estimation distribuée ou parallèle des sous-espaces désirés. Après avoir démontré l’efficacité numérique de cette solution, nous introduisons différentes variantes de celle-ci pour la poursuite adaptative ou bloc des sous espaces principaux ou mineurs ainsi que des vecteurs propres de la matrice de covariance des données. Une application à la suppression d’interférences radiofréquences en radioastronomie a été traitée. La seconde partie du travail a été consacrée aux décompositions rapides de type PARAFAC ou Tucker de tenseurs multidimensionnels. Nous commençons par généraliser l’approche ‘divide and conquer’ précédente au contexte tensoriel et ce en vue de la décomposition PARAFAC parallélisable des tenseurs. Ensuite nous adaptons une technique d’optimisation de type ‘all-at-once’ pour la décomposition robuste (à la méconnaissance des ordres) de tenseurs parcimonieux et non négatifs. Finalement, nous considérons le cas de flux de données continu et proposons deux algorithmes adaptatifs pour la décomposition rapide (à complexité linéaire) de tenseurs en dimension 3. Malgré leurs faibles complexités, ces algorithmes ont des performances similaires (voire parfois supérieures) à celles des méthodes existantes de la littérature. Au final, ce travail aboutit à un ensemble d’outils algorithmiques et algébriques efficaces pour la manipulation et l’analyse de données multidimensionnelles de grandes tailles
Large volumes of data are being generated at any given time, especially from transactional databases, multimedia content, social media, and applications of sensor networks. When the size of datasets is beyond the ability of typical database software tools to capture, store, manage, and analyze, we face the phenomenon of big data for which new and smarter data analytic tools are required. Big data provides opportunities for new form of data analytics, resulting in substantial productivity. In this thesis, we will explore fast matrix and tensor decompositions as computational tools to process and analyze multidimensional massive-data. We first aim to study fast subspace estimation, a specific technique used in matrix decomposition. Traditional subspace estimation yields high performance but suffers from processing large-scale data. We thus propose distributed/parallel subspace estimation following a divide-and-conquer approach in both batch and adaptive settings. Based on this technique, we further consider its important variants such as principal component analysis, minor and principal subspace tracking and principal eigenvector tracking. We demonstrate the potential of our proposed algorithms by solving the challenging radio frequency interference (RFI) mitigation problem in radio astronomy. In the second part, we concentrate on fast tensor decomposition, a natural extension of the matrix one. We generalize the results for the matrix case to make PARAFAC tensor decomposition parallelizable in batch setting. Then we adapt all-at-once optimization approach to consider sparse non-negative PARAFAC and Tucker decomposition with unknown tensor rank. Finally, we propose two PARAFAC decomposition algorithms for a classof third-order tensors that have one dimension growing linearly with time. The proposed algorithms have linear complexity, good convergence rate and good estimation accuracy. The results in a standard setting show that the performance of our proposed algorithms is comparable or even superior to the state-of-the-art algorithms. We also introduce an adaptive nonnegative PARAFAC problem and refine the solution of adaptive PARAFAC to tackle it. The main contributions of this thesis, as new tools to allow fast handling large-scale multidimensional data, thus bring a step forward real-time applications