Spelling suggestions: "subject:"réseau euclidien"" "subject:"réseau euclidiens""
1 |
Évaluation efficace de fonctions numériques - Outils et exemplesChevillard, Sylvain 06 July 2009 (has links) (PDF)
Les systèmes informatiques permettent d'évaluer des fonctions numériques telles que f = exp, sin, arccos, etc. Cette thèse s'intéresse au processus d'implémentation de ces fonctions. Suivant la cible visée (logiciel ou matériel, faible ou grande précision), les problèmes qui se posent sont différents, mais l'objectif est toujours d'obtenir l'implémentation la plus efficace possible. Nous étudions d'abord, à travers un exemple, les problèmes qui se posent dans le cas où la précision est arbitraire. Lorsque, à l'inverse, la précision est connue d'avance, la fonction f est souvent remplacée par un polynôme d'approximation p. Un tel polynôme peut ensuite être évalué très efficacement en machine. En pratique, les coefficients de p doivent être représentables sur un nombre fini donné de bits. Nous proposons un ensemble d'algorithmes (certains sont heuristiques, d'autres rigoureux) pour trouver de très bons polynômes d'approximation répondant à cette contrainte. Ces résultats s'étendent au cas où la fonction d'approximation est une fraction rationnelle. Une fois p trouvé, il faut prouver que l'erreur |p-f| n'excède pas un certain seuil. La nature particulière de la fonction p-f (soustraction de deux fonctions très proches) rend cette propriété difficile à prouver rigoureusement. Nous proposons un algorithme capable de contourner cette difficulté. Tous ces algorithmes ont été intégrés au logiciel Sollya, développé pendant la thèse. À l'origine conçu pour faciliter l'implémentation de fonctions, ce logiciel s'adresse à présent à toute personne souhaitant faire des calculs numériques dans un cadre complètement fiable.
|
2 |
Sur la hauteur de tores plats / On the height of Flat ToriLazzarini, Giovanni 19 February 2015 (has links)
Nous considérons la fonction zêta d’Epstein des réseaux euclidiens pour étudier le problème des minima de la hauteur du tore plat associé à un réseau. La hauteur est définie comme la dérivée au point s = 0 de la fonction zêta spectrale du tore, fonction qui coïncide, à un facteur près, avec la fonction zêta d’Epstein du réseau dual du réseau donné. Nous donnons dans cette dissertation une condition suffisante pour qu’un réseau donné soit un point critique de la hauteur. En particulier, en utilisant la théorie des designs sphériques, nous montrons qu’un réseau qui a des 2-designs sphériques sur toutes ses couches est un point critique de la hauteur. Nous donnons un algorithme pour tester si un réseau donné satisfait cette condition de 2-designs, et nous donnons des tables de résultats en dimension jusqu’à 7. Ensuite, nous montrons qu’un réseau qui réalise un minimum local de la hauteur est nécessairement irréductible. Enfin, nous nous intéressons à certains tores définis sur les corps de nombres quadratiques imaginaires, et nous prouvons une formule qui donne leur hauteur comme limite d’une suite de hauteurs de tores complexes discrets. / In this thesis we consider the Epstein zeta function of Euclidean lattices, in order to study the problem of the minima of the height of the flat torus associated to a lattice. The height is defined as the first derivative at the point s = 0 of the spectral zeta function of the torus ; this function coincides, up to a factor, with the Epstein zeta function of the dual lattice of the given lattice. We describe a sufficient condition for a given lattice to be a stationary point of the height. In particular, by means of the theory of spherical designs, we show that a lattice which has a spherical 2-design on every shell is a stationary point of the height. We give an algorithm to check whether a given lattice satisfies this 2-design condition or not, and we give some tables of results in dimension up to 7. Then, we show that a lattice which realises a local minimum of the height is necessarily irreducible. Finally, we deal with some tori defined over the imaginary quadratic number fields, and we show a formula which gives their height as a limit of a sequence of heights of discrete complex tori.
|
3 |
Robust tools for weighted Chebyshev approximation and applications to digital filter design / Outils robustes pour l’approximation de Chebyshev pondérée et applications à la synthèse de filtres numériquesFilip, Silviu-Ioan 07 December 2016 (has links)
De nombreuses méthodes de traitement du signal reposent sur des résultats puissants d'approximation numérique. Un exemple significatif en est l'utilisation de l'approximation de type Chebyshev pour l'élaboration de filtres numériques.En pratique, le caractère fini des formats numériques utilisés en machine entraîne des difficultés supplémentaires pour la conception de filtres numériques (le traitement audio et le traitement d'images sont deux domaines qui utilisent beaucoup le filtrage). La majorité des outils actuels de conception de filtres ne sont pas optimisés et ne certifient pas non plus la correction de leurs résultats. Notre travail se veut un premier pas vers un changement de cette situation.La première partie de la thèse traite de l'étude et du développement de méthodes relevant de la famille Remez/Parks-McClellan pour la résolution de problèmes d'approximation polynomiale de type Chebyshev, en utilisant l'arithmétique virgule-flottante.Ces approches sont très robustes, tant du point de vue du passage à l'échelle que de la qualité numérique, pour l'élaboration de filtres à réponse impulsionnelle finie (RIF).Cela dit, dans le cas des systèmes embarqués par exemple, le format des coefficients du filtre qu'on utilise en pratique est beaucoup plus petit que les formats virgule flottante standard et d'autres approches deviennent nécessaires.Nous proposons une méthode (quasi-)optimale pour traîter ce cas. Elle s'appuie sur l'algorithme LLL et permet de traiter des problèmes de taille bien supérieure à ceux que peuvent traiter les approches exactes. Le résultat est ensuite utilisé dans une couche logicielle qui permet la synthèse de filtres RIF pour des circuits de type FPGA.Les résultats que nous obtenons en sortie sont efficaces en termes de consommation d'énergie et précis. Nous terminons en présentant une étude en cours sur les algorithmes de type Remez pour l'approximation rationnelle. Ce type d'approches peut être utilisé pour construire des filtres à réponse impulsionnelle infinie (RII) par exemple. Nous examinons les difficultés qui limitent leur utilisation en pratique. / The field of signal processing methods and applications frequentlyrelies on powerful results from numerical approximation. One suchexample, at the core of this thesis, is the use of Chebyshev approximationmethods for designing digital filters.In practice, the finite nature of numerical representations adds an extralayer of difficulty to the design problems we wish to address using digitalfilters (audio and image processing being two domains which rely heavilyon filtering operations). Most of the current mainstream tools for thisjob are neither optimized, nor do they provide certificates of correctness.We wish to change this, with some of the groundwork being laid by thepresent work.The first part of the thesis deals with the study and development ofRemez/Parks-McClellan-type methods for solving weighted polynomialapproximation problems in floating-point arithmetic. They are veryscalable and numerically accurate in addressing finite impulse response(FIR) design problems. However, in embedded and power hungry settings,the format of the filter coefficients uses a small number of bits andother methods are needed. We propose a (quasi-)optimal approach basedon the LLL algorithm which is more tractable than exact approaches.We then proceed to integrate these aforementioned tools in a softwarestack for FIR filter synthesis on FPGA targets. The results obtainedare both resource consumption efficient and possess guaranteed accuracyproperties. In the end, we present an ongoing study on Remez-type algorithmsfor rational approximation problems (which can be used for infinite impulseresponse (IIR) filter design) and the difficulties hindering their robustness.
|
Page generated in 0.0473 seconds