Dans cette thèse, nous nous intéressons à la résolution parallèle de grands systèmes linéaires creux. Nous nous focalisons plus particulièrement sur les solveurs linéaires creux hybrides directs itératifs tels que HIPS, MaPHyS, PDSLIN ou ShyLU, qui sont basés sur une décomposition de domaine et une approche « complément de Schur ». Bien que ces solveurs soient moins coûteux en temps et en mémoire que leurs homologues directs, ils ne sont néanmoins pas exempts de surcoûts. Dans une première partie, nous présentons les différentes méthodes de réduction de la consommation mémoire déjà existantes et en proposons une nouvelle qui n’impacte pas la robustesse numérique du précondionneur construit. Cette technique se base sur une atténuation du pic mémoire par un ordonnancement spécifique des tâches de calcul, d’allocation et de désallocation des blocs, notamment ceux se trouvant dans les parties « couplage » des domaines.Dans une seconde partie, nous nous intéressons à la question de l’équilibrage de la charge que pose la décomposition de domaine pour le calcul parallèle. Ce problème revient à partitionner le graphe d’adjacence de la matrice en autant de parties que de domaines désirés. Nous mettons en évidence le fait que pour avoir un équilibrage correct des temps de calcul lors des phases les plus coûteuses d’un solveur hybride tel que MaPHyS, il faut à la fois équilibrer les domaines en termes de nombre de noeuds et de taille d’interface locale. Jusqu’à aujourd’hui, les partitionneurs de graphes tels que Scotch et MeTiS ne s’intéressaient toutefois qu’au premier critère (la taille des domaines) dans le contexte de la renumérotation des matrices creuses. Nous proposons plusieurs variantes des algorithmes existants afin de prendre également en compte l’équilibrage des interfaces locales. Toutes nos modifications sont implémentées dans le partitionneur Scotch, et nous présentons des résultats sur de grands cas de tests industriels. / In this thesis, we focus on the parallel solving of large sparse linear systems. Our main interestis on direct-iterative hybrid solvers such as HIPS, MaPHyS, PDSLIN or ShyLU, whichrely on domain decomposition and Schur complement approaches. Althrough these solvers arenot as time and space consuming as direct methods, they still suffer from serious overheads. Ina first part, we thus present the existing techniques for reducing the memory consumption, andwe present a new method which does not impact the numerical robustness of the preconditioner.This technique reduces the memory peak by doing a special scheduling of computation, allocation,and freeing tasks in particular in the Schur coupling blocks of the matrix. In a second part,we focus on the load balancing of the domain decomposition in a parallel context. This problemconsists in partitioning the adjacency graph of the matrix in as many domains as desired. Wepoint out that a good load balancing for the most expensive steps of an hybrid solver such asMaPHyS relies on the balancing of both interior nodes and interface nodes of the domains.Through, until now, graph partitioners such as MeTiS or Scotch used to optimize only thefirst criteria (i.e., the balancing of interior nodes) in the context of sparse matrix ordering. Wepropose different variations of the existing algorithms to improve the balancing of interface nodesand interior nodes simultaneously. All our changes are implemented in the Scotch partitioner.We present our results on large collection of matrices coming from real industrial cases.

