We develop a new method for pricing options on discretely sampled arithmetic average in exponential Lévy models. The main idea is the reduction to a backward induction procedure for the difference Wn between the Asian option with averaging over n sampling periods and the price of the European option with maturity one period. This allows for an efficient truncation of the state space. At each step of backward induction, Wn is calculated accurately and fast using a piece-wise interpolation or splines, fast convolution and either flat iFT and (refined) iFFT or the parabolic iFT. Numerical results demonstrate the advantages of the method.

En dépit du succès que les implantations optiques des applications de traitement d'images ont connu, le traitement optique de l'information suscite aujourd'hui moins d'intérêt que dans les années 80-90. Ceci est dû à l'encombrement des réalisations optiques, la qualité des images traitées et le coût des composants optiques. De plus, les réalisations optiques ont eu du mal à s’affranchir de l’avènement des circuits numériques. C’est dans ce cadre que s’inscrivent les travaux de cette thèse dont l’objectif est de proposer une implantation numérique des méthodes optiques de traitement d’images. Pour réaliser cette implantation nous avons choisi d’utiliser les FPGA et les GPU grâce aux bonnes performances de ces circuits en termes de rapidité. En outre, pour améliorer la productivité nous nous sommes focalisés à la réutilisation des blocs préconçus ou IP « Intellectual Properties ». Malgré que les IP commerciales existantes soient optimisées, ces dernières sont souvent payantes et dépendent de la famille de la carte utilisée. La première contribution est de proposer une implantation optimisée des IP pour le calcul de la transformée de Fourier FFT et de la DCT. En effet, le choix de ces deux transformations est justifié par l'utilisation massive de ces deux transformées (FFT et DCT), dans les algorithmes de reconnaissance de formes et de compression, respectivement. La deuxième contribution est de valider le fonctionnement des IP proposées par un banc de test et de mesure. Enfin, la troisième contribution est de concevoir sur FPGA et GPU des implantations numériques des applications de reconnaissance de formes et de compression. Un des résultats probant obtenu dans cette thèse consiste à avoir une rapidité de l’IP FFT proposée 3 fois meilleure que celle de l’IP FFT Xilinx et de pouvoir réaliser 4700 corrélations par seconde. / The main objective of this thesis is to realize a numerical implementation of optical methods of image and signal processing. To achieve this end, we opted to use FPGA (Field Programmable Gate Array) and GPU (Graphical Processing Unit) devices. This choice is justified by their high performance in terms of speed. In addition, to improve productivity, we focused on the reuse of predesigned blocks or "Intellectual Properties" IP. While existing commercial IP are optimized, they are often paid and highly dependent on the card. The first contribution is to provide an optimized IP for Fourier transform (FFT) and the cosine transform (DCT) computing. Indeed, the choice of these two transformations is justified by the widespread use of these two transforms (FFT and DCT), particularly in pattern recognition and compression algorithms. The second contribution is to validate the operation of the proposed IP using a bench test. The last contribution is to implement on FPGA and GPU applications for pattern recognition and compression. One of the convincing results obtained in this thesis is to propose an IP for FFT computing three times faster than Xilinx IP and thus to achieve 4700 correlations per second.

