• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 29
  • 13
  • 2
  • Tagged with
  • 44
  • 22
  • 14
  • 12
  • 8
  • 7
  • 7
  • 7
  • 7
  • 7
  • 7
  • 7
  • 7
  • 7
  • 6
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
31

Irrégularités dans la distribution des nombres premiers et des suites plus générales dans les progressions arithmétiques

Fiorilli, Daniel 08 1900 (has links)
Le sujet principal de cette thèse est la distribution des nombres premiers dans les progressions arithmétiques, c'est-à-dire des nombres premiers de la forme $qn+a$, avec $a$ et $q$ des entiers fixés et $n=1,2,3,\dots$ La thèse porte aussi sur la comparaison de différentes suites arithmétiques par rapport à leur comportement dans les progressions arithmétiques. Elle est divisée en quatre chapitres et contient trois articles. Le premier chapitre est une invitation à la théorie analytique des nombres, suivie d'une revue des outils qui seront utilisés plus tard. Cette introduction comporte aussi certains résultats de recherche, que nous avons cru bon d'inclure au fil du texte. Le deuxième chapitre contient l'article \emph{Inequities in the Shanks-Rényi prime number race: an asymptotic formula for the densities}, qui est le fruit de recherche conjointe avec le professeur Greg Martin. Le but de cet article est d'étudier un phénomène appelé le <<Biais de Chebyshev>>, qui s'observe dans les <<courses de nombres premiers>>. Chebyshev a observé qu'il semble y avoir plus de premiers de la forme $4n+3$ que de la forme $4n+1$. De manière plus générale, Rubinstein et Sarnak ont montré l'existence d'une quantité $\delta(q;a,b)$, qui désigne la probabilité d'avoir plus de premiers de la forme $qn+a$ que de la forme $qn+b$. Dans cet article nous prouvons une formule asymptotique pour $\delta(q;a,b)$ qui peut être d'un ordre de précision arbitraire (en terme de puissance négative de $q$). Nous présentons aussi des résultats numériques qui supportent nos formules. Le troisième chapitre contient l'article \emph{Residue classes containing an unexpected number of primes}. Le but est de fixer un entier $a\neq 0$ et ensuite d'étudier la répartition des premiers de la forme $qn+a$, en moyenne sur $q$. Nous montrons que l'entier $a$ fixé au départ a une grande influence sur cette répartition, et qu'il existe en fait certaines progressions arithmétiques contenant moins de premiers que d'autres. Ce phénomène est plutôt surprenant, compte tenu du théorème des premiers dans les progressions arithmétiques qui stipule que les premiers sont équidistribués dans les classes d'équivalence $\bmod q$. Le quatrième chapitre contient l'article \emph{The influence of the first term of an arithmetic progression}. Dans cet article on s'intéresse à des irrégularités similaires à celles observées au troisième chapitre, mais pour des suites arithmétiques plus générales. En effet, nous étudions des suites telles que les entiers s'exprimant comme la somme de deux carrés, les valeurs d'une forme quadratique binaire, les $k$-tuplets de premiers et les entiers sans petit facteur premier. Nous démontrons que dans chacun de ces exemples, ainsi que dans une grande classe de suites arithmétiques, il existe des irrégularités dans les progressions arithmétiques $a\bmod q$, avec $a$ fixé et en moyenne sur $q$. / The main subject of this thesis is the distribution of primes in arithmetic progressions, that is of primes of the form $qn+a$, with $a$ and $q$ fixed, and $n=1,2,3,\dots$ The thesis also compares different arithmetic sequences, according to their behaviour over arithmetic progressions. It is divided in four chapters and contains three articles. The first chapter is an invitation to the subject of analytic number theory, which is followed by a review of the various number-theoretic tools to be used in the following chapters. This introduction also contains some research results, which we found adequate to include. The second chapter consists of the article \emph{Inequities in the Shanks-Rényi prime number race: an asymptotic formula for the densities}, which is joint work with Professor Greg Martin. The goal of this article is to study <<Chebyshev's Bias>>, a phenomenon appearing in <<prime number races>>. Chebyshev was the first to observe that there tends to be more primes of the form $4n+3$ than of the form $4n+1$. More generally, Rubinstein and Sarnak showed the existence of the quantity $\delta(q;a,b)$, which stands for the probability of having more primes of the form $qn+a$ than of the form $qn+b$. In this paper, we establish an asymptotic series for $\delta(q;a,b)$ which is precise to an arbitrary order of precision (in terms of negative powers of $q$). %(it can be instantiated with an error term smaller than any negative power of $q$). We also provide many numerical results supporting our formulas. The third chapter consists of the article \emph{Residue classes containing an unexpected number of primes}. We fix an integer $a \neq 0$ and study the distribution of the primes of the form $qn+a$, on average over $q$. We show that the choice of $a$ has a significant influence on this distribution, and that some arithmetic progressions contain, on average over q, fewer primes than typical arithmetic progressions. This phenomenon is quite surprising since in light of the prime number theorem for arithmetic progressions, the primes are equidistributed in the residue classes $\bmod q$. The fourth chapter consists of the article \emph{The influence of the first term of an arithmetic progression}. In this article we are interested in studying more general arithmetic sequences and finding irregularities similar to those observed in chapter three. Examples of such sequences are the integers which can be written as the sum of two squares, values of binary quadratic forms, prime $k$-tuples and integers free of small prime factors. We show that a broad class of arithmetic sequences exhibits such irregularities over the arithmetic progressions $a\bmod q$, with $a$ fixed and on average over $q$.
32

