Search

In this thesis, we study algorithms for a problem of finding relations in one or severalvariables. It generalizes that of computing a solution to a system of linear modularequations over a polynomial ring, including in particular the computation of Hermite-Padéapproximants and bivariate interpolants. Rather than a single solution, we aim atcomputing generators of the solution set which have good properties.Precisely, the input of our problem consists of a finite-dimensional module given bythe action of the variables on its elements, and of some elements of this module; the goalis to compute a Gröbner basis of the module of syzygies between these elements. In termsof linear algebra, the input describes a matrix with a type of Krylov structure, and thegoal 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 multiplicationmatrices which specify the action of the variables. In the case of a Jordan matrix, weaccelerate the computation of multivariate interpolants under degree constraints; ourresult for a Frobenius matrix leads to a faster algorithm for computing normal forms ofunivariate polynomial matrices. In the case of several dense matrices, we accelerate thechange of monomial order for Gröbner bases of multivariate zero-dimensional ideals.; 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èmed’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple lecalcul 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 bonnespropriétés.Précisément, l’entrée de notre problème consiste en un module de dimension finiespécifié par l’action des variables sur ses éléments, et en un certain nombre d’élémentsde ce module ; il s’agit de calculer une base de Gröbner du module des relations entreces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structurede type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cettematrice.Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplicationqui représentent l’action des variables. Dans le cas d’une matrice de Jordan, nousaccélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultatspour une forme de Frobenius permettent d’accélérer le calcul de formes normalesde 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észéro-dimensionnels.