Les équipements de communications numériques intègrent de plus en plus de standards. La commutation d’un standard à l’autre doit pouvoir se faire au prix d’un surcoût matériel modéré, ce qui impose l’utilisation de ressources communes dans des instanciations différentes. La plateforme matérielle nécessaire à l’exécution d’une couche physique multistandard est le segment du système présentant le plus de contraintes par rapport à la reconfiguration : réactivité, consommation et occupation de ressources matérielles. Nos travaux se focalisent sur la paramétrisation qui vise une implémentation multistandards efficace. L’objectif de cette technique est d’identifier des traitements communs entre les standards, voire entre blocs de traitement au sein d’un même standard, afin de définir des blocs génériques pouvant être réutilisés facilement. Nous définissons le management d’opérateurs mutualisés (opérateurs communs) et nous étudions leur implémentation en se basant essentiellement sur des évaluations de complexité pour quelques standards utilisant la modulation OFDM. Nous proposons en particulier l’architecture d’un opérateur commun permettant la gestion efficace des ressources matérielles entre les algorithmes FFT et décodage de Viterbi. L’architecture, que nous avons proposé et implémenté sur FPGA, permet d’adapter le nombre d’opérateurs communs alloués à chaque algorithme et donc permet l’accélération des traitements. Les résultats montrent que l’utilisation de cette architecture commune offre des gains en complexité pouvant atteindre 30% dans les configurations testées par rapport à une implémentation classique avec une réduction importante de l’occupation mémoire. / Today's telecommunication systems require more and more flexibility, and reconfiguration mechanisms are becoming major topics especially when it comes to multistandard designs. In typical hardware designs, the communication standards are implemented separately using dedicated instantiations which are difficult to upgrade for the support of new features. To overcome these issues, we exploit a parameterization approach called the Common Operator (CO) technique that can be considered to build a generic terminal capable of supporting a large range of communication standards. The main principle of the CO technique is to identify common elements based on smaller structures that could be widely reused across signal processing functions. This technique aims at designing a scalable digital signal processing platform based on medium granularity operators, larger than basic logic cells and smaller than signal processing functions. In this thesis, the CO technique is applied to two widely used algorithms in wireless communication systems: Viterbi decoding and Fast Fourier Transform (FFT). Implementing the FFT and Viterbi algorithms in a multistandard context through a common architecture poses significant architectural constraints. Thus, we focus on the design of a flexible processor to manage the COs and take advantage from structural similarities between FFT and Viterbi trellis. A flexible FFT/Viterbi processor was proposed and implemented on FPGA and compared to dedicated hardware implementations. The results show a considerable gain in flexibility. This gain is achieved with no complexity overhead since the complexity if even decreased up to 30% in the considered configurations.

Esta pesquisa propôs uma contribuição aos procedimentos de inspeção de pontes por meio de um plano de monitoramento de curta duração do comportamento dinâmico do tabuleiro de pontes rodoviárias de concreto com a utilização de receptores GPS de 100 Hz associado à diversas técnicas de filtragem de sinais. O estudo foi conduzido em uma ponte em serviço localizada na rodovia Fernão Dias (BR-381). O procedimento de inspeção proposto baseou-se no uso de dois sinais de satélites GPS, por meio da aplicação do Método Residual de Fase (MRF), e da análise temporal dos resíduos da dupla diferença de fase a partir da Fast Fourier Transform (FFT), Continuous Wavelet Transform (CWT), Passa-Faixa Chebyshev do Tipo I. A descrição do comportamento dinâmico do tabuleiro do vão central da ponte se deu por meio da extração dos valores de frequência e amplitude das deflexões verticais a partir dos dados GPS filtrados (resíduos), em três períodos de amostragem de 1 minuto. Os valores de frequência variaram de 0,5 Hz a 8 Hz nos três períodos de amostragens e também nos filtros FFT, CWT e Passa-Faixa Chebyshev do Tipo I. Os valores de amplitude de deslocamento vertical máximo ficaram em torno de 6 mm. Estes valores coincidiram com os valores de frequência e amplitude de deslocamento vertical registrados pela instrumentação clássica com acelerômetros, transdutores de deslocamento vertical, modelagem por elementos finitos e prova de carga estática e dinâmica realizadas sobre tabuleiro do vão central da ponte instrumentado. Por fim, pode-se afirmar que os procedimentos propostos, além de poderem ser utilizados como uma etapa preliminar de inspeção de tabuleiro de pontes rígidas possibilitaram a detecção de deslocamentos dinâmicos verticais milimétricos e suas frequências de vibração. / This research proposed a contribution for bridge inspection procedures at of a short-term monitoring plan of the dynamic behavior of the concrete road bridge with the use of 100 Hz GPS receivers associated with various signal filtering techniques. The study was conducted in the service bridge located on the highway Fernão Dias (BR-381). The procedure inspection proposed was based on the use of two satellite GPS signals, by applying the Phase Residual Method (PRM), and the temporal analysis of the residuals of the double difference phase from the Fast Fourier Transform (FFT), Continuous Wavelet Transform (CWT), Type I Chebyshev Band-Pass. The dynamic behavior of the central span of the bridge was described by extracting the frequency and amplitude values of the vertical deflections from the filtered GPS data (residues), in three sampling periods of 1 minute. The frequency values found ranged from 0.5 Hz to 8 Hz in the three sampling periods as well as in the FFT, CWT and Chebyshev Type I Band-Pass filters. The maximum vertical displacement peak values were around 6 mm. These values coincided with the vertical displacement and amplitude values recorded by the classical instrumentation with accelerometers, vertical displacement transducers, finite element modeling and static and dynamic load test performed on the central span deck of the instrumented bridge. Finally, it could affirm that the procedures proposed, besides being able to be used as a preliminary step of inspection of the rigid bridge\'s deck enabled the detection of millimetric vertical dynamic displacements and their frequencies of vibration.