On the distribution of the values of arithmetical functions / Sur la répartition des valeurs des fonctions arithmétiques

Hassani, Mehdi 08 December 2010 (has links)
La thèse concerne différents aspects de la répartition des fonctions arithmétiques.1. Deshouillers, Iwaniec et Luca se sont récemment intéressés à la répartition modulo 1 de suites qui sont des valeurs moyennes de fonctions multiplicatives, par exemple phi(n)/n où phi est la fonction d'Euler. Nous étendons leur travail à la densité modulo 1 de suites qui sont des valeurs moyennes sur des suites polynômiales, typiquement n^2+1.2. On sait depuis les travaux de Katai, il y a une quarantaine d'années que la fonction de répartition des valeurs de phi(p-1)/(p-1) (où p parcourt les nombres premiers) est continue, purement singulière, strictement croissante entre 0 et 1/2. On précise cette étude en montrant que cette fonction de répartition a une dérivée infinie à gauche de tout point phi(2n)/(2n). / Abstract
33

Structures linéaires dans les ensembles à faible densité

Henriot, Kevin 07 1900 (has links)
Réalisé en cotutelle avec l'Université Paris-Diderot. / Nous présentons trois résultats en combinatoire additive, un domaine récent à la croisée de la combinatoire, l'analyse harmonique et la théorie analytique des nombres. Le thème unificateur de notre thèse est la détection de structures additives dans les ensembles arithmétiques à faible densité, avec un intérêt particulier pour les aspects quantitatifs. Notre première contribution est une estimation de densité améliorée pour le problème, initié entre autres par Bourgain, de trouver une longue progression arithmétique dans un ensemble somme triple. Notre deuxième résultat consiste en une généralisation des bornes de Sanders pour le théorème de Roth, du cas d'un ensemble dense dans les entiers à celui d'un ensemble à faible croissance additive dans un groupe abélien arbitraire. Finalement, nous étendons les meilleures bornes quantitatives connues pour le théorème de Roth dans les premiers, à tous les systèmes d'équations linéaires invariants par translation et de complexité un. / We present three results in additive combinatorics, a recent field at the interface of combinatorics, harmonic analysis and analytic number theory. The unifying theme in our thesis is the detection of additive structure in arithmetic sets of low density, with an emphasis on quantitative aspects. Our first contribution is an improved density estimate for the problem, initiated by Bourgain and others, of finding a long arithmetic progression in a triple sumset. Our second result is a generalization of Sanders' bounds for Roth's theorem from the dense setting, to the setting of small doubling in an arbitrary abelian group. Finally, we extend the best known quantitative results for Roth's theorem in the primes, to all translation-invariant systems of equations of complexity one.
34

Déformation des extensions peu ramifiées en P / Deformation extensions slightly branched P

