L'arithmétique par intervalles permet de calculer et simultanément vérifier des résultats. Cependant, une application naïve de cette arithmétique conduit à un encadrement grossier des résultats. De plus, de tels calculs peuvent être lents.Nous proposons des algorithmes précis et des implémentations efficaces, utilisant l'arithmétique par intervalles, dans le domaine de l'algèbre linéaire. Deux problèmes sont abordés : la multiplication de matrices à coefficients intervalles et la résolution vérifiée de systèmes linéaires. Pour le premier problème, nous proposons deux algorithmes qui offrent de bons compromis entre vitesse et précision. Pour le second problème, nos principales contributions sont d'une part une technique de relaxation, qui réduit substantiellement le temps d'exécution de l'algorithme, et d'autre part l'utilisation d'une précision étendue en quelques portions bien choisies de l'algorithme, afin d'obtenir rapidement une grande précision. / Interval arithmetic is a means to compute verified results. However, a naive use of interval arithmetic does not provide accurate enclosures of the exact results. Moreover, interval arithmetic computations can be time-consuming. We propose several accurate algorithms and efficient implementations in verified linear algebra using interval arithmetic. Two fundamental problems are addressed, namely the multiplication of interval matrices and the verification of a floating-point solution of a linear system. For the first problem, we propose two algorithms which offer new tradeoffs between speed and accuracy. For the second problem, which is the verification of the solution of a linear system, our main contributions are twofold. First, we introduce a relaxation technique, which reduces drastically the execution time of the algorithm. Second, we propose to use extended precision for few, well-chosen parts of the computations, to gain accuracy without losing much in term of execution time.

Le développement de code efficace en pratique pour effectuer un calcul donné est un problème difficile. Cette thèse présente deux situations où nous avons été confronté à ce problème. La première partie de la thèse propose des améliorations au niveau algorithmique dans le cadre de l'algèbre linéaire structurée. Nous montrons d'abord comment étendre un algorithme de Cardinal pour l'inversion de matrices de type Cauchy afin de traiter les autres structures classiques. Cette approche, qui repose essentiellement sur des produits de type « matrice structurée × matrice », conduit à une accélération d'un facteur allant jusqu'à 7 en théorie et constaté en pratique. Ensuite, nous généralisons des travaux sur les matrices de type Toeplitz afin de montrer comment, pour les structures classiques, calculer le produit d'une matrice structurée n×n et de rang de déplacement α par une matrice n×α en Õ(α^(ω-1)n). Cela conduit à des algorithmes en Õ(α^(ω-1)n) pour l'inversion de matrices structurées, sans avoir à passer par des matrices de type Toeplitz. La deuxième partie de la thèse traite de l'implantation d'expressions arithmétiques. Ce sujet soulève de nombreuses questions comme le nombre d'opérations minimum, la vitesse, ou encore la précision des calculs en arithmétique approchée. En exploitant la nature inductive des expressions arithmétiques, il est possible de développer des algorithmes aidant à répondre à ces questions. Nous présentons ainsi plusieurs algorithmes de génération de schémas d'évaluation, de comptage et d'optimisation selon un ou plusieurs critères. Ces algorithmes ont été implanté dans une librairie qui a en autre été utilisée pour accélérer un logiciel de génération de code pour une librairie mathématique, et pour étudier des questions d'optimalité pour le problème de l'évaluation d'un polynôme à coefficients scalaires de petit degré en une matrice. / Designing efficient code in practice for a given computation is a hard task. In this thesis, we tackle this issue in two different situations. The first part of the thesis introduces some algorithmic improvements in structured linear algebra. We first show how to extend an algorithm by Cardinal for inverting Cauchy-like matrices to the other common structures. This approach, which mainly relies on products of the type "structured matrix × matrix", leads to a theoretical speed-up of a factor up to 7 that we also observe in practice. Then, we extend some works on Toeplitz-like matrices and prove that, for any of the common structures, the product of an n×n structured matrix of displacement rank α by an n×α matrix can be computed in Õ(α^(ω-1)n). This leads to direct inversion algorithms in Õ(α^(ω-1)n) , that do not rely on a reduction to the Toeplitz-like case. The second part of the thesis deals with the implementation of arithmetic expressions. This topic raises several issues like finding the minimum number of operations, and maximizing the speed or the accuracy when using some finite-precision arithmetic. Making use of the inductive nature of arithmetic expressions enables the design of algorithms that help to answer such questions. We thus present a set of algorithms for generating evaluation schemes, counting them, and optimizing them according to one or several criteria. These algorithms are part of a library that we have developed and used, among other things, in order to decrease the running time of a code generator for a mathematical library, and to study optimality issues about the evaluation of a small degree polynomial with scalar coefficients at a matrix point.