Depuis 1960 et le résultat fondateur de Karatsuba, on sait que la complexité de la multiplication (d’entiers ou de polynômes) est sous-quadratique : étant donné un anneau R quelconque, le produit sur R[X] des polynômes a_0 + a_1 X et b_0 + b_1 X, pour tous a_0, a_1, b_0 et b_1 dans R, peut être calculé en seulement trois et non pas quatre multiplications sur R : (a_0 + a_1 X)(b_0 + b_1 X) = m_0 + (m_2 - m_0 - m_1)X + m_1 X^2, avec les trois produits m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). De la même manière, l’algorithme de Strassen permet de multiplier deux matrices 2nx2n en seulement sept produits de matrices nxn. Les deux exemples précédents tombent dans la catégorie des applications bilinéaires : des fonctions de la forme Phi : K^m x K^n -> K^l, pour un corps donné K, linéaires en chacune des deux variables. Parmi les applications bilinéaires les plus classiques, on trouve ainsi la multiplication de polynômes, de matrices, ou encore d’éléments d’extensions algébriques de corps finis. Étant donnée une application bilinéaire Phi, calculer le nombre minimal de multiplications nécessaires au calcul de cette application est un problème NP-difficile. L'objectif de cette thèse est de proposer des algorithmes minimisant ce nombre de multiplications. Deux angles d'attaques ont été suivis. Un premier aspect de cette thèse est l'étude du problème du calcul de la complexité bilinéaire sous l'angle de la reformulation de ce problème en termes de recherche de sous-espaces vectoriels de matrices de rang donné. Ce travail a donné lieu à un algorithme tenant compte de propriétés intrinsèques aux produits considérés tels que les produits matriciels ou polynomiaux sur des corps finis. Cet algorithme a permis de trouver toutes les décompositions possibles, sur F_2, pour le produit de polynômes modulo X^5 et le produit de matrices 3x2 par 2x3. Un autre aspect de ma thèse est celui du développement d’algorithmes asymptotiquement rapides pour la multiplication entière. Une famille particulière d'algorithmes récents ont été proposés suite à un article de Fürer publié en 2007, qui proposait un premier algorithme, reposant sur la transformée de Fourier rapide (FFT) permettant de multiplier des entiers de n bits en O(n log n 2^{O(log^* n)}), où log^* est la fonction logarithme itéré. Dans cette thèse, un algorithme dont la complexité dépend d'une conjecture de théorie des nombres est proposé, reposant sur la FFT et l'utilisation de premiers généralisés de Fermat. Une analyse de complexité permet d'obtenir une estimation en O(n log n 4^{log^* n}) / Since 1960 and the result of Karatsuba, we know that the complexity of the multiplication (of integers or polynomials) is sub-quadratic: given a ring R, the product in R[X] of polynomials a_0 + a_1 X and b_0 + b_1 X, for any a_0, a_1, b_0 and b_1 in R, can be computed with three and not four multiplications over R: (a_0 + a_1X)(b_0 + b_1X) = m_0 + (m_2 - m_0 - m_1)X + m_1X^2, with the three multiplications m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). In the same manner, Strassen's algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn. The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^m x K^n -> K^l, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied. The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_2, for the product of polynomials modulo X^5 and the product of matrices 3x2 by 2x3. Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply n-bit integers in O(n log n 2^{O(log^* n)}), where log^* is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes. With a careful complexity analysis of this algorithm, we obtain a complexity in O(nlog n 4^{log^* n})