Blondeau, Julien 17 June 2011 (has links)
Déformation des extensions peu ramifiées en P / Deformation extensions slightly branched P
35

Adaptation du modèle de la Construction-Intégration de Kintsch à la compréhension des énoncés et à la résolution des problèmes arithmétiques complexes / Understanding and solving complex word arithmetic problems : adaptation of the Construction-Integration model of Kintsch

Lebreton, Olivier 21 January 2011 (has links)
Cette recherche a pour objet la compréhension des énoncés de problèmes arithmétiques complexes et leur résolution. Les problèmes complexes choisis combinent des problèmes simples de types Changement et Combinaison. Ce travail s’appuie sur le modèle de la Construction-Intégration de Kintsch. Les résultats montrent qu’il existe une relation entre le niveau d’expertise en compréhension de textes narratifs et la résolution des problèmes arithmétiques complexes. Comprendre un texte narratif ou un énoncé de problème complexe exige de la part des lecteurs la construction d’un réseau propositionnel hiérarchisé et les résultats suggèrent, entre autres, une sensibilité des élèves aux propositions textuelles et aux ellipses contenues dans les textes. La formation des macropropositions est un processus fondamental et les résultats montrent une relation entre le nombre d’objets contenus dans les énoncés de problème et la procédure préférentiellement choisie par les élèves. Ils suggèrent d’une part, la mise en oeuvre du processus de catégorisation au cours du processus de compréhension et d’autre part, l’affaiblissement des liaisons entre les macropropositions élaborées et le schéma de problème Parties-Tout qui leur sont liés. D’un point de vue pédagogique, les résultats montrent que les questions relatives à l’activation d’une part des concepts superordonnés et d’autre part des schémas de problèmes Parties-Tout ne sont pas à privilégier pour aider les élèves. Finalement, les connaissances du lecteur sont essentielles à la compréhension. Cet élément est confirmé ici et la compréhension des problèmes complexes nécessite des connaissances solides relativement aux problèmes arithmétiques simples. / This research deals with text comprehension processes and complex arithmetic word problems resolution by 9-10 years old children in Reunion Island based upon the CI model of Kintsch. The complex word arithmetic problems used in this research are a combination of Change simple problems and Combine simple problems. The results show a relation between subject’s level of expertise in narrative texts comprehension and complex arithmetic word problems resolution. In order to understand a narrative text or to resolve a complex arithmetic word problem, subjects have to elaborate a coherent hierarchical propositional network : bridging inferences and macropropositions are involved to achieve complex arithmetic word problems resolution too. More precisely, the results suggest children are sensitive to the number of propositions and to the ellipsises. Macropropositions formation is an integral process of reading. The results show a relation between number of objects in complex arithmetic problems and procedure naturally used by children to solve them. They suggest on the one hand, categorization processes are an integral part of reading and on the other hand, some links between macropropositions and arithmetic hypothesis become weaker. Consequently, questions about superordinate concepts and arithmetic hypothesis attached to them are not helpul to resolve complex arithmetic word problems. Finally, reader’s knowlegde is a key element of comprehension processes and to achieve complex arithmetic word problems, problem schemata about simple arithmetic word problems are crucial. The results show a relation between subject’s level of expertise in simple arithmetic word problems and complex arithmetic word problems resolution.
36

Unités arithmétiques et cryptoprocesseurs matériels pour la cryptographie sur courbe hyperelliptique / Hardware arithmetic units and cryptoprocessors for hyperelliptic curve cryptography