L'objet est de comparer des algorithmes de multiplication de matrices à coefficients intervalles et leurs implémentations.Le premier axe est la mesure de la précision numérique. Les précédentes analyses d'erreur se limitent à établir une borne sur la surestimation du rayon du résultat en négligeant les erreurs dues au calcul en virgule flottante. Après examen des différentes possibilités pour quantifier l'erreur d'approximation entre deux intervalles, l'erreur d'arrondi est intégrée dans l'erreur globale. À partir de jeux de données aléatoires, la dispersion expérimentale de l'erreur globale permet d'éclairer l'importance des différentes erreurs (de méthode et d'arrondi) en fonction de plusieurs facteurs : valeur et homogénéité des précisions relatives des entrées, dimensions des matrices, précision de travail. Cette démarche conduit à un nouvel algorithme moins coûteux et tout aussi précis dans certains cas déterminés.Le deuxième axe est d'exploiter le parallélisme des opérations. Les implémentations précédentes se ramènent à des produits de matrices de nombres flottants. Pour contourner les limitations d'une telle approche sur la validité du résultat et sur la capacité à monter en charge, je propose une implémentation par blocs réalisée avec des threads OpenMP qui exécutent des noyaux de calcul utilisant les instructions vectorielles. L'analyse des temps d'exécution sur une machine de 4 octo-coeurs montre que les coûts de calcul sont du même ordre de grandeur sur des matrices intervalles et numériques de même dimension et que l'implémentation par bloc passe mieux à l'échelle que l'implémentation avec plusieurs appels aux routines BLAS. / This work aims at determining suitable scopes for several algorithms of interval matrices multiplication.First, we quantify the numerical quality. Former error analyses of interval matrix products establish bounds on the radius overestimation by neglecting the roundoff error. We discuss here several possible measures for interval approximations. We then bound the roundoff error and compare experimentally this bound with the global error distribution on several random data sets. This approach enlightens the relative importance of the roundoff and arithmetic errors depending on the value and homogeneity of relative accuracies of inputs, on the matrix dimension, and on the working precision. This also leads to a new algorithm that is cheaper yet as accurate as previous ones under well-identified conditions.Second, we exploit the parallelism of linear algebra. Previous implementations use calls to BLAS routines on numerical matrices. We show that this may lead to wrong interval results and also restrict the scalability of the performance when the core count increases. To overcome these problems, we implement a blocking version with OpenMP threads executing block kernels with vector instructions. The timings on a 4-octo-core machine show that this implementation is more scalable than the BLAS one and that the cost of numerical and interval matrix products are comparable.

Dans cette thèse, on présente la théorie algébrique IH par le biais de générateurs et d’équations.Le modèle libre de IH est la catégorie des sous-espaces linéaires sur un corps k. Les termes de IH sont des diagrammes de cordes, qui, selon le choix de k, peuvent exprimer différents types de réseaux et de formalismes graphiques, que l’on retrouve dans des domaines scientifiques divers, tels que les circuits quantiques, les circuits électriques et les réseaux de Petri. Les équations de IH sont obtenues via des lois distributives entre algèbres de Hopf – d’où le nom “Interacting Hopf algebras” (algèbres de Hopf interagissantes). La caractérisation via les sous-espaces permet de voir IH comme une syntaxe fondée sur les diagrammes de cordes pour l’algèbre linéaire: les applications linéaires, les espaces et leurs transformations ont chacun leur représentation fidèle dans le langage graphique. Cela aboutit à un point de vue alternatif, souvent fructueux, sur le domaine.On illustre cela en particulier en utilisant IH pour axiomatiser la sémantique formelle de circuits de calculs de signaux, pour lesquels on s’intéresse aux questions de la complète adéquation et de la réalisabilité. Notre analyse suggère un certain nombre d’enseignements au sujet du rôle de la causalité dans la sémantique des systèmes de calcul. / We present by generators and equations the algebraic theory IH whose free model is the category oflinear subspaces over a field k. Terms of IH are string diagrams which, for different choices of k, expressdifferent kinds of networks and graphical formalisms used by scientists in various fields, such as quantumcircuits, electrical circuits and Petri nets. The equations of IH arise by distributive laws between Hopfalgebras - from which the name interacting Hopf algebras. The characterisation in terms of subspacesallows to think of IH as a string diagrammatic syntax for linear algebra: linear maps, spaces and theirtransformations are all faithfully represented in the graphical language, resulting in an alternative, ofteninsightful perspective on the subject matter. As main application, we use IH to axiomatise a formalsemantics of signal processing circuits, for which we study full abstraction and realisability. Our analysissuggests a reflection about the role of causality in the semantics of computing devices.

Cette thèse présente une méthode de résolution parallèle de systèmes linéaires creux qui combine efficacement les techniques de résolutions directes et itératives en utilisant une approche de type complément de Schur. Nous construisons une décomposition de domaine. L'intérieur des sous-domaines est éliminé de manière directe pour se ramener à un problème sur l'interface. Ce problème est résolu grâce à une méthode itérative préconditionnée par une factorisation incomplète. Un réordonnancement de l'interface permet la construction d'un préconditionneur global du complément de Schur. Des algorithmes minimisant le pic mémoire de la construction du préconditionneur sont proposés. Nous exploitons un schéma d'équilibrage de charge utilisant une répartition de multiples sous-domaines sur les processeurs. Les méthodes sont implémentées dans le solveur HIPS et des résultats expérimentaux parallèles sont présentés sur de grands cas tests industriels. / This thesis presents a parallel resolution method for sparse linear systems which combines effectively techniques of direct and iterative solvers using a Schur complement approach. A domain decomposition is built ; the interiors of the subdomains are eliminated by a direct method in order to use an iterative method only on the interface unknowns. The system on the interface (Schur complement) is solved thanks to an iterative method preconditioned by a global incomplete factorization. A special ordering on the Schur complement allows to build a scalable preconditioner. Algorithms minimizing the memory peak that appears during the construction of the preconditioner are presented. The memory is balanced thanks to a multiple domains per processors parallelization scheme. The methods are implemented in the HIPS solver and parallel experimental results are presented on large industrial test cases.

Le calcul scientifique est souvent associé au calcul numérique. Pourtant dans de nombreuses disciplines scientifiques il est nécessaire d'aller au-delà du calcul approché : nécessité de certification des résultats, calculs dans des structures mathématiques discrètes, instabilité des algorithmique numériques. Le calcul exact s'attache donc à donner des résultats exacts ou certifiés. Cependant, la principale obstruction à l'utilisation du Calcul Formel est bien souvent les faibles performances des systèmes commerciaux y compris pour les opérations fondamentales comme l'algèbre linéaire. L'objectif de ces travaux est donc de réduire l'écart entre le calcul exact et le calcul numérique, tant sur le plan algorithmique, que sur le plan logiciel. Les défis sont multiples : développer une arithmétique efficace dans les structures discrètes ; concevoir des algorithmes ayant un terme dominant de complexité optimal même en tenant compte de la croissance des données intermédiaires ; transcrire ces algorithmes dans des logiciels combinant efficacité pérenne, interfaçage et généricité.

Le problème de la factorisation et celui du logarithme discret sont deux fondements essentiels de nombreux algorithmes de la cryptographie à clé publique. Dans le champ des algorithmes pour attaquer ces problèmes éminemment ardus, le crible algébrique et ses algorithmes cousins occupent une place de première importance. La première partie de ce mémoire est consacrée à la présentation de la " famille " du crible algébrique, et à plusieurs de mes contributions dans ce domaine. D'autres travaux sont abordés dans la partie suivante, notamment en lien avec le problème du logarithme discret sur les jacobiennes de courbes, et à ma contribution à de nouveaux algorithmes pour ce problème dans certains cas particuliers. La partie 3 du mémoire aborde mes travaux sur le thème de l'algèbre linéaire creuse sur les corps finis, motivés par le contexte d'application des algorithmes précédemment cités. La partie 4, enfin, traite de mes travaux dans le domaine de l'arithmétique, notamment concernant l'arithmétique des polynômes sur GF(2). La proximité des travaux apparaissant dans ces parties 3 et 4 avec des problématiques d'implantation indique le souci permanent, dans mes travaux, de ne pas laisser de côté cet aspect.

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.