On présente ici un ensemble de méthodes numériques performantes pour lasimulation micromagnétique 3D reposant sur l’équation de Landau-Lifchitz-Gilbert, constituantun code nommé feeLLGood. On a choisi l’approche éléments finis pour sa flexibilitégéométrique. La formulation adoptée respecte la contrainte d’orthogonalité entre l’aimantationet sa dérivée temporelle, contrairement à la formulation classique sur-dissipative.On met au point un schéma de point milieu pour l’équation Landau-Lifchitz-Gilbert quiest stable et d’ordre deux en temps. Cela permet de prendre, à précision égale, des pas detemps beaucoup plus grands (typiquement un ordre de grandeur) que les schémas classiques.Un véritable enjeu numérique est le calcul du champ démagnétisant, non local. Oncompare plusieurs techniques de calcul rapide pour retenir celles, inédites dans le domaine,des multipôles rapides (FMM) et des transformées de Fourier hors-réseau (NFFT). Aprèsavoir validé le code sur des cas-tests et établi son efficacité, on présente les applications àla simulation des nanostructures : sélection de chiralité et résonance ferromagnétique d’unplot monovortex de cobalt, hystérésis des chapeaux de Néel dans un plot allongé de fer.Enfin, l’étude d’un oscillateur spintronique prouve l’évolutivité du code. / Here is presented a set of efficient numerical methods for 3D micromagneticsimulation based on the Landau-Lifchitz-Gilbert equation, making up a code named feeLLGood.The finite element approach was chosen for its geometrical flexibility. The adoptedformulation meets the orthogonality constraint between the magnetization and its time derivative,unlike the over-dissipative classical formulation. A midoint rule was developed forthe Landau-Lifchitz-Gilbert equation which is stable and second order in time. This allowsfor much bigger time steps (typically an order of magnitude) than classical schemes at thesame precision. Computing the nonlocal demagnetizing interaction is a real numerical challenge.Several fast computation techniques are compared. Those selected are novel to thefield : the Fast Multipole Method (FMM) and Non-uniform Fast Fourier Transforms (NFFT).After the code is validated on test cases and its efficiency established, applications to the simulationof nanostructures are presented : chirality selection and ferromagnetic resonanceof a cobalt monovortex dot, Neel caps hysteresis in an iron dot. Finally, the study of a spintronicoscillator proves the code’s upgradability.