Gallin, Gabriel 29 November 2018 (has links)
De nombreux systèmes numériques nécessitent des primitives de cryptographie asymétrique de plus en plus performantes mais aussi robustes aux attaques et peu coûteuses pour les applications embarquées. Dans cette optique, la cryptographie sur courbe hyperelliptique (HECC) a été proposée comme une alternative intéressante aux techniques actuelles du fait de corps finis plus petits. Nous avons étudié des cryptoprocesseurs HECC matériels performants, flexibles et robustes contre certaines attaques physiques. Tout d’abord, nous avons proposé une nouvelle architecture d’opérateurs exécutant, en parallèle, plusieurs multiplications modulaires (A × B) mod P, où P est un premier générique de quelques centaines de bits et configurable dynamiquement. Elle permet le calcul de la grande majorité des opérations nécessaires pour HECC. Nous avons développé un générateur d’opérateurs, distribué en logiciel libre, pour l'exploration de nombreuses variantes de notre architecture. Nos meilleurs opérateurs sont jusqu'à 2 fois plus petits et 2 fois plus rapids que les meilleures solutions de l'état de l'art. Ils sont aussi flexibles quant au choix de P et atteignent les fréquences maximales du FPGA. Dans un second temps, nous avons développé des outils de modélisation et de simulation pour explorer, évaluer et valider différentes architectures matérielles pour la multiplication scalaire dans HECC sur les surfaces de Kummer. Nous avons implanté, validé et évalué les meilleures architectures sur différents FPGA. Elles atteignent des vitesses similaires aux meilleures solutions comparables de l’état de l’art, mais pour des surfaces réduites de moitié. La flexibilité obtenue permet de modifier lors de l'exécution les paramètres des courbes utilisées. / Many digital systems require primitives for asymmetric cryptography that are more and more efficient but also robust to attacks and inexpensive for embedded applications. In this perspective, and thanks to smaller finite fields, hyperelliptic curve cryptography (HECC) has been proposed as an interesting alternative to current techniques. We have studied efficient and flexible hardware HECC cryptoprocessors that are also robust against certain physical attacks. First, we proposed a new operator architecture able to compute, in parallel, several modular multiplications (A × B) mod P, where P is a generic prime of a few hundred bits and configurable at run time. It allows the computation of the vast majority of operations required for HECC. We have developed an operator generator, distributed in free software, for the exploration of many variants of our architecture. Our best operators are up to 2 times smaller and twice as fast as the best state-of-the-art solutions. They are also flexible in the choice of P and reach the maximum frequencies of the FPGA. In a second step, we developed modeling and simulation tools to explore, evaluate and validate different hardware architectures for scalar multiplication in HECC on Kummer surfaces. We have implemented, validated and evaluated the best architectures on various FPGA. They reach speeds similar to the best comparable solutions of the state of the art, but for halved surfaces. The flexibility obtained makes it possible to modify the parameters of the curves used during execution.
37

Adaptation du modèle de la Construction-Intégration de Kintsch à la compréhension des énoncés et à la résolution des problèmes arithmétiques complexes

Lebreton, Olivier 21 January 2011 (has links) (PDF)
Cette recherche a pour objet la compréhension des énoncés de problèmes arithmétiques complexes et leur résolution. Les problèmes complexes choisis combinent des problèmes simples de types Changement et Combinaison. Ce travail s'appuie sur le modèle de la Construction-Intégration de Kintsch. Les résultats montrent qu'il existe une relation entre le niveau d'expertise en compréhension de textes narratifs et la résolution des problèmes arithmétiques complexes. Comprendre un texte narratif ou un énoncé de problème complexe exige de la part des lecteurs la construction d'un réseau propositionnel hiérarchisé et les résultats suggèrent, entre autres, une sensibilité des élèves aux propositions textuelles et aux ellipses contenues dans les textes. La formation des macropropositions est un processus fondamental et les résultats montrent une relation entre le nombre d'objets contenus dans les énoncés de problème et la procédure préférentiellement choisie par les élèves. Ils suggèrent d'une part, la mise en oeuvre du processus de catégorisation au cours du processus de compréhension et d'autre part, l'affaiblissement des liaisons entre les macropropositions élaborées et le schéma de problème Parties-Tout qui leur sont liés. D'un point de vue pédagogique, les résultats montrent que les questions relatives à l'activation d'une part des concepts superordonnés et d'autre part des schémas de problèmes Parties-Tout ne sont pas à privilégier pour aider les élèves. Finalement, les connaissances du lecteur sont essentielles à la compréhension. Cet élément est confirmé ici et la compréhension des problèmes complexes nécessite des connaissances solides relativement aux problèmes arithmétiques simples.
38

Conception et développement de circuits logiques de faible consommation et fiables basés sur des jonctions tunnel magnétiques à écriture par transfert de spin / Design and development of low-power and reliable logic circuits based on spin-transfer torque magnetic tunnel junctions