Les Systèmes à Evénements Discrets (SED) peuvent être définis comme des systèmes dans lesquels les variables d'état changent sous l'occurrence d'évènements au fil du temps. Les SED mettant en jeu des phénomènes de synchronisation peuvent être modélisés par des équations linéaires dans les algèbres de type (max,+). L'analyse d'atteignabilité est une problématique majeure pour les systèmes dynamiques. L'objectif est de calculer l'ensemble des états atteignables d'un système dynamique pour toutes les valeurs admissibles d'un ensemble d'états initiaux. Le problème de l'analyse d'atteignabilité pour les systèmes Max-Plus Linéaire (MPL) a été, proprement, résolu en décomposant le système MPL en une combinaison de systèmes affines par morceaux où les composantes affines du système sont représentées par des matrices de différences bornées (Difference Bound Matrix, DBM). La contribution principale de cette thèse est de présenter une procédure similaire pour résoudre le problème de l'atteignabilité pour des systèmes MPL incertains (uMPL), c'est-à-dire des systèmes MPL soumis à des bruits bornés, des perturbations et/ou des erreurs de modélisation. Tout d'abord, nous présentons une procédure permettant de partionner l'espace d'état d'un système uMPL en parties représentables par des DBM. Ensuite, nous étendons l'analyse d'atteignabilité des systèmes MPL aux systèmes uMPL. Enfin, les résultats sur l'analyse d'atteignabilité sont mis en oeuvre pour résoudre le problème d'atteignabilité conditionnelle, qui est étroitement lié au calcul du support de la densité de probabilité impliquée dans le problème de filtage stochastique / Discrete Event Dynamic Systems (DEDS) are discrete-state systems whose dynamics areentirely driven by the occurrence of asynchronous events over time. Linear equations in themax-plus algebra can be used to describe DEDS subjected to synchronization and time delayphenomena. The reachability analysis concerns the computation of all states that can bereached by a dynamical system from an initial set of states. The reachability analysis problemof Max Plus Linear (MPL) systems has been properly solved by characterizing the MPLsystems as a combination of Piece-Wise Affine (PWA) systems and then representing eachcomponent of the PWA system as Difference-Bound Matrices (DBM). The main contributionof this thesis is to present a similar procedure to solve the reachability analysis problemof MPL systems subjected to bounded noise, disturbances and/or modeling errors, calleduncertain MPL (uMPL) systems. First, we present a procedure to partition the state spaceof an uMPL system into components that can be completely represented by DBM. Then weextend the reachability analysis of MPL systems to uMPL systems. Moreover, the results onreachability analysis of uMPL systems are used to solve the conditional reachability problem,which is closely related to the support calculation of the probability density function involvedin the stochastic filtering problem. / Os Sistemas a Eventos Discretos (SEDs) constituem uma classe de sistemas caracterizada por apresentar espaço de estados discreto e dinâmica dirigida única e exclusivamente pela ocorrência de eventos. SEDs sujeitos aos problemas de sincronização e de temporização podem ser descritos em termos de equações lineares usando a álgebra max-plus. A análise de alcançabilidade visa o cálculo do conjunto de todos os estados que podem ser alcançados a partir de um conjunto de estados iniciais através do modelo do sistema. A análise de alcançabilidade de sistemas Max Plus Lineares (MPL) pode ser tratada por meio da decomposição do sistema MPL em sistemas PWA (Piece-Wise Affine) e de sua correspondente representação por DBM (Difference-Bound Matrices). A principal contribuição desta tese é a proposta de uma metodologia similar para resolver o problema de análise de alcançabilidade em sistemas MPL sujeitos a ruídos limitados, chamados de sistemas MPL incertos ou sistemas uMPL (uncertain Max Plus Linear Systems). Primeiramente, apresentamos uma metodologia para particionar o espaço de estados de um sistema uMPL em componentes que podem ser completamente representados por DBM. Em seguida, estendemos a análise de alcançabilidade de sistemas MPL para sistemas uMPL. Além disso, a metodologia desenvolvida é usada para resolver o problema de análise de alcançabilidade condicional, o qual esta estritamente relacionado ao cálculo do suporte da função de probabilidade de densidade envolvida o problema de filtragem estocástica.