In this thesis, we study algorithms for a problem of finding relations in one or severalvariables. It generalizes that of computing a solution to a system of linear modularequations over a polynomial ring, including in particular the computation of Hermite-Padéapproximants and bivariate interpolants. Rather than a single solution, we aim atcomputing generators of the solution set which have good properties.Precisely, the input of our problem consists of a finite-dimensional module given bythe action of the variables on its elements, and of some elements of this module; the goalis to compute a Gröbner basis of the module of syzygies between these elements. In termsof linear algebra, the input describes a matrix with a type of Krylov structure, and thegoal 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 multiplicationmatrices which specify the action of the variables. In the case of a Jordan matrix, weaccelerate the computation of multivariate interpolants under degree constraints; ourresult for a Frobenius matrix leads to a faster algorithm for computing normal forms ofunivariate polynomial matrices. In the case of several dense matrices, we accelerate thechange of monomial order for Gröbner bases of multivariate zero-dimensional ideals.; 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èmed’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple lecalcul 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 bonnespropriétés.Précisément, l’entrée de notre problème consiste en un module de dimension finiespécifié par l’action des variables sur ses éléments, et en un certain nombre d’élémentsde ce module ; il s’agit de calculer une base de Gröbner du module des relations entreces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structurede type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cettematrice.Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplicationqui représentent l’action des variables. Dans le cas d’une matrice de Jordan, nousaccélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultatspour une forme de Frobenius permettent d’accélérer le calcul de formes normalesde 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észéro-dimensionnels.

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.

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 $1000 \times 1000 \times 1000$ pixels. Variable blurs can be modelled by linear integral operators $H$ that map a sharp image $u$ to its blurred version $Hu$ defined by\[ Hu(x) = \int_{\Omega} K(x,y) u(y) dy, \quad \forall x \in \Omega = [0,1]^d\]where $K : \Omega \times \Omega \to \mathbb{R}$ is called the kernel. After discretization of the image on a grid of $N$ pixels, $H$ can be viewed as a matrix of size $N \times N$. For targeted applications, matrices contain $10^{18}$ coefficients. 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 \emph{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.In a first part, this work studied the approximation methods of integral operators. Existing approaches in the literature can be separated in two classes. The most developed approaches consists in constructing a low rank decomposition of the kernel $K$. Similarly to the seminal work of Beylkin, Coifman and Rokhlin, we studied the representation of blurring operators in wavelet bases. We showed that matrix-vector products can be rapidly computed in $O(N\epsilon^{-M/d})$ with a precision $\epsilon$ in spectral norm where $M$ is a scalar describing the regularity of the kernel. This type of approximations can be used to design restoration algorithms that are two orders of magnitude faster than current methods.The second class contains methods commonly used in the imaging community. They consist in constructing a low rank decomposition of the Time Varying Impulse Response (TVIR) $T : \Omega \times \Omega \to \mathbb{R}$ defined by $T(x,y) = K(x+y,y)$. Until now, those methods were partially studied and this work bridges the gap in the comprehension of their performances. Moreover, it allowed the identification of a representation that ``super'' compresses the operator. This representation appeals for the development of new identification strategies.In a second part, this work addresses the challenging problem of the estimation of operators. Recent theoretical works studied this problem but none of them can be implemented in targeted applications. In the specific case where some scattered impulse responses are observed, this work proposes the construction of an estimator of the operator that can be evaluated numerically in large dimensions. Theoretical guarantees on the performance of the estimator are also provided. \\Finally, this thesis studied other imaging problems. Images from light-sheet microscopy are degraded by stripe shaped attenuations. These phenomena can be modelled by multiplicative structured noises. This work proposes to solve a convex optimization and convincing results are obtained on real data.The development of quantitative indices that measure the similarity of images is a challenging question in imaging.The illumination of a scene can vary between two moments. Most indices are non invariant to these variations and will fail to assess the similarity of the same scene between the two instants. We proposed a similarity measure that is invariant to illumination changes.; 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 $1000 \times 1000 \times 1000$ 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$ définie par\[ Hu(x) = \int_{\Omega} K(x,y) u(y) dy, \quad \forall x \in \Omega = [0,1]^d\]où $K : \Omega \times \Omega \to \mathbb{R}$ est appelé le noyau. 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 \times N$. Pour les applications visées, la matrice contient $10^{18}$ coefficients. 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. Dans une première partie, ce travail a étudié les méthodes d'approximation des opérateurs intégraux. Elles peuvent être distinguées en deux groupes. Le plus étoffé contient les méthodes qui construisent une décomposition de rang faible du noyau $K$. Similairement aux travaux fondateurs du groupe de Beylkin, Coifman et Rokhlin, nous avons étudié les représentations des opérateurs de flou dans des bases d'ondelettes. Nous avons montré que les produits matrice-vecteur $Hu$ peuvent être appliqués en $O(N\epsilon^{-M/d})$ avec une précision $\epsilon$ où $M$ est un scalaire décrivant la régularité du noyau. Ces approximations peuvent donner lieu à des temps de restauration des images réduits de deux ordres de grandeurs.Les méthodes du deuxième groupe, couramment utilisées dans la communauté du traitement d'image, construisent une décomposition de rang faible de la Time Varying Impulse Response (TVIR) $T : \Omega \times \Omega \to \mathbb{R}$ définie par $T(x,y) = K(x+y,y)$. Elles sont restées jusqu'à présent non-étudiées et ce travail a permis de combler un manque dans la compréhension de leurs performances. De plus, il a permis d'identifier des représentations qui compressent considérablement les opérateurs et rendent possible l'estimation de l'opérateur.Dans une deuxième partie, ce travail aborde le délicat problème d'estimation des opérateurs. Récemment, de nouveaux travaux théoriques s'y sont intéressés, cependant aucun d'eux ne peut être implémenté en pratique. Dans le cas où quelques réponses impulsionnelles arbitrairement réparties dans l'espace sont connues, ce travail propose une construction d'un estimateur de l'opérateur qui soit numériquement applicable en grande dimension. Nous donnons aussi des garanties théoriques sur ses performances.Dans un troisième temps, cette thèse étudie d'autres types de dégradation. Les images issues de la microscopie à feuille de lumière sont altérées par des atténuations en forme de raies. Ce phénomène peut-être modélisé par un bruit multiplicatif structuré. Ce travail propose un modèle de résolution convexe qui rend le problème soluble aisément et qui donne des résultats probants sur des données réelles.Les indices de comparaison de deux images consistent une question délicate. Entre deux instants, une scène peut être illuminée différemment. Beaucoup d'indices sont sensibles à ces variations et échoueront à reconnaître la similarité de la scène entre deux instants. Nous avons proposé une mesure de similarité des images qui est invariante aux changements d'illumination.

By combining Kaltofen's 1992 baby steps/giant steps technique for Wiedemann's 1986 determinant algorithm with Coppersmith's 1994 projections by a block of vectors in the Wiedemann approach and Villard's 1997 analysis of the block technique, we obtain new algorithms for dense matrix problems of asymptotically fast running time. The rst category of problems is for a dense nn matrix A with integer entries. We express the cost in terms of bit operations on the exact integers and denote by kAk the largest entry in absolute value. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal form and Smith normal form of A in (n and (n bit operations, where the exponent adjustment by +o(1) captures additional factors C1(log n) for positive real constants C1 , C2 , C3 and where the rst, asymptotically slower bit complexity does not require any of the sub-cubic matrix multiplication algorithms. Our algorithms are randomized, and we can certify the determinant of A in a Las Vegas fashion. The second category of problems deals with the setting where the matrix A has elements from an abstract commutative ring, that is, when no divisions in the domain of entries are possible. We present algorithms that deterministically compute the determinant, characteristic polynomial and adjoint of A with n ring additions, subtractions and multiplications, that without utilizing sub-cubic matrix multiplication algorithms. With the asymptotically fast matrix multiplication algorithms by Coppersmith and Winograd our method computes the determinant and adjoint in O(n ) ring operations and the characteristic polynomial in O(n ) ring operations. We achieve our results in part through new proofs for Villard's 1997 analysis of the block Wiedemann/Lanczos algorithm and a genralisation od the Knuth/Schönhage/Moenck Euclidean remainder sequence algorithm to matrix polynomials

A Chebyshev series is an expansion in the basis of Chebyshev polynomials of the first kind. These series are important in approximation theory. Unlike Taylor series, their algorithmic aspects are not very developed in computer algebra. This thesis proposes new algorithms for these series. A first part gives fast algorithms that convert a truncated Chebyshev series into a truncated Taylor series and vice versa, and others that multiply or divide two truncated Chebyshev series. The rest of the thesis is devoted to Chebyshev series that are solutions of a linear differential equation with polynomial coefficients. In this class, the coefficients of series are solutions of a linear recurrence. This thesis show how to compute this recurrence efficiently, then how to use it for the efficient computation of approximated coefficients despite numerical instabilities. These algorithms lead to an efficient computation of the approximation by polynomials of fixed degree on a segment for solutions of linear differential equations. Finally, the computation of recurrences for the coefficients of series is generalized to the case of generalized Fourier series. The document is illustrated by examples using implementations developed during this thesis.; 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.

The number of degrees of freedom to be controlled in an Adaptive Optics (AO) system is evolving from a few hundreds on the current telescopes to several thousands foreseen on the coming extremely large telescopes with diameters of order 30 to 100 meters. The control strategies should be adapted both to comply with the new performance criteria and to enable real-time estimation of such a large number of parameters. First, I demonstrate the quantitative improvement of the estimation, a factor of 2 on error variance, available when inserting priors about turbulence statistics, even with a fast algorithm designed for large systems. Next, the optimisation of a closed-loop criterion leads to an optimal law with an internal model control, which can be applied in real time thanks to the same fast algorithm. The robustness of this new control method is finally checked on an end-to-end AO simulator and the performance is compared to other approaches.; 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.

The number of degrees of freedom to be controlled in an Adaptive Optics (AO) system is evolving from a few hundreds on the current telescopes to several thousands foreseen on the coming extremely large telescopes with diameters of order 30 to 100 meters. The control strategies should be adapted both to comply with the new performance criteria and to enable real-time estimation of such a large number of parameters. First, I demonstrate the quantitative improvement of the estimation, a factor of 2 on error variance, available when inserting priors about turbulence statistics, even with a fast algorithm designed for large systems. Next, the optimisation of a closed-loop criterion leads to an optimal law with an internal model control, which can be applied in real time thanks to the same fast algorithm. The robustness of this new control method is finally checked on an end-to-end AO simulator and the performance is compared to other approaches., 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.

Typical tasks in signal processing may be done in simpler ways or more efficiently if the signals to analyze are represented in a proper way. This thesis deals with some algorithmic problems related to signal approximation, more precisely, in the novel field of sparse approximation using redundant dictionaries of functions. Orthogonal bases permit to approximate signals by just taking the N waveforms whose associated projections have maximal amplitudes. This nice property is no longer valid if the used base is redundant. In fact, finding the best decomposition becomes a NP Hard problem in the general case. Thus, suboptimal heuristics have been developed; the best known ones are Matching Pursuit and Basis Pursuit. Both remain highly complex which prevent them from being used in practice in many situations. The first part of the thesis is concerned with this computational bottleneck. We propose to create a tree structure endowing the dictionary and grouping similar atoms in the same branches. An approximation algorithm, called Tree-Based Pursuit, exploiting this structure is presented. It considerably lowers the cost of finding good approximations with redundant dictionaries. The quality of the representation does not only depend on the approximation algorithm but also on the dictionary used. One of the main advantages of these techniques is that the atoms can be tailored to match the features present in the signal. It might happen that some knowledge about the class of signals to approximate directly leads to the dictionary. For most natural signals, however, the underlying structures are not clearly known and may be obfuscated. Learning dictionaries based on examples is an alternative to manual design and is gaining in interest. Most natural signals exhibit behaviors invariant to translations in space or in time. Thus, we propose an algorithm to learn redundant dictionaries under the translation invariance constraint. In the case of images, the proposed solution is able to recover atoms similar to Gabor functions, line edge detectors and curved edge detectors. The two first categories were already observed and the third one completes the range of natural features and is a major contribution of this algorithm. Sparsity is used to define the efficiency of approximation algorithms as well as to characterize good dictionaries. It directly comes from the fact that these techniques aim at approximating signals with few significant terms. This property was successfully exploited as a dimension reduction method for different signal processing tasks as analysis, de-noising or compression. In the last chapter, we tackle the problem of finding the nearest neighbor to a query signal in a set of signals that have a sparse representation. We take advantage of sparsity to approximate quickly the distance between the query and all elements of the database. In this way, we are able to prune recursively all elements that do not match the query, while providing bounds on the true distance. Validation of this technique on synthetic and real data sets confirms that it could be very well suited to process queries over large databases of compressed signals, avoiding most of the burden of decoding.

This thesis deals with the algorithms of Mathematical Morphology that can consider the pixels of an image as if they were a stream of data. We will show that a great number of algorithms of Mathematical Morphology can be described by data flows (streams) passing through the operating units. We will see that this approach can function on generic processors supporting a multi-media instruction set as well as on graphics cards. We propose to use the functional language Haskell for the description of algorithms operating on data flows. This allows us to describe the building blocks that are used to construct morphological algorithms. We apply these building blocks in the description of the most usually used algorithms (dilation/erosion, geodesic operations, distance function and levelings). This will also facilitate the porting of these algorithms onto several platforms. We propose an original mode of execution by macro blocks for the construction of morphological algorithms and we study in depth the transposition of this idea to SIMD architectures. We show that the use of macro blocks is interesting for multimedia architectures. We also show that the morphological algorithms proposed in this thesis reach better performances than standard implementations. Thus, a new field opens to algorithms we have developed here in real-time image processing applications. This thesis also explores the graphics processors and shows on experimental results that they are already powerful enough to compete with general processors.; 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.

This thesis deals with the algorithms of Mathematical Morphology that can consider the pixels of an image as if they were a stream of data. We will show that a great number of algorithms of Mathematical Morphology can be described by data flows (streams) passing through the operating units. We will see that this approach can function on generic processors supporting a multi-media instruction set as well as on graphics cards. We propose to use the functional language Haskell for the description of algorithms operating on data flows. This allows us to describe the building blocks that are used to construct morphological algorithms. We apply these building blocks in the description of the most usually used algorithms (dilation/erosion, geodesic operations, distance function and levelings). This will also facilitate the porting of these algorithms onto several platforms. We propose an original mode of execution by macro blocks for the construction of morphological algorithms and we study in depth the transposition of this idea to SIMD architectures. We show that the use of macro blocks is interesting for multimedia architectures. We also show that the morphological algorithms proposed in this thesis reach better performances than standard implementations. Thus, a new field opens to algorithms we have developed here in real-time image processing applications. This thesis also explores the graphics processors and shows on experimental results that they are already powerful enough to compete with general processors.; 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.

We are interested in this PhD in the study of solutions to the Boltzmann equation (elastic or inelastic) and the Landau equation. The axis of this study are the regularity and asymptotic behavior of the solutions, and we systematically search for quantitative results. In the first part, we consider on the one hand the spatially homogeneous solutions to the Boltzmann equation, for which we prove propagation of regularity and damping of singularities for short-range interactions, as well as propagation of integrability bounds for long-range interactions. On the other hand, we quantify the positivity of the spatially inhomogeneous solutions, under regularity assumptions. In the second part, we give spectral gap and coercivity estimates for the linearized Boltzmann and Landau operators, and we prove exponential convergence to equilibrium with explicit rate for a gas of spatially homogeneous hard spheres. In the third part, we consider the spatially homogeneous Boltzmann equation for granular gases, for which we construct solutions for realistic models of inelasticity (however strongly non-linear) and discuss the possibility of cooling in finite time or asymptotically. We then show the existence of self-similar profils, and study the behavior of solutions for large velocities. In the forth part, we use a semi-discretization of the Boltzmann operator in order to propose fast numerical schemes based on the spectral method or discrete velocity models., 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 d'intégrabilité pour des interactions à longue portée. D'autre part, nous quantifions la positivité des solutions spatialement 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 des schémas numériques rapides basés sur les méthodes spectrales ou les méthodes par discrétisation des vitesses.

The subject of this thesis is the design and implementation of efficient algorithms for some basic operations in computer algebra, as well as their applications to related fields, such as computational number theory and cryptography. The first part of the text is dedicated to basic algorithms on univariate polynomials. The tool which we use systematically is a constructive version of Tellegen's transposition principle, which makes it possible to obtain new algorithms for the problems of multipoint evaluation and interpolation (in various polynomial bases and for various families of evaluation points), as well as a theorem of equivalence between the complexities of these two problems. The second part is devoted to fast computation with algebraic numbers. We begin by studying certain elementary operations, such as the composed sum and the composed product and their generalization -- the diamond product of Brawley and~Carlitz. Their calculation rests on the use of the formal Newton operator and the algebraic duality, translated algorithmically by the use of transposition principle and baby step / giant step methods. The results are then generalized to the framework of zero-dimensional algebraic polynomial systems, for the computation of minimal polynomials in quotient algebras and that of rational parametrizations. In the third part, we investigate the question of the efficient computation of a term in a linear recurrent sequence with polynomial coefficients. As an application, we obtain theoretical and practical improvements of a point-counting method used in hyperelliptic curve cryptography. Then, we propose an evaluation-interpolation type method for certain usual operations on linear differential operators with polynomial coefficients., 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.