Deng, Erya 10 February 2017 (has links)
Avec la diminution du nœud de la technologie CMOS, la puissance statique et dynamique augmente spectaculairement. It est devenu l'un des principaux problèmes en raison de l'augmentation du courant de fuite et de la longue distance entre les mémoires et les circuits logiques. Au cours des dernières décennies, les dispositifs de spintronique, tels que la jonction tunnel magnétique (JTM) écrit par transfert de spin, sont largement étudiés pour résoudre le problème de la puissance statique grâce à leur non-volatilité. L'architecture logic-in-memory (LIM) hybride permet de fabriquer les dispositifs de spintronique au-dessus des circuits CMOS, réduisant le temps de transfert et la puissance dynamique. Cette thèse vise à la conception de circuits logiques et mémoires pour le système de faible puissance, en combinant les technologies JTM et CMOS. En utilisant un modèle compact JTM et le design-kit CMOS de STMicroelectronics, nous étudions les circuits hybrides MTJ/CMOS de 1-bit et multi-bit, y compris les opérations de lecture et d'écriture. Les méthodes d'optimisation sont également introduites pour améliorer la fiabilité, ce qui est extrêmement important pour les circuits logiques où les blocs de correction d'erreur ne peuvent pas être facilement intégrés sans sacrifier leurs performances ou augmenter la surface de circuit. Nous étendons la structure MTJ/CMOS hybride de multi-bit à la conception d’une mémoire MRAM avec les circuits périphériques simples. Basés sur le concept de LIM, les circuits logiques/arithmétiques non-volatiles sont conçus. Les JTMs sont intégrés non seulement comme des éléments de stockage, mais aussi comme des opérandes logiques. Tout d'abord, nous concevons et analysons théoriquement les portes logiques non-volatiles (PLNVs) comprenant NOT, AND, OR et XOR. Ensuite, les additionneurs complets non-volatiles (ACNVs) de 1-bit et 8-bit sont proposés et comparés avec l'additionneur classique basé sur la technologie CMOS. Nous étudions l'effet de la taille de transistor CMOS et des paramètres de JMT sur les performances d’ACNV. De plus, nous optimisons l’ACNV sous deux faces. Premièrement, un circuit de détection (mode de tension) de très haute fiabilité est proposé. Après, nous proposons de remplacer le JTM à deux électrodes par un JTM à trois électrodes (écrit par transfert de spin assisté par l’effet Hall de spin) en raison du temps d'écriture et de la puissance plus petit. Basé sur les PLNVs et ACNVs, d'autres circuits logiques peuvent être construits, par exemple, soustracteur non-volatile. Enfin, une mémoire adressable par contenu non-volatile (MACNV) est proposée. Deux décodeurs magnétiques visent à sélectionner des lignes et à enregistrer la position de recherche dans un état non-volatile. / With the shrinking of CMOS (complementary metal oxide semi-conductor) technology, static and dynamic power increase dramatically and indeed has become one of the main challenges due to the increasing leakage current and long transfer distance between memory and logic chips. In the past decades, spintronics devices, such as spin transfer torque based magnetic tunnel junction (STT-MTJ), are widely investigated to overcome the static power issue thanks to their non-volatility. Hybrid logic-in-memory (LIM) architecture allows spintronics devices to be fabricated over the CMOS circuit plane, thereby reducing the transfer latency and the dynamic power dissipation. This thesis focuses on the design of hybrid MTJ/CMOS logic circuits and memories for low-power computing system.By using a compact MTJ model and the STMicroelectronics design kit for regular CMOS design, we investigate the hybrid MTJ/CMOS circuits for single-bit and multi-bit reading and writing. Optimization methods are also introduced to improve the reliability, which is extremely important for logic circuits where error correction blocks cannot be easily embedded without sacrificing their performances or adding extra area to the circuit. We extend the application of multi-context hybrid MTJ/CMOS structure to the memory design. Magnetic random access memory (MRAM) with simple peripheral circuits is designed.Based on the LIM concept, non-volatile logic/arithmetic circuits are designed to integrate MTJs not only as storage elements but also as logic operands. First, we design and theoretically analyze the non-volatile logic gates (NVLGs) including NOT, AND, OR and XOR. Then, 1-bit and 8-bit non-volatile full-adders (NVFAs), the basic elements for arithmetic operations, are proposed and compared with the traditional CMOS-based full-adder. The effect of CMOS transistor sizing and the MTJ parameters on the performances of NVFA is studied. Furthermore, we optimize the NVFA from two levels. From the structure-level, an ultra-high reliability voltage-mode sensing circuit is used to store the operand of NVFA. From the device-level, we propose 3-terminal MTJ switched by spin-Hall-assisted STT to replace the 2-terminal MTJ because of its smaller writing time and power consumption. Based on the NVLGs and NVFAs, other logic circuits can be built, for instance, non-volatile subtractor.Finally, non-volatile content addressable memory (NVCAM) is proposed. Two magnetic decoders aim at selecting a word line to be read or written and saving the corresponding search location in non-volatile state.
39