La combinatoire a permis de résoudre certains problèmes en Mathématiques, en Physique et en Informatique, en retour celles-ci inspirent des questions nouvelles à la combinatoire. Ce mémoire de thèse intitulé "Combinatoire et algorithme des factorisations tangentes à l'identité" regroupe plusieurs travaux sur la combinatoire des déformations du produit de Shuffle. L'objectif de cette thèse est d'écrire des factorisations dont le terme principal est l'identité à travers l'utilisation d'outils portant principalement sur la combinatoire des mots (ordres, graduation etc.). Dans le cas classique, soit F une algèbre libre. En raison du fait que F est une algèbre enveloppante, on a une factorisation exacte de l'identité de End(F) = F*⨶F comme un produit infini d'exponentielles (End(F) étant muni du produit de Shuffle sur la gauche et de la concaténation sur la droite, une représentation fidèle du produit de convolution). La procédure est la suivante : premièrement on commence avec une base de Poincaré-Birkhoff-Witt, deuxièmement on calcule la famille des formes coordonnées et alors les propriétés (combinatoires) non triviales de ces familles en dualité donne la factorisation. Si on part de l'autre côté, l'écriture pour le même produit ne donne exactement l'identité que sous des conditions très restrictives que nous précisons ici. Dans de nombreux autres cas (déformés), la construction explicite des paires de bases en dualité nécessite une étude combinatoire et algorithmique que nous fournissons dans ce mémoire. / Combinatorics has solved many problems in Mathematics, Physics and Computer Science, in return these domains inspire new questions to combinatorics. This memoir entitled "Combinatorics and algorithmics of factorization tangent to indentity includes several works on the combinatorial deformations of the shuffle product. The aim of this thesis is to write factorizations wich principal term is the identity through the use of tools relating mainly to combinatorics on the words (orderings, grading etc). In the classical case, let F be the free algebra. Due to the fact that F is an enveloping algebra, one has an exact factorization of the identity of End(F) = F⨶F as an infinite product of exponentials (End(F) being endowed with the shuffle product on the left and the concatenation on the right, a faithful representation of the convolution product) as follows : first on begins with a PBW basis, second one computes the family of coordinate forms and then non-trivial (combinatorial) properties of theses families in duality gives the factorization. Starting from the other side and writing the same product does give exactly identity only under very restrictive conditions that we clarify here. In many other (deformed) cases, the explicit construction of pairs of bases in duality requires combinatorial and algorithmic studies that we provide in this memoir.

Quelques problèmes en analyse harmonique non commutative / Some problems on noncommutative harmonique analysis

L'objet de la thèse est la classification à conjugaison près des sous-groupes finis du groupe de stabilisateur (classique) de Morava S_n et du groupe de stabilisateur étendu G_n(u) associé à une loi de groupe formel F de hauteur n définie sur le corps F_p à p éléments. Une classification complète dans S_n est établie pour tout entier positif n et premier p. De plus, on montre que la classification dans le groupe étendu dépend aussi de F et son unité associée u dans l'anneau des entiers p-adiques. On établit un cadre théorique pour la classification dans G_n(u), on donne des conditions nécessaires et suffisantes sur n, p et u pour l'existence dans G_n(u) d'extensions de sous-groupes finis maximaux de S_n par le groupe de Galois de F_{p^n} sur F_p, et lorsque de telles extensions existent on dénombre leurs classes de conjugaisons. On illustre nos méthodes en fournissant une classification complète et explicite dans le cas n=2. / The problem addressed is the classification up to conjugation of the finite subgroups of the (classical) Morava stabilizer group S_n and the extended Morava stabilizer group G_n(u) associated to a formal group law F of height n over the field F_p of p elements. A complete classification in S_n is provided for any positive integer n and prime p. Furthermore, we show that the classification in the extended group also depends on F and its associated unit u in the ring of p-adic integers. We provide a theoretical framework for the classification in G_n(u), we give necessary and sufficient conditions on n, p and u for the existence in G_n(u) of extensions of maximal finite subgroups of S_n by the Galois group of F_{p^n} over F_p, and whenever such extension exist we enumerate their conjugacy classes. We illustrate our methods by providing a complete and explicit classification in the case n=2.

L'article "A systematic search for nonrelativistic systems with dynamical symetries, Part I" publié il y a à peu près 50 ans a commencé une classification de ce qui est maintenant appelé les systèmes superintégrables. Il était dévoué aux systèmes dans l'espace Euclidien ayant plus d'intégrales de mouvement que de degrés de liberté. Les intégrales étaient toutes supposées de second ordre en quantité de mouvement. Dans ce mémoire, sont présentés de nouveaux résultats sur la superintégrabilité de second ordre qui sont pertinents à l'étude de la superintégrabilité d'ordre supérieur et de la superintégrabilité de systèmes ayant des potentiels vecteurs ou des particules avec spin. / The article "A systematic search for nonrelativistic systems with dynamical symetries, Part I" published about 50 years ago started the classification of what is now called superintegrable systems. It was devoted to systems in Euclidean space with more integrals of motion than degrees of freedom. The integrals were all assumed to be second order polynomials in the particle momentum. Here we present some further results on second order superintegrability that are relevant for studies of higher order superintegrability and for superintegrability for systems with vector potentials or for particles with spin.