Made available in DSpace on 2016-03-15T19:37:47Z (GMT). No. of bitstreams: 1 Luiz Carlos Bernardo.pdf: 7288586 bytes, checksum: b7562f834db8a5ce808707075e7ce04b (MD5) Previous issue date: 2013-06-14 / A chaotic signal based communication system represents a new wideband transmission model. Nonetheless, chaotic based systems have not yet shown a distinguished performance in terms of bit error rate when transmitted in narrow band channels or in the presence of impairments in comparison to the traditional communications systems. The focus of this work relies on an experiment that overcomes this issue, through the conjugation of the characteristics of traditional communications based in orthogonal carriers and those originated from chaotic signals. More clearly, the chaotic modulation is employed in sub-carriers of traditional OFDM (Orthogonal Frequency Division Multiplexing). This novel modulation scheme is implemented through the generation of chaotic sequences in a one dimensional map controlled by a parameter p which defines the central region of the map as a guard interval, the slope of the delimiting lines and the chaotic behavior of the generated sequence. This parameter also determines directly the amplitude of each symbol, making it more irregular and less predictable, avoiding the detection by eavesdroppers and increasing the security level of the link to be transmitted. Besides the change in the traditional OFDM modulator from 4QAM to chaotic one, the Fast Fourier Transform (IFFT /FFT) will be replaced by Wavelets Transform IDWT/DWT), in order to overcome some conventional OFDM s disadvantages Additionally a quadrature chaotic OFDM system was conceived, where the chaotic modulation was performed in a constellation I and Q that was submitted to the same channel conditions as the previous one. Both systems were simulated in a MATLAB® environment using the built in functions at the Communications System Toolbox and its behavior analyzed using the BER-Bit error rate versus SNR-Signal noise ratio. The obtained results were reported and scrutinized. / Sistemas de comunicações baseados em sinais caóticos representam um novo campo de estudo de transmissão em banda larga. Entretanto, sistemas baseados em sinais caóticos não apresentaram ainda um desempenho distinto em termos de taxa de erro, quando transmitidos em canais sem fios ou na presença de interferências em comparação aos sistemas tradicionais. O foco deste trabalho está na proposta de um novo esquema obtido através da conjugação das características da comunicação tradicional baseada em subportadoras ortogonais e aquelas originadas por sinais caóticos. Mais precisamente, a modulação caótica é empregada nas subportadoras de um sistema OFDM (Multiplexação por Divisão de Frequência Ortogonal) tradicional. Este novo modelo de modulação é implementado através de geração de sequências caóticas em um mapa unidimensional controlado por um parâmetro p que define uma região central do mapa como um intervalo de guarda e, por conseguinte, o comportamento caótico da sequência gerada. Este parâmetro também determina diretamente a amplitude de cada símbolo, fazendo-o mais irregular e menos previsível, evitando a detecção por pessoal não autorizado, possibilitando o aumento do nível de segurança da transmissão. Além da mudança no modulador do OFDM convencional de 4QAM para caótico, ter-se-á a substituição da Transformada Rápida de Fourier (IFFT/FFT), largamente utilizada em sistemas OFDM pela Transformada Wavelet (IDWT/DWT), de maneira a aprimorar os pontos fracos do sistema OFDM convencional. Como contribuição adicional, tem se a concepção do sinal com modulação simbólica em quadratura, ou seja, uma parte do sinal foi gerada no eixo I e a outra parte no eixo Q, criando uma modulação caótica em quadratura que é submetida aos mesmos canais da modulação caótica anterior. Os sistemas propostos foram simulados em ambiente MATLAB® utilizando-se de funções pré-existentes no modulo de ferramentas de comunicações (Communications System Toolbox) e o seu comportamento analisado em termos de gráficos que representam a relação da taxa de erro do bit (BER) versus relação sinal ruído (SNR). Os resultados obtidos foram reportados e debatidos.

Esta pesquisa propôs uma contribuição aos procedimentos de inspeção de pontes por meio de um plano de monitoramento de curta duração do comportamento dinâmico do tabuleiro de pontes rodoviárias de concreto com a utilização de receptores GPS de 100 Hz associado à diversas técnicas de filtragem de sinais. O estudo foi conduzido em uma ponte em serviço localizada na rodovia Fernão Dias (BR-381). O procedimento de inspeção proposto baseou-se no uso de dois sinais de satélites GPS, por meio da aplicação do Método Residual de Fase (MRF), e da análise temporal dos resíduos da dupla diferença de fase a partir da Fast Fourier Transform (FFT), Continuous Wavelet Transform (CWT), Passa-Faixa Chebyshev do Tipo I. A descrição do comportamento dinâmico do tabuleiro do vão central da ponte se deu por meio da extração dos valores de frequência e amplitude das deflexões verticais a partir dos dados GPS filtrados (resíduos), em três períodos de amostragem de 1 minuto. Os valores de frequência variaram de 0,5 Hz a 8 Hz nos três períodos de amostragens e também nos filtros FFT, CWT e Passa-Faixa Chebyshev do Tipo I. Os valores de amplitude de deslocamento vertical máximo ficaram em torno de 6 mm. Estes valores coincidiram com os valores de frequência e amplitude de deslocamento vertical registrados pela instrumentação clássica com acelerômetros, transdutores de deslocamento vertical, modelagem por elementos finitos e prova de carga estática e dinâmica realizadas sobre tabuleiro do vão central da ponte instrumentado. Por fim, pode-se afirmar que os procedimentos propostos, além de poderem ser utilizados como uma etapa preliminar de inspeção de tabuleiro de pontes rígidas possibilitaram a detecção de deslocamentos dinâmicos verticais milimétricos e suas frequências de vibração. / This research proposed a contribution for bridge inspection procedures at of a short-term monitoring plan of the dynamic behavior of the concrete road bridge with the use of 100 Hz GPS receivers associated with various signal filtering techniques. The study was conducted in the service bridge located on the highway Fernão Dias (BR-381). The procedure inspection proposed was based on the use of two satellite GPS signals, by applying the Phase Residual Method (PRM), and the temporal analysis of the residuals of the double difference phase from the Fast Fourier Transform (FFT), Continuous Wavelet Transform (CWT), Type I Chebyshev Band-Pass. The dynamic behavior of the central span of the bridge was described by extracting the frequency and amplitude values of the vertical deflections from the filtered GPS data (residues), in three sampling periods of 1 minute. The frequency values found ranged from 0.5 Hz to 8 Hz in the three sampling periods as well as in the FFT, CWT and Chebyshev Type I Band-Pass filters. The maximum vertical displacement peak values were around 6 mm. These values coincided with the vertical displacement and amplitude values recorded by the classical instrumentation with accelerometers, vertical displacement transducers, finite element modeling and static and dynamic load test performed on the central span deck of the instrumented bridge. Finally, it could affirm that the procedures proposed, besides being able to be used as a preliminary step of inspection of the rigid bridge\'s deck enabled the detection of millimetric vertical dynamic displacements and their frequencies of vibration.

