Spelling suggestions: "subject:"algorithme rapide"" "subject:"algorithme rapidement""
1 |
Algorithmique semi-numérique rapide des séries de TchebychevBenoit, Alexandre 18 July 2012 (has links) (PDF)
Une série de Tchebychev est un développement dans la base des polynômes de Tchebychev. Ces séries sont importantes en théorie de l'approximation. Contrairement aux séries de Taylor, l'algorithmique en calcul formel autour d'elles n'est pas très développée. Cette thèse propose de nouveaux algorithmes pour ces séries. Une première partie présente des algorithmes rapides pour convertir une série de Tchebychev tronquée en une série de Taylor tronquée et réciproquement, et pour multiplier ou diviser deux séries de Tchebychev tronquées. Le reste de la thèse porte sur les séries de Tchebychev solutions d'une équation différentielle linéaire à coefficients polynomiaux. Dans cette classe, les coefficients des séries sont solutions d'une récurrence linéaire. Cette thèse montre comment calculer cette récurrence efficacement, puis comment l'utiliser pour obtenir un calcul approché efficace des coefficients malgré des instabilités numériques. Ces algorithmes mènent au calcul efficace d'une approximation sur un segment par un polynôme de degré fixé d'une fonction solution d'une équation différentielle linéaire. Enfin, le calcul des récurrences pour les coefficients de séries est généralisé au cas des séries de Fourier généralisées. L'ensemble est illustré d'exemples à partir de programmes développés durant cette thèse.
|
2 |
Commande optimale rapide pour l'optique adaptative des futurs télescopes hectométriquesBéchet, Clémentine 10 December 2008 (has links) (PDF)
Le nombre de degrés de liberté à contrôler dans un système d'optique adaptative (OA) passe de quelques centaines pour les grands télescopes actuels à plusieurs milliers prévus sur les futurs télescopes de 30 à 100 mètres de diamètre. La méthode de commande de cette OA doit être repensée à la fois pour être en adéquation avec les nouveaux critères de performance et pour pouvoir estimer un si grand nombre de paramètres en temps réel. Je montre d'abord qu'il est possible d'améliorer l'estimation de la déformation de la surface d'onde, d'un facteur 2 sur la variance de l'erreur, en tenant compte de connaissances a priori sur la statistique de la turbulence atmosphérique et ce, tout en utilisant un algorithme rapide adapté aux grands systèmes. Ensuite, l'optimisation d'un critère en boucle fermée me conduit à une commande optimale par modèle interne, applicable en temps réel sur un télescope hectométrique grâce à l'algorithme rapide cité précédemment. La robustesse de cette nouvelle méthode de commande a enfin été éprouvée sur un simulateur complet d'OA et ses performances ont été comparées à d'autres approches.
|
3 |
Algorithmes de la morphologie mathématique pour les architectures orientées fluxBrambor, Jaromír 11 July 2006 (has links) (PDF)
Cette thèse est consacrée aux algorithmes de morphologie mathématique qui peuvent considérer les pixels d'une image comme un flux de données. Nous allons démontrer qu'un grand nombre d'algorithmes de morphologie mathématique peuvent être décrits comme un flux de données traversant des unités d'exécution. Nous verrons que cette approche peut aussi fonctionner sur des processeurs génériques possédant un jeu d'instructions multimédia ou sur des cartes graphiques. Pour décrire les algorithmes en flux de données, nous proposons d'utiliser le langage fonctionnel Haskell, ce qui nous permettra de décrire les briques de base de la construction des algorithmes de morphologie mathématique. On applique ces briques dans la description des algorithmes les plus couramment utilisés (dilatation/érosion, opérations géodésiques, fonction distance et nivellements) ce qui facilitera le portage de ces algorithmes sur plusieurs plate-formes. Nous proposons pour la construction des algorithmes morphologiques un mode d'exécution original par macro blocs et nous étudions en profondeur la transposition de cette idée aux architectures SIMD. Nous montrons que l'utilisation des macro blocs est intéressante pour les architectures multimédia et nous montrons également que les algorithmes morphologiques proposés dans cette thèse atteignent de meilleures performances que les implémentations standard. Un nouveau champ s'ouvre ainsi aux algorithmes développés dans les applications de traitement d'images en temps réel. Cette thèse explore également les processeurs graphiques et démontre sur des résultats expérimentaux qu'ils sont, dès à présent, assez performants pour concurrencer les processeurs généraux.
|
4 |
Algorithmique efficace pour des opérations de base en calcul formel.Bostan, Alin 09 December 2003 (has links) (PDF)
Le sujet de cette thèse est la conception et l'implantation d'algorithmes efficaces pour des opérations de base en calcul formel, ainsi que leurs applications à des domaines connexes, comme la théorie algorithmique des nombres et la cryptographie. Une première partie traite de l'algorithmique de base sur les polynômes à une variable. L'outil systématiquement mis en oeuvre est une version constructive du principe de transposition de Tellegen, qui permet d'obtenir de nouveaux algorithmes pour l'évaluation multipoint et l'interpolation (dans diverses bases polynomiales et pour diverses familles de points d'évaluation), ainsi qu'un théorème d'équivalence entre les complexités de ces deux problèmes. La deuxième partie est consacrée à l'algorithmique des nombres algébriques. Nous étudions d'abord certaines opérations élémentaires, comme la somme, le produit et leur généralisation, le produit diamant de Brawley et Carlitz. Leur calcul repose sur l'utilisation de l'opérateur de Newton formel et de la dualité algébrique, traduite algorithmiquement par l'emploi du principe de transposition et des méthodes de type pas de bébés / pas de géants. Ces méthodes sont ensuite généralisées au cadre des systèmes de polynômes de dimension zéro, pour le calcul de polynômes minimaux dans des algèbres quotient, ainsi que de paramétrisations rationnelles. Dans la troisième partie, nous étudions la question du calcul d'un terme d'une suite récurrente linéaire à coefficients polynomiaux. Comme application, nous obtenons des améliorations théoriques et pratiques des méthodes de comptage de points utilisées en cryptographie. Nous proposons ensuite une méthode de type évaluation-interpolation pour certaines opérations usuelles sur les opérateurs différentiels linéaires à coefficients polynomiaux.
|
5 |
Bases of relations in one or several variables : fast algorithms and applications / Bases de relation en une ou plusieurs variables : algorithmes rapides et applicationsNeiger, Vincent 30 November 2016 (has links)
Dans cette thèse, nous étudions des algorithmes pour un problème de recherche de relations à une ou plusieurs variables. Il généralise celui de calculer une solution à un système d’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple le calcul d’approximants de Hermite-Padé ou d’interpolants bivariés. Plutôt qu’une seule solution, nous nous attacherons à calculer un ensemble de générateurs possédant de bonnes propriétés. Précisément, l’entrée de notre problème consiste en un module de dimension finie spécifié par l’action des variables sur ses éléments, et en un certain nombre d’éléments de ce module ; il s’agit de calculer une base de Gröbner du modules des relations entre ces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structure de type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cette matrice. Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplication qui représentent l’action des variables. Dans le cas d’une matrice de Jordan,nous accélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultats pour une forme de Frobenius permettent d’accélérer le calcul de formes normales de matrices polynomiales univariées. Enfin, dans le cas de plusieurs matrices denses, nous accélérons le changement d’ordre pour des bases de Gröbner d’idéaux multivariés zéro-dimensionnels. / In this thesis, we study algorithms for a problem of finding relations in one or several variables. It generalizes that of computing a solution to a system of linear modular equations over a polynomial ring, including in particular the computation of Hermite- Padéapproximants and bivariate interpolants. Rather than a single solution, we aim at computing generators of the solution set which have good properties. Precisely, the input of our problem consists of a finite-dimensional module given by the action of the variables on its elements, and of some elements of this module; the goal is to compute a Gröbner basis of the module of syzygies between these elements. In terms of linear algebra, the input describes a matrix with a type of Krylov structure, and the goal is to compute a compact representation of a basis of the nullspace of this matrix. We propose several algorithms in accordance with the structure of the multiplication matrices which specify the action of the variables. In the case of a Jordan matrix, we accelerate the computation of multivariate interpolants under degree constraints; our result for a Frobenius matrix leads to a faster algorithm for computing normal forms of univariate polynomial matrices. In the case of several dense matrices, we accelerate the change of monomial order for Gröbner bases of multivariate zero-dimensional ideals.
|
6 |
Étude mathématique de quelques équations cinétiques collisionnellesMouhot, Clément 25 November 2004 (has links) (PDF)
On s'intéresse dans cette thèse à l'étude des solutions des équations de Boltzmann (élastiques et inélastiques) et Landau. Les axes de cette étude sont la régularité des solutions et leur comportement asymptotique, et nous nous attachons systématiquement à quantifier les résultats obtenus. Dans la première partie, d'une part nous considérons les solutions spatialement homogènes de l'équation de Boltzmann, pour lesquelles nous montrons la propagation de la régularité et la décroissance des singularités pour des interactions à courte portée, et la propagation de bornes <br />d'intégrabilité pour des interactions à longue portée. D'autre part, nous quantifions la positivité des solutions spatialement <br />inhomogènes, sous des hypothèses de régularité. Dans la deuxième partie, nous donnons des estimations de trou spectral et de coercivité sur les opérateurs de Boltzmann et Landau linéarisés, puis nous prouvons la convergence exponentielle vers l'équilibre avec taux explicite pour un gaz de sphères dures spatialement homogènes. Dans la troisième partie, nous considérons l'équation de Boltzmann spatialement homogène pour les gaz granulaires, pour laquelle nous construisons des solutions pour des modèles d'inélasticité réalistes (mais fortement non-linéaires) et discutons la possibilité de « gel » en temps fini ou asymptotiquement. Puis nous montrons l'existence de profils auto-similaires et étudions le comportement de la solution pour les grandes vitesses. Dans la quatrième partie, nous utilisons une semi-discrétisation de l'opérateur de Boltzmann pour proposer <br />des schémas numériques rapides basés sur les méthodes spectrales ou les méthodes par discrétisation des vitesses.
|
7 |
Compression et inférence des opérateurs intégraux : applications à la restauration d’images dégradées par des flous variables / Approximation and estimation of integral operators : applications to the restoration of images degraded by spatially varying blursEscande, Paul 26 September 2016 (has links)
Le problème de restauration d'images dégradées par des flous variables connaît un attrait croissant et touche plusieurs domaines tels que l'astronomie, la vision par ordinateur et la microscopie à feuille de lumière où les images sont de taille un milliard de pixels. Les flous variables peuvent être modélisés par des opérateurs intégraux qui associent à une image nette u, une image floue Hu. Une fois discrétisé pour être appliqué sur des images de N pixels, l'opérateur H peut être vu comme une matrice de taille N x N. Pour les applications visées, la matrice est stockée en mémoire avec un exaoctet. On voit apparaître ici les difficultés liées à ce problème de restauration des images qui sont i) le stockage de ce grand volume de données, ii) les coûts de calculs prohibitifs des produits matrice-vecteur. Ce problème souffre du fléau de la dimension. D'autre part, dans beaucoup d'applications, l'opérateur de flou n'est pas ou que partialement connu. Il y a donc deux problèmes complémentaires mais étroitement liés qui sont l'approximation et l'estimation des opérateurs de flou. Cette thèse a consisté à développer des nouveaux modèles et méthodes numériques permettant de traiter ces problèmes. / The restoration of images degraded by spatially varying blurs is a problem of increasing importance. It is encountered in many applications such as astronomy, computer vision and fluorescence microscopy where images can be of size one billion pixels. Variable blurs can be modelled by linear integral operators H that map a sharp image u to its blurred version Hu. After discretization of the image on a grid of N pixels, H can be viewed as a matrix of size N x N. For targeted applications, matrices is stored with using exabytes on the memory. This simple observation illustrates the difficulties associated to this problem: i) the storage of a huge amount of data, ii) the prohibitive computation costs of matrix-vector products. This problems suffers from the challenging curse of dimensionality. In addition, in many applications, the operator is usually unknown or only partially known. There are therefore two different problems, the approximation and the estimation of blurring operators. They are intricate and have to be addressed with a global overview. Most of the work of this thesis is dedicated to the development of new models and computational methods to address those issues.
|
Page generated in 0.0423 seconds