Implantations et protections de mécanismes cryptographiques logiciels et matériels / Implementations and protections of software and hardware cryptographic mechanisms

Cornelie, Marie-Angela 12 April 2016 (has links)
La protection des mécanismes cryptographiques constitue un enjeu important lors du développement d'un système d'information car ils permettent d'assurer la sécurisation des données traitées. Les supports utilisés étant à la fois logiciels et matériels, les techniques de protection doivent s'adapter aux différents contextes.Dans le cadre d'une cible logicielle, des moyens légaux peuvent être mis en oeuvre afin de limiter l'exploitation ou les usages. Cependant, il est généralement difficile de faire valoir ses droits et de prouver qu'un acte illicite a été commis. Une alternative consiste à utiliser des moyens techniques, comme l'obscurcissement de code, qui permettent de complexifier les stratégies de rétro-conception en modifiant directement les parties à protéger.Concernant les implantations matérielles, on peut faire face à des attaques passives (observation de propriétés physiques) ou actives, ces dernières étant destructives. Il est possible de mettre en place des contre-mesures mathématiques ou matérielles permettant de réduire la fuite d'information pendant l'exécution de l'algorithme, et ainsi protéger le module face à certaines attaques par canaux cachés.Les travaux présentés dans ce mémoire proposent nos contributions sur ces sujets tes travaux. Nous étudions et présentons les implantations logicielle et matérielle réalisées pour le support de courbes elliptiques sous forme quartique de Jacobi étendue. Ensuite, nous discutons des problématiques liées à la génération de courbes utilisables en cryptographie et nous proposons une adaptation à la forme quartique de Jacobi étendue ainsi que son implantation. Dans une seconde partie, nous abordons la notion d'obscurcissement de code source. Nous détaillons les techniques que nous avons implantées afin de compléter un outil existant ainsi que le module de calcul de complexité qui a été développé. / The protection of cryptographic mechanisms is an important challenge while developing a system of information because they allow to ensure the security of processed data. Since both hardware and software supports are used, the protection techniques have to be adapted depending on the context.For a software target, legal means can be used to limit the exploitation or the use. Nevertheless, it is in general difficult to assert the rights of the owner and prove that an unlawful act had occurred. Another alternative consists in using technical means, such as code obfuscation, which make the reverse engineering strategies more complex, modifying directly the parts that need to be protected.Concerning hardware implementations, the attacks can be passive (observation of physical properties) or active (which are destructive). It is possible to implement mathematical or hardware countermeasures in order to reduce the information leakage during the execution of the code, and thus protect the module against some side channel attacks.In this thesis, we present our contributions on theses subjects. We study and present the software and hardware implementations realised for supporting elliptic curves given in Jacobi Quartic form. Then, we discuss issues linked to the generation of curves which can be used in cryptography, and we propose an adaptation to the Jacobi Quartic form and its implementation. In a second part, we address the notion of code obfuscation. We detail the techniques that we have implemented in order to complete an existing tool, and the complexity module which has been developed.
40

Efficient computation with structured matrices and arithmetic expressions / Calcul efficace avec des matrices structurées et des expressions arithmétiques

Mouilleron, Christophe 04 November 2011 (has links)
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.

Page generated in 0.4067 seconds