La multiplication de polynômes est une opération fondamentale en théorie de la complexité. En effet, pour de nombreux problèmes d’arithmétique, la complexité des algorithmes s’exprime habituellement en fonction de la complexité de la multiplication. Un meilleur algorithme de multiplication permet ainsi d’effectuer les opérations concernées plus rapidement. Un résultat de 2016 a établi une meilleure complexité asymptotique pour la multiplication de polynômes dans des corps finis. Cet article constitue le point de départ de la thèse ; l’objectif est d’étudier les conséquences à la fois théoriques et pratiques de la nouvelle borne de complexité.La première partie s’intéresse à la multiplication de polynômes à une variable. Cette partie présente deux nouveaux algorithmes censés accélérer le calcul en pratique (plutôt que d’un point de vue asymptotique). S’il est difficile dans le cas général d’observer l’amélioration prévue, certains cas précis sont particulièrement favorables. En l’occurrence, le second algorithme proposé, spécifique aux corps finis, conduit à une meilleure implémentation de la multiplication dans F_2[X], environ deux fois plus rapide que les logiciels précédents.La deuxième partie traite l’arithmétique des polynômes à plusieurs variables modulo un idéal, telle qu’utilisée par exemple pour la résolution de systèmespolynomiaux. Ce travail suppose une situation simplifiée, avec seulement deux variables et sous certaines hypothèses de régularité. Dans ce cas particulier, la deuxième partie de la thèse donne des algorithmes de complexité asymptotiquement optimale (à des facteurs logarithmiques près), par rapport à la taille des entrées/sorties. L’implémentation pour ce cas spécifique est alors nettement plus rapide que les logiciels généralistes, le gain étant de plus en plus marqué lorsque la taille de l’entrée augmente. / The multiplication of polynomials is a fundamental operation in complexity theory. Indeed, for many arithmetic problems, the complexity of algorithms is expressed in terms of the complexity of polynomial multiplication. For example, the complexity of euclidean division or of multi-point evaluation/interpolation (and others) is often expressed in terms of the complexity of polynomial multiplication. This shows that a better multiplication algorithm allows to perform the corresponding operations faster. A 2016 result gave an improved asymptotic complexity for the multiplication of polynomials over finite fields. This article is the starting point of the thesis; the present work aims to study the implications of the new complexity bound, from a theoretical and practical point of view.The first part focuses on the multiplication of univariate polynomials. This part presents two new algorithms that should make the computation faster in practice (rather than asymptotically speaking). While it is difficult in general to observe the predicted speed-up, some specific cases are particularly favorable. Actually, the second proposed algorithm, which is specific to finite fields, leads to a better implementation for the multiplication in F 2 [X], about twice as fast as state-of-the-art software.The second part deals with the arithmetic of multivariate polynomials modulo an ideal, as considered typically for polynomial system solving. This work assumes a simplified situation, with only two variables and under certain regularity assumptions. In this particular case, there are algorithms whose complexity is asymptotically optimal (up to logarithmic factors), with respect to input/output size. The implementation for this specific case is then significantly faster than general-purpose software, the speed-up becoming larger and larger when the input size increases.

No description available.