Cette thèse est divisée en quatre parties qui portent sur les centralisateurs des algèbres quantiques \(U_q(\mathfrak{sl}_N)\), les polynômes biorthogonaux avec propriétés bispectrales, les polynômes bivariés de Griffiths, et les schémas d'association avec structures polynomiales bivariées. Le fil conducteur principal entre ces parties est l'algèbre d'Askey–Wilson. Dans la première partie, l'idée principale est de combiner l'algèbre du groupe des tresses avec l'algèbre d'Askey–Wilson dans des situations qui impliquent les centralisateurs de \(U_q(\mathfrak{sl}_2)\). Ainsi, on obtient des représentations du groupe des tresses en termes de polynômes orthogonaux de \(q\)-Racah par le biais de matrices \(R\) de \(U_q(\mathfrak{sl}_2)\), on obtient une interprétation de l'algèbre d'Askey–Wilson dans le cadre de la théorie topologique des champs de Chern–Simons avec groupe de jauge \(SU(2)\) ainsi que dans le cadre des invariants d'entrelacs associés à \(U_q(\mathfrak{su}_2)\), et on offre une description algébrique complète du centralisateur de \(U_q(\mathfrak{sl}_2)\) dans un produit tensoriel de trois représentations irréductibles identiques de spin quelconque. Dans une optique différente, on offre aussi une présentation algébrique de certaines algèbres de Hecke fusionnées qui décrivent des centralisateurs de \(U_q(\mathfrak{sl}_N)\). Dans la deuxième partie, on étudie deux familles de polynômes biorthogonaux par des méthodes algébriques, offrant une extension du tableau qui existe pour les polynômes orthogonaux classiques de type Askey–Wilson. Les deux familles considérées sont les polynômes \(R_I\) de type Hahn et les polynômes de Pastro. Dans les deux cas, l'idée est d'introduire un triplet d'opérateurs ayant une action tridiagonale et d'obtenir les polynômes comme solutions à deux problèmes aux valeurs propres généralisés provenant de ce triplet. On trouve les propriétés de bispectralité et de biorthogonalité des polynômes en se servant des opérateurs du triplet, et on détermine l'algèbre réalisée par les opérateurs. Dans la troisième partie, on caractérise deux familles de polynômes bivariés de Griffiths. La première famille est une généralisation des polynômes de Griffiths de type Krawtchouk qui dépend d'un paramètre \(\lambda\). On trouve leurs relations de bispectralité et leur biorthogonalité en utilisant les propriétés des polynômes de Krawtchouk à une variable. Les relations de contiguïté des polynômes univariés jouent un rôle essentiel dans les calculs. On utilise des méthodes semblables pour caractériser la deuxième famille, qui est formée de polynômes de Griffiths de type Racah. Ceux-ci sont orthogonaux. Dans la quatrième partie, on propose une généralisation bivariée des propriétés \(P\)- et \(Q\)-polynomiales pour les schémas d'association et de concepts reliés. Plusieurs exemples de schémas vérifiant la propriété \(P\)-polynomiale bivariée sont obtenus. On montre que les schémas de Johnson non-binaires ainsi que leurs analogues \(q\)-déformés, les schémas définis à partir d'espaces atténués, sont \(P\)- et \(Q\)-polynomiaux bivariés en étudiant les propriétés bispectrales des polynômes bivariés associés. Les structures algébriques reliées à ces schémas sont explorées. On propose aussi une généralisation multivariée des graphes distance-réguliers, et on montre que ceux-ci sont en correspondance avec des schémas \(P\)-polynomiaux multivariés. Finalement, on étudie une sous-classe de paires de Leonard de rang 2 qui font intervenir des polynômes bivariés factorisés. / This thesis is divided in four parts concerning centralizers of quantum algebras \(U_q(\mathfrak{sl}_N)\), biorthogonal polynomials with bispectral properties, bivariate Griffiths polynomials, and association schemes with bivariate polynomial structures. The main topic relating all these parts is the Askey–Wilson algebra. In the first part, the main idea is to combine the braid group algebra with the Askey–Wilson algebra in situations involving the centralizers of the quantum algebra \(U_q(\mathfrak{sl}_2)\). Hence, we obtain representations of the braid group in terms of \(q\)-Racah orthogonal polynomials using \(R\)-matrices of \(U_q(\mathfrak{sl}_2)\), we obtain an interpretation of the Askey–Wilson algebra in the framework of Chern–Simons topological quantum field theory with gauge field \(SU(2)\) as well as in the framework of link invariants associated to \(U_q(\mathfrak{su}_2)\), and we provide a complete algebraic description of the centralizer of \(U_q(\mathfrak{sl}_2)\) in the tensor product of three identical irreducible representations of any spin. In a different perspective, we also provide an algebraic presentation of some fused Hecke algebras, which describe some centralizers of \(U_q(\mathfrak{sl}_N)\). In the second part, we study two families of biorthogonal polynomials using algebraic methods, hence extending the picture that exists for the classical orthogonal polynomials of the Askey–Wilson type. The two families that we consider are the \(R_I\) polynomials of Hahn type and the Pastro polynomials. In both cases, the idea is to introduce a triplet of operators with tridiagonal actions and obtain the polynomials as solutions of two generalized eigenvalue problems involving this triplet. We find the bispectrality and biorthogonality properties of the polynomials using the operators of the triplet, and we determine the algebra realized by the operators. In the third part, we characterize two families of bivariate Griffiths polynomials. The first family is a generalization of the Griffiths polynomials of Krawtchouk type which depends on a parameter \(\lambda\). We find their bispectrality relations and their biorthogonality by using the properties of univariate Krawtchouk polynomials. The contiguity relations of the univariate polynomials play a key role in the computations. We use similar methods to characterize the second family, which is formed by Griffiths polynomials of Racah type. These are orthogonal. In the fourth part, we propose a bivariate generalization of the \(P\)- and \(Q\)-polynomial properties of association schemes and related concepts. Several examples of schemes satisfying the bivariate \(P\)-polynomial property are obtained. We show that the non-binary Johnson schemes and their \(q\)-deformed analogs, the schemes based on attenuated spaces, are bivariate \(P\)- and \(Q\)-polynomial by studying the bispectral properties of the associated bivariate polynomials. The algebraic structures related to these schemes are explored. We also propose a multivariate generalization of distance-regular graphs, and we show that these are in correspondence with multivariate \(P\)-polynomial schemes. Finally, we study a subclass of rank 2 Leonard pairs involving factorized bivariate polynomials.

Ce rapport résume mes activités de recherche depuis l'obtention de mon doctorat. Je me suis penché sur le problème fondamental de l'estimation de signaux sources à partir de l'observation de mesures corrompues de ces signaux, dans des scénarios où les données mesurées peuvent être considérées comme une transformation linéaire inconnue des sources. Deux problèmes classiques de ce type sont la déconvolution ou égalisation de canaux introduisant des distorsions linéaires, et la séparation de sources dans des mélanges linéaires. L'approche dite aveugle essaie d'exploiter un moindre nombre d'hypothèses sur le problème à résoudre : celles-ci se réduisent typiquement à l'indépendance statistique des sources et l'inversibilité du canal ou de la matrice de mélange caractérisant le milieu de propagation. Malgré les avantages qui ont suscité l'intérêt pour ces techniques depuis les années soixante-dix, les critères aveugles présentent aussi quelques inconvénients importants, tels que l'existence d'ambiguïtés dans l'estimation, la présence d'extrema locaux associés à des solutions parasites, et un coût de calcul élevé souvent lié à une convergence lente. Ma recherche s'est consacrée à la conception de nouvelles techniques d'estimation de signal visant à pallier aux inconvénients de l'approche aveugle et donc à améliorer ses performances. Une attention particulière a été portée sur deux applications dans les télécommunications et le génie biomédical : l'égalisation et la séparation de sources dans des canaux de communications numériques, et l'extraction de l'activité auriculaire à partir des enregistrements de surface chez les patients souffrant de fibrillation auriculaire. La plupart des techniques proposées peuvent être considérées comme étant semi-aveugles, dans le sens où elles visent à exploiter des informations a priori sur le problème étudié autres que l'indépendance des sources ; par exemple, l'existence de symboles pilotes dans les systèmes de communications ou des propriétés spécifiques de la source atriale dans la fibrillation auriculaire. Dans les télécommunications, les approches que j'ai explorées incluent des solutions algébriques aux fonctions de contraste basées sur la modulation numérique, la combinaison de contrastes aveugles et supervisés dans des critères semi-aveugles, et une technique d'optimisation itérative basée sur un pas d'adaptation calculé algébriquement. Nos efforts visant à extraire le signal atrial dans des enregistrements de fibrillation auriculaire nous ont permis non seulement de dégager de nouvelles fonctions de contraste basées sur les statistiques de second ordre et d'ordre élevé incorporant l'information a priori sur les statistiques des sources, mais aussi d'aboutir à de nouveaux résultats d'impact clinique et physiologique sur ce trouble cardiaque encore mal compris. Ce rapport se conclut en proposant quelques perspectives pour la continuation de ces travaux. Ces recherches ont été menées en collaboration avec un nombre de collègues en France et à l'étranger, et ont également compris le co-encadrement de plusieurs doctorants. Les contributions qui en ont découlé ont donné lieu à plus de soixante publications dans des journaux, des conférences et des ouvrages collectifs à caractère international. Quelques-unes de ces publications sont jointes à ce document.

Cette thèse d'algèbre commutative porte principalement sur la théorie de la profondeur. Nous nous efforçons d'en fournir une approche épurée d'hypothèse noethérienne dans l'espoir d'échapper aux idéaux premiers et ceci afin de manier des objets élémentaires et explicites. Parmi ces objets, figurent les complexes algébriques de Koszul et de Cech dont nous étudions les propriétés cohomologiques grâce à des résultats simples portant sur la cohomologie du totalisé d'un bicomplexe. Dans le cadre de la cohomologie de Cech, nous avons établi la longue suite exacte de Mayer-Vietoris avec un traitement reposant uniquement sur le maniement des éléments. Une autre notion importante est celle de dimension de Krull. Sa caractérisation en termes de monoïdes bords permet de montrer de manière expéditive le théorème d'annulation de Grothendieck en cohomologie de Cech. Nous fournissons également un algorithme permettant de compléter un polynôme homogène en un h.s.o.p.. La profondeur est intimement liée à la théorie des résolutions libres/projectives finies, en témoigne le théorème de Ferrand-Vasconcelos dont nous rapportons une généralisation due à Jouanolou. Par ailleurs, nous revenons sur des résultats faisant intervenir la profondeur des idéaux caractéristiques d'une résolution libre finie. Nous revisitons, dans un cas particulier, une construction due à Tate permettant d'expliciter une résolution projective totalement effective de l'idéal d'un point lisse d'une hypersurface. Enfin, nous abordons la théorie de la régularité en dimension 1 via l'étude des idéaux inversibles et fournissons un algorithme implémenté en Magma calculant l'anneau des entiers d'un corps de nombres. / This Commutative Algebra thesis focuses mainly on the depth theory. We try to provide an approach without noetherian hypothesis in order to escape prime ideals and to handle only basic and explicit concepts. We study the algebraic complexes of Koszul and Cech and their cohomological properties by using simple results on the cohomology of the totalization of a bicomplex. In the Cech cohomology context we established the long exact sequence of Mayer-Vietoris only with a treatment based on the elements. Another important concept is that of Krull dimension. Its characterization in terms of monoids allows us to show expeditiously the vanishing Grothendieck theorem in Cech cohomology.We also provide an algorithm to complete a omogeneous polynomial in a h.s.o.p.. The depth is closely related to the theory of finite free/projective resolutions. We report a generalization of the Ferrand-Vasconcelos theorem due to Jouanolou. In addition, we review some results involving the depth of the ideals of expected ranks in a finite free resolution.We revisit, in a particular case, a construction due to Tate. This allows us to give an effective projective resolution of the ideal of a point of a smooth hypersurface. Finally, we discuss the regularity theory in dimension 1 by studying invertible ideals and provide an algorithm implemented in Magma computing the ring of integers of a number field.