Search

Polynomials are very used in applied mathematics. Polynomial models provide an analytic framework for mechanics, physics, economy or financial modeling. They play an important role in a growing range of applications. For a real polynomial in one variable, one can consider on the one side the signs of its coefficients and on the other the signs of its possible real roots. The Descartes’ rule of signs imposes restrictions on the number of its positive roots expressed via the number of sign changes in its sequence of coefficients. This allows to deduce restrictions on the number of negative roots as well. A sign pattern (SP) of length d + 1 is a finite sequence of ”+” and/or ”−” signs. For the polynomial P := x^d + a_(d−1)x^(d−1) + ··· + a0, (aj ∈ R∗) we say that the sequence (1, a_(d−1), . . ., a0) defines the SP σ if σ = (+, sgn(a_(d−1)), . . ., sgn(a0)). As we consider only monic polynomials, the first sign of the SP is a ”+”. Denote by c and p the numbers of sign changes and sign preservations in the sequence (1, ad−1, . . ., a0) and by pos and neg the numbers of positive and negative roots of P counted with multiplicity. According to Descartes’ rule of signs, one has pos ≤ c and, applying this rule to the polynomial P (−x) one has neg ≤ p. Fourier’s observation is tantamount to saying that: c−pos ∈ 2Z and p−neg ∈ 2Z. We say that (pos, neg) is an admissible pair (AP) for σ if Descartes’ rule is satisfied (pos is the number of positive roots and neg the number of negative roots). A given couple (SP, AP) is realizable if there exists a monic polynomial whose sequence of coefficients defines the SP σ and which has exactly pos positive and exactly neg negative roots, all of them distinct. Question 1. For a given degree d, what are the non-realizable couples (SP,AP) ? We explore this question and find some sufficient conditions for the (non)existence of degree d real polynomials with two sign changes in the SP. For d ≤ 10 and for SPs with two sign changes, we give the exhaustive answer to Question 1. Up to degree 8, for all the non-realizable cases, one of the numbers pos or neg is 0. The next result presented in this thesis is that for d = 9, there is a non- realizable couple (SP, AP) in which both components of the AP are nonzero (and this is the only couple in degree 9). We formulate a third problem when a polynomial and its derivatives of all orders are considered. In this case we have one more constraint due to Rolle’s theorem. A list of APs of the polynomial P and its derivatives compatible with Descartes’ rule and Rolle’s theorem is called SAP (sequence of admissible pairs). In this part, one has explained the realizability of all possible SAPs in degree up to 5. The fourth result of this thesis concerns the explanation of the non-realizability of certain couples (SP, AP) using pictures showing the discriminant set. We explain the non-existence of the only non-realizable case for d = 5 and the existence of all other cases by means of pictures showing the discriminant set of the family of polynomials x^5 + x^4 + ax^3 + bx^2 + cx + d together with the coordinate axes.; Les polynômes sont très utilisés en mathématiques appliquées. Les modèles utilisant des polynômes fournissent un cadre analytique pour la modélisation mécanique, physique, économique ou financière. Pour un polynôme réel à une variable, nous considérons d’un côté les signes de ses coefficients et de l’autre les signes de ses racines réelles. La règle de Descartes impose des contraintes sur le nombre de racines strictement positives exprimées en termes du nombre de changements de signe dans la suite des coefficients du polynôme. Cela permet de déduire des restrictions sur le nombre de racines négatives. Une suite de signe (SS) de longueur d + 1 est une séquence finie de signes ”+” et/ou ”−”. Pour le polynôme P := x^d + a_(d−1)x^(d−1) + · · · + a0, (aj ∈ R∗) nous disons que la séquence (1, a_(d−1)), . . ., a_0) définit la SS σ si σ = (+, sgn (ad−1), . . ., sgn (a0)). Comme nous ne considérons que les polynômes moniques, le premier signe de la SS est un ”+”. Soit c (respectivement p) le nombre de changements (respectivement préservations) de signe dans la séquence (1, a_(d−1), . . ., a0) et soit pos (respectivement neg) le nombre de racines positives (respectivement négatives) de P compté avec multiplicité. D’aprés la règle de Descartes on a pos ≤ c et, en appliquant cette règle à P (−x), neg ≤ p. Une observation faite par Fourier dit que: c − pos ∈ 2Z et p − neg ∈ 2Z. On dit que (pos, neg) est une paire admissible (PA) pour σ si la règle de Descartes est satisfaite (pos est le nombre de racines positives et neg le nombre de racines négatives). Un couple (SS, PA) est dit réalisable s’il existe un polynôme monique dont la séquence de coefficients définit la SS σ et qui a exactement pos racines positives et neg racines négatives, toutes distinctes. Pour un degré donné d, nous recherchons les couples (SS, PA) non réalisables. Le premier résultat de notre travail donne des conditions suffisantes pour l’existence ou la non-existence de polynômes réels de degré d avec deux changements de signe dans la SS. Pour d ≤ 10 et pour les SS avec deux changements de signe, nous donnons la réponse exhaustive à la question. Jusqu’en degré 8, pour tous les cas non réalisables, l’un des nombres pos ou neg est 0. Le deuxième résultat présenté dans cette these, dit que pour d = 9, il existe un couple non réalisable (SS, PA) dans lequel les deux composantes de la PA sont non nulles (et c’est le seul couple en degré 9). Le troisième résultat porte sur un polynôme et ses dérivées de tous ordres. Dans ce cas, nous avons une contrainte supplémentaire qui est celle du théorème de Rolle. Une liste de PAs du polynôme P et de ses dérivées compatibles avec la règle de Descartes et le théorème de Rolle, est appelée séquence de paires admissibles (SPA). Dans cette partie, nous avons expliqué la (non) réalisabilité de toutes les SPA possibles en degré ≤ 5. Le quatrième résultat de cette thèse concerne l’explication de la non-réalisabilité à l’aide d’images montrant le discriminant. Nous expliquons la non-existence du seul cas non réalisable pour d = 5 et l’existence de tous les autres cas au moyen d’images montrant le discriminant de la famille des polynômes x^5 + x^4 + ax^3 + bx^2 + cx + d.

Polynomials are very used in applied mathematics. Polynomial models provide an analytic framework for mechanics, physics, economy or financial modeling. They play an important role in a growing range of applications. For a real polynomial in one variable, one can consider on the one side the signs of its coefficients and on the other the signs of its possible real roots. The Descartes’ rule of signs imposes restrictions on the number of its positive roots expressed via the number of sign changes in its sequence of coefficients. This allows to deduce restrictions on the number of negative roots as well. A sign pattern (SP) of length d + 1 is a finite sequence of ”+” and/or ”−” signs. For the polynomial P := x^d + a_(d−1)x^(d−1) + ··· + a0, (aj ∈ R∗) we say that the sequence (1, a_(d−1), . . ., a0) defines the SP σ if σ = (+, sgn(a_(d−1)), . . ., sgn(a0)). As we consider only monic polynomials, the first sign of the SP is a ”+”. Denote by c and p the numbers of sign changes and sign preservations in the sequence (1, ad−1, . . ., a0) and by pos and neg the numbers of positive and negative roots of P counted with multiplicity. According to Descartes’ rule of signs, one has pos ≤ c and, applying this rule to the polynomial P (−x) one has neg ≤ p. Fourier’s observation is tantamount to saying that: c−pos ∈ 2Z and p−neg ∈ 2Z. We say that (pos, neg) is an admissible pair (AP) for σ if Descartes’ rule is satisfied (pos is the number of positive roots and neg the number of negative roots). A given couple (SP, AP) is realizable if there exists a monic polynomial whose sequence of coefficients defines the SP σ and which has exactly pos positive and exactly neg negative roots, all of them distinct. Question 1. For a given degree d, what are the non-realizable couples (SP,AP) ? We explore this question and find some sufficient conditions for the (non)existence of degree d real polynomials with two sign changes in the SP. For d ≤ 10 and for SPs with two sign changes, we give the exhaustive answer to Question 1. Up to degree 8, for all the non-realizable cases, one of the numbers pos or neg is 0. The next result presented in this thesis is that for d = 9, there is a non- realizable couple (SP, AP) in which both components of the AP are nonzero (and this is the only couple in degree 9). We formulate a third problem when a polynomial and its derivatives of all orders are considered. In this case we have one more constraint due to Rolle’s theorem. A list of APs of the polynomial P and its derivatives compatible with Descartes’ rule and Rolle’s theorem is called SAP (sequence of admissible pairs). In this part, one has explained the realizability of all possible SAPs in degree up to 5. The fourth result of this thesis concerns the explanation of the non-realizability of certain couples (SP, AP) using pictures showing the discriminant set. We explain the non-existence of the only non-realizable case for d = 5 and the existence of all other cases by means of pictures showing the discriminant set of the family of polynomials x^5 + x^4 + ax^3 + bx^2 + cx + d together with the coordinate axes.; Les polynômes sont très utilisés en mathématiques appliquées. Les modèles utilisant des polynômes fournissent un cadre analytique pour la modélisation mécanique, physique, économique ou financière. Pour un polynôme réel à une variable, nous considérons d’un côté les signes de ses coefficients et de l’autre les signes de ses racines réelles. La règle de Descartes impose des contraintes sur le nombre de racines strictement positives exprimées en termes du nombre de changements de signe dans la suite des coefficients du polynôme. Cela permet de déduire des restrictions sur le nombre de racines négatives. Une suite de signe (SS) de longueur d + 1 est une séquence finie de signes ”+” et/ou ”−”. Pour le polynôme P := x^d + a_(d−1)x^(d−1) + · · · + a0, (aj ∈ R∗) nous disons que la séquence (1, a_(d−1)), . . ., a_0) définit la SS σ si σ = (+, sgn (ad−1), . . ., sgn (a0)). Comme nous ne considérons que les polynômes moniques, le premier signe de la SS est un ”+”. Soit c (respectivement p) le nombre de changements (respectivement préservations) de signe dans la séquence (1, a_(d−1), . . ., a0) et soit pos (respectivement neg) le nombre de racines positives (respectivement négatives) de P compté avec multiplicité. D’aprés la règle de Descartes on a pos ≤ c et, en appliquant cette règle à P (−x), neg ≤ p. Une observation faite par Fourier dit que: c − pos ∈ 2Z et p − neg ∈ 2Z. On dit que (pos, neg) est une paire admissible (PA) pour σ si la règle de Descartes est satisfaite (pos est le nombre de racines positives et neg le nombre de racines négatives). Un couple (SS, PA) est dit réalisable s’il existe un polynôme monique dont la séquence de coefficients définit la SS σ et qui a exactement pos racines positives et neg racines négatives, toutes distinctes. Pour un degré donné d, nous recherchons les couples (SS, PA) non réalisables. Le premier résultat de notre travail donne des conditions suffisantes pour l’existence ou la non-existence de polynômes réels de degré d avec deux changements de signe dans la SS. Pour d ≤ 10 et pour les SS avec deux changements de signe, nous donnons la réponse exhaustive à la question. Jusqu’en degré 8, pour tous les cas non réalisables, l’un des nombres pos ou neg est 0. Le deuxième résultat présenté dans cette these, dit que pour d = 9, il existe un couple non réalisable (SS, PA) dans lequel les deux composantes de la PA sont non nulles (et c’est le seul couple en degré 9). Le troisième résultat porte sur un polynôme et ses dérivées de tous ordres. Dans ce cas, nous avons une contrainte supplémentaire qui est celle du théorème de Rolle. Une liste de PAs du polynôme P et de ses dérivées compatibles avec la règle de Descartes et le théorème de Rolle, est appelée séquence de paires admissibles (SPA). Dans cette partie, nous avons expliqué la (non) réalisabilité de toutes les SPA possibles en degré ≤ 5. Le quatrième résultat de cette thèse concerne l’explication de la non-réalisabilité à l’aide d’images montrant le discriminant. Nous expliquons la non-existence du seul cas non réalisable pour d = 5 et l’existence de tous les autres cas au moyen d’images montrant le discriminant de la famille des polynômes x^5 + x^4 + ax^3 + bx^2 + cx + d.

This thesis in bijective combinatorics focuses on the classical combinatorics classes that are trees and walks, and attempts to build bijections around them. Motivated by recent works, we first work on basketball walks, which generating function verifies a non-trivial relation involving the Catalan numbers. Since the original proof was using the kernel method to find this result, our objective is to study the decomposition of these walks to bijectively prove this formula. Moreover, we manage to find that these walks are in bijection with increasing unary-binary trees which permutation avoids the pattern -213-. Then we look at an enumerating formula for some weighted Dyck paths. Corollary to a generalised hook-length formula for skew Young tableaux, we use Flajolet's work to study this result with continued fractions. Following that, we look at a -4- variables generalization of the Ramanujan polynomials, and their link to different families of trees. As Guo and Zeng did with planar trees and half mobile trees, we interpret these polynomials as generating functions for Greg trees and Cayley trees, whilst building multiple bijections linking them all together. Finally, we look at a partially ordered set of bubbling parking functions. This tree structure representing parking functions allows us to prove multiple properties of the ordered set, such as shellability and chain enumeration, Cette thèse située dans le cadre de la combinatoire bijective a pour sujet plusieurs familles d'arbres et de chemins, objets classiques de la combinatoire, et tente de les mettre en relation par la construction de bijections. Dans un premier temps, motivé par des travaux récents, on s'intéresse aux chemins de basketball, dont la fonction génératrice vérifie une relation non triviale avec les nombres de Catalan. La preuve originale provenant de la méthode du noyau, notre objectif est d'étudier la décomposition de ce chemin pour obtenir une preuve bijective de cette formule. On trouve de plus que cette classe de chemins est en bijection avec les arbres unaires-binaires croissants dont la permutation associée évite -213-. Ensuite on s'intéresse à une formule d'énumération de chemins de Dyck pondérés. Corolaire de l'application d'une formule des équerres généralisée sur les tableaux de Young gauche, on montre que cette formule peut être interprétée comme une fraction continue grâce à la théorie de Flajolet. On s'intéresse aussi à une généralisation à -4- variables des polynômes de Ramanujan, et leur lien avec certaines familles d'arbres. Tout comme Guo et Zeng l'on fait précédemment avec les arbres planaires et les arbres à moitié mobiles, on interprète ces polynômes comme des fonctions génératrices des arbres de Greg et des arbres de Cayley, en construisant plusieurs bijections les mettant toutes en relation. Enfin, on s'intéresse à un ensemble partiellement ordonné de fonctions de parking à bulles. En s'intéressant à une représentation arborescente des fonctions de parking, on obtient plusieurs résultats sur la topologie de cet ensemble, notamment des résultats d'épluchabilité et d'énumération de chaînes

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}); 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})

International audience; We analyze Tartaglia's account, in 1546, of the circumstances leading to his breakthrough regarding the solution of cubic equations. He claims that he solved $x^3+rx^2=q$ in 1530, well before he could handle, in 1535, equations with a linear term $px$ (and no quadratic term). This claim is at variance with Cardano's narrative as well as with later treatments of the problem, in which the solution of equations of the latter type provides the basis for the solution of all the other types of cubic equations. We show that Tartaglia's claim is supported in his text by the use of the theory of continued proportions, that occurs as a Leitmotiv. We show that relations on continued proportions stressed by Pacioli as basic ``keys'' provide a simple derivation of the results given by Tartaglia, that is consistent with their chronological order. Thus, his narrative contains not only priority claims, but also proposes an account of the mathematical steps that led him to his results.; On analyse le récit que fait Tartaglia, en 1546, des circonstances qui l'ont conduit \`a sa découverte du mode de résolution de certaines \'equations du troisi\`eme degr\'e. Il y affirme avoir résolu l'équation $x^3+rx^2=q$ dès 1530, bien avant qu'il fût en mesure d'aborder les équations avec un terme $px$ (et sans terme carré). Ceci est incompatible avec le mode de résolution de Cardan, ainsi qu'avec ceux préconisés par les auteurs postérieurs, pour qui la solution de ces dernières équations fournit la base de celle de toutes les autres équations de degré trois. On montre que la théorie des proportions continuées tient une place centrale dans le texte de Tartaglia et que, si l'on part des ``clefs'' que Pacioli désigne comme des outils fondamentaux, on obtient une dérivation très simple des résultats de Tartaglia, dans l'ordre de leur découverte. Son récit vise donc non seulement à établir sa priorité, mais également à suggérer la démarche qui l'a conduit à ses résultats.

The contribution of the thesis is threefold. The first Problem is computing the discriminant, when the system’s dimension varies. Thus solving polynomial equations and systems by exploiting the structure and sparseness of them have been studied. Specifically, closed formulas for the degree of the sparse (mixed) discriminant and the sparse resultant of polynomial equations have been studied, as well as relationships between them. Closed formulas when one of the polynomials factors in the context of the theory of sparse elimination using the Newton polytope have been proposed. The purpose is to facilitate the computation of the sparse (or mixed) discriminant of a well-constrained polynomial system and to generalize the formula that connects the mixed discriminant with the sparse resultant. Further, we are given a system of n ⩾ 2 homogeneous polynomials in n variables which is equivariant with respect to the symmetric group of n symbols. We then prove that its resultant can be decomposed into a product of several resultants that are given in terms of some divided differences. As an application, we obtain a decomposition formula for the discriminant.The second Problem is computing the Minkowski decomposition of a polytope and the third one was the problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. We present an algorithm for computing all Minkowski Decompositions (MinkDecomp) of a given convex, integral d-dimensional polytope. Further, we consider the approximation of two NP-hard problems: Minkowski Decomposition (MinkDecomp) of lattice polygons in the plane and the closely related problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. In kD-SS, a multiset S of k-dimensional vectors is given, along with a target vector t, and one must decide whether there exists a subset of S that sums up to t. We prove, through a gap-preserving reduction from Set Cover that, for general dimension k, the corresponding optimization problem kD-SS-opt is not in APX, although the classic 1D-SS-opt has a PTAS. On the positive side, we present an approximation algorithm for 2D-SS-opt, where ε > 0 bounds the additive error in terms of some property of the input. By a reduction of the optimization version of MinkDecomp to 2D-SS-opt we approximate the former.; La contribution de la thèse est triple. Le premier problème est le calcul du discriminant, lorsque la dimension du système varie. Ainsi, la résolution d'équations et de systèmes polynomiaux en exploitant la structure de ceux-ci a été étudiée. Des formules fermées pour le degré du discriminant clairsemé (mixte) et la résultante des équations polynomiales ont été étudiées, ainsi que des relations entre eux, en utilisant le polytope de Newton. Le but est de faciliter le calcul du discriminant creuse (ou mixte) d'un système polynomial bien contraint et de généraliser la formule qui relie le discriminant mixte au résultant creux. De plus, etant donne' un système de n ⩾ 2 polynômes homogènes en n variables qui est équivariant par rapport au groupe symétrique de n symboles, nous montrons que son résultant peut être décomposé en un produit de plusieurs résultants en termes de différences divisées. En tant qu'application, nous obtenons une formule de décomposition pour le discriminant.Le deuxième problème est le calcul de la décomposition de Minkowski d'un polytope et le troisième était le problème de la somme des sous-ensembles multidimensionnels (kD-SubsetSum) dans une dimension arbitraire. Nous présentons un algorithme pour calculer toutes les décompositions de Minkowski (MinkDecomp) d'un polytope d-dimensionnel convexe et entier. Nous considérons l'approximation de deux problèmes NP-hard: la décomposition de Minkowski (MinkDecomp) des polygones dans le plan et le problème de la somme des sous-ensembles multidimensionnels (kD-SS) dans une dimension arbitraire. En kD-SS, un multiset S de vecteurs k-dimensionnels est donné, avec un vecteur cible t, et il faut décider s'il existe un sous-ensemble de S qui somme jusqu'à t. Nous prouvons, à travers une réduction gap-preserving de Set Cover, que le problème d'optimisation correspondant kD-SS-opt n'est pas dans APX, bien que le classique 1D-SS-opt ait un PTAS. Du côté positif, nous présentons un algorithme d'approximation pour 2D-SS-opt, où ε> 0 limite l'erreur additive.

The contribution of the thesis is threefold. The first Problem is computing the discriminant, when the system’s dimension varies. Thus solving polynomial equations and systems by exploiting the structure and sparseness of them have been studied. Specifically, closed formulas for the degree of the sparse (mixed) discriminant and the sparse resultant of polynomial equations have been studied, as well as relationships between them. Closed formulas when one of the polynomials factors in the context of the theory of sparse elimination using the Newton polytope have been proposed. The purpose is to facilitate the computation of the sparse (or mixed) discriminant of a well-constrained polynomial system and to generalize the formula that connects the mixed discriminant with the sparse resultant. Further, we are given a system of n ⩾ 2 homogeneous polynomials in n variables which is equivariant with respect to the symmetric group of n symbols. We then prove that its resultant can be decomposed into a product of several resultants that are given in terms of some divided differences. As an application, we obtain a decomposition formula for the discriminant.The second Problem is computing the Minkowski decomposition of a polytope and the third one was the problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. We present an algorithm for computing all Minkowski Decompositions (MinkDecomp) of a given convex, integral d-dimensional polytope. Further, we consider the approximation of two NP-hard problems: Minkowski Decomposition (MinkDecomp) of lattice polygons in the plane and the closely related problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. In kD-SS, a multiset S of k-dimensional vectors is given, along with a target vector t, and one must decide whether there exists a subset of S that sums up to t. We prove, through a gap-preserving reduction from Set Cover that, for general dimension k, the corresponding optimization problem kD-SS-opt is not in APX, although the classic 1D-SS-opt has a PTAS. On the positive side, we present an approximation algorithm for 2D-SS-opt, where ε > 0 bounds the additive error in terms of some property of the input. By a reduction of the optimization version of MinkDecomp to 2D-SS-opt we approximate the former.; La contribution de la thèse est triple. Le premier problème est le calcul du discriminant, lorsque la dimension du système varie. Ainsi, la résolution d'équations et de systèmes polynomiaux en exploitant la structure de ceux-ci a été étudiée. Des formules fermées pour le degré du discriminant clairsemé (mixte) et la résultante des équations polynomiales ont été étudiées, ainsi que des relations entre eux, en utilisant le polytope de Newton. Le but est de faciliter le calcul du discriminant creuse (ou mixte) d'un système polynomial bien contraint et de généraliser la formule qui relie le discriminant mixte au résultant creux. De plus, etant donne' un système de n ⩾ 2 polynômes homogènes en n variables qui est équivariant par rapport au groupe symétrique de n symboles, nous montrons que son résultant peut être décomposé en un produit de plusieurs résultants en termes de différences divisées. En tant qu'application, nous obtenons une formule de décomposition pour le discriminant.Le deuxième problème est le calcul de la décomposition de Minkowski d'un polytope et le troisième était le problème de la somme des sous-ensembles multidimensionnels (kD-SubsetSum) dans une dimension arbitraire. Nous présentons un algorithme pour calculer toutes les décompositions de Minkowski (MinkDecomp) d'un polytope d-dimensionnel convexe et entier. Nous considérons l'approximation de deux problèmes NP-hard: la décomposition de Minkowski (MinkDecomp) des polygones dans le plan et le problème de la somme des sous-ensembles multidimensionnels (kD-SS) dans une dimension arbitraire. En kD-SS, un multiset S de vecteurs k-dimensionnels est donné, avec un vecteur cible t, et il faut décider s'il existe un sous-ensemble de S qui somme jusqu'à t. Nous prouvons, à travers une réduction gap-preserving de Set Cover, que le problème d'optimisation correspondant kD-SS-opt n'est pas dans APX, bien que le classique 1D-SS-opt ait un PTAS. Du côté positif, nous présentons un algorithme d'approximation pour 2D-SS-opt, où ε> 0 limite l'erreur additive.

In this thesis, we present three independent works in cryptography, p-adic Hodge theory and Numerical analysis.First we present several algorithms to solve the discrete logarithm in several characteristic finite fields. We are particularly interested with the determination of classes of polynomial functions with small coefficients.The second part of the thesis deals with one of the major object of p-adic Hodge theory. We present a multi-variable version of Breuil-Kisin modules where the Lubin-Tate tower replaces the classical cyclotomic tower. He third proposes two numerical schemes for the modelisation of desorption of shale gaz.; Cette thèse comporte trois volets indépendants en cryptographie, en théorie de Hodge p-adique et en analyse numérique.La première partie consiste en l'étude d'algorithmes performants de résolution du logarithme discret. La résolution du logarithme discret consiste à déterminer les exposants d'une famille fixée de générateurs dans la décomposition des éléments du groupe. Dans le cas des groupes multiplicatifs d'un corps fini, la complexité des calculs dépendent de la taille - dite de petite, moyenne ou grande caractéristique- de la caractéristique du corps dans lesquels on effectue les calculs.Nous présentons différents algorithmes dans chacune des caractéristiques (petite, moyenne ou grande) en précisant quel est l'algorithme le plus performant dans chacun des cas.La seconde partie s'inscrit dans le contexte du programme de Langlands p-adique. Nous présentons une généralisation de l'un des outils centraux de la théorie, les modules de Breuil-Kisin, en plusieurs variables La troisième partie est un travail effectué en collaboration avec Victor Vilaça Da Rocha, Roberta Tittarelli, Richard Sambilason Rafefimanana, Victor Michel-Dansac et Benjamin Couéraud. Il a été initié lors de la treizième SEME, Semaine d'Etudes Maths Entreprises organisée par l'Agence pour les Mathématiques en Interaction avec l'Entreprise et la Société (AMIES).L'Institut Français du Pétrole et des Energies Nouvelles nous a soumis un problème de résolution numérique d'un système d'équations modélisant la désorption d'un gaz de schiste en une dimension.Nous proposons plusieurs schémas du premier ordre recourant à un traitement implicite de l'équation de relaxation. Enfin nous présentons un schéma numérique d'ordre deux en temps.

In this thesis, we present three independent works in cryptography, p-adic Hodge theory and Numerical analysis.First we present several algorithms to solve the discrete logarithm in several characteristic finite fields. We are particularly interested with the determination of classes of polynomial functions with small coefficients.The second part of the thesis deals with one of the major object of p-adic Hodge theory. We present a multi-variable version of Breuil-Kisin modules where the Lubin-Tate tower replaces the classical cyclotomic tower. He third proposes two numerical schemes for the modelisation of desorption of shale gaz.; Cette thèse comporte trois volets indépendants en cryptographie, en théorie de Hodge p-adique et en analyse numérique.La première partie consiste en l'étude d'algorithmes performants de résolution du logarithme discret. La résolution du logarithme discret consiste à déterminer les exposants d'une famille fixée de générateurs dans la décomposition des éléments du groupe. Dans le cas des groupes multiplicatifs d'un corps fini, la complexité des calculs dépendent de la taille - dite de petite, moyenne ou grande caractéristique- de la caractéristique du corps dans lesquels on effectue les calculs.Nous présentons différents algorithmes dans chacune des caractéristiques (petite, moyenne ou grande) en précisant quel est l'algorithme le plus performant dans chacun des cas.La seconde partie s'inscrit dans le contexte du programme de Langlands p-adique. Nous présentons une généralisation de l'un des outils centraux de la théorie, les modules de Breuil-Kisin, en plusieurs variables La troisième partie est un travail effectué en collaboration avec Victor Vilaça Da Rocha, Roberta Tittarelli, Richard Sambilason Rafefimanana, Victor Michel-Dansac et Benjamin Couéraud. Il a été initié lors de la treizième SEME, Semaine d'Etudes Maths Entreprises organisée par l'Agence pour les Mathématiques en Interaction avec l'Entreprise et la Société (AMIES).L'Institut Français du Pétrole et des Energies Nouvelles nous a soumis un problème de résolution numérique d'un système d'équations modélisant la désorption d'un gaz de schiste en une dimension.Nous proposons plusieurs schémas du premier ordre recourant à un traitement implicite de l'équation de relaxation. Enfin nous présentons un schéma numérique d'ordre deux en temps.

RésuméNous définissons une classe de suites de polynômes, calculés par des circuits de complexité polynomiale comprenant des additions, des soustractions. des multiplications et des sommations de Valiant. Nous montrons que cette classe est close pour la prise de la fonction-coefficient. définie au paragraphe 3 de cet article; nous en déduisons l'existence d'un circuit de complexité 72.n2, calculant le coefficient binomial de deux nombres de n chiffres, donnés en base 2. Il est par ailleurs facile de construire un circuit de complexité 17.n + 2 calculant la factorielle d'un nombre de n chiffres. La présence de 2.n sommations d'effet exponentiel dans chacun de ces circuits en affecte gravement l'intérêt pratique. II est peu probable, ou du moins peu souhaitable. qu'on puisse éliminer ces sommations sans explosion, car cela provoquerait la catastrophe cryptographique que redoutent tous les banquiers; néanmoins, nous ne savons pas séparer la classe définie ici de celle des suites de polynômes calculables en un nombre polynomial d'opérations arithmétiques. Cela n'a rien de surprenant, vu la très grande affinité qu'elle a avec la classe PSPACE: nous montrons en effet que cette classe est identique à la classe VPSPACE, définie antérieurement par Koiran et Perifel, qui apparaît ici sous une forme bien plus maniable que l'originale.

Mémoire de stage M1 Mathématiques Appliquées

Multivariate polynomial systems arise naturally in many scientific fields. These systems coming from applications often carry a specific algebraic structure.A classical method for solving polynomial systems isbased on the computation of a Gr\"obner basis of the ideal associatedto the system.This thesis presents new tools for solving suchstructured systems, where the structure is induced by the action of a particular group or a monomial structure, which include multihomogeneous or quasihomogeneous systems.On the one hand, this thesis proposes new algorithmsusing these algebraic structures to improve the efficiency of solving suchsystems (invariant under the action of a group or having a support in a particular set of monomials). These techniques allow to solve a problem arising in physics for instances out of reach until now.On the other hand, these tools improve the complexity bounds for solving several families of structured polynomial systems (systems globally invariant under the action of an abelian group or with their support in the same polytope). This allows in particular to extend known results on bilinear systems to general mutlihomogeneous systems.; Les systèmes polynomiaux à plusieurs variables apparaissent naturellement dans de nombreux domaines scientifiques. Ces systèmes issus d'applications possèdent une structure algébrique spécifique. Une méthode classique pour résoudre des systèmes polynomiaux repose sur le calcul d'une base de Gröbner de l'idéal associé au système. Cette thèse présente de nouveaux outils pour la résolution de tels systèmes structurés, lorsque la structure est induite par l'action d'un groupe ou une structure monomiale particulière, qui englobent les systèmes multi-homogènes ou quasi-homogènes. D'une part, cette thèse propose de nouveaux algorithmes qui exploitent ces structures algébriques pour améliorer l'efficacité de la résolution de systèmes (systèmes invariant sous l'action d'un groupe ou à support dans un ensemble de monômes particuliers). Ces techniques permettent notamment de résoudre un problème issu de la physique pour des instances hors de portée jusqu'à présent. D'autre part, ces outils permettent d'améliorer les bornes de complexité de résolution de plusieurs familles de systèmes polynomiaux structurés (systèmes globalement invariant sous l'action d'un groupe abélien, individuellement invariant sous l'action d'un groupe quelconque, ou ayant leur support dans un même polytope). Ceci permet en particulier d'étendre des résultats connus sur les systèmes bilinéaires aux systèmes mutli-homogènes généraux.

In this thesis we study at length the discrete logarithm problem in finite fields. In the first part, we focus on the notion of smoothness and on ECM, the fastest known smoothness test. We present an improvement to the algorithm by analyzing the Galois properties of the division polynomials. We continue by an application of ECM in the last stage of the number field sieve (NFS). In the second part, we present NFS and its related algorithm on function fields (FFS). We show how to speed up the computation of discrete logarithms in all the prime finite fields of a given bit-size by using a pre-computation. We focus later on the polynomial selection stage of FFS and show how to compare arbitrary polynomials with a unique function. We conclude the second part with an algorithm issued from the recent improvements for discrete logarithm. The key fact was to create a descent procedure which has a quasi-polynomial number of nodes, each requiring a polynomial time. This leads to a quasi-polynomial algorithm for finite fields of small characteristic, Dans cette thèse nous examinons en détail le problème du logarithme discret dans les corps finis. Dans la première partie, nous nous intéressons à la notion de friabilité et à l'algorithme ECM, le plus rapide test de friabilité connu. Nous présentons une amélioration de l'algorithme en analysant les propriétés galoisiennes des polynômes de division. Nous continuons la présentation par une application d'ECM dans la dernière étape du crible algébrique (NFS). Dans la deuxième partie, nous présentons NFS et son algorithme correspondant utilisant les corps de fonctions (FFS). Parmi les améliorations examinées, nous montrons qu'on peut accélérer le calcul de logarithme discret au prix d'un pré-calcul commun pour une plage de premiers ayant le même nombre de bits. Nous nous concentrons ensuite sur la phase de sélection polynomiale de FFS et nous montrons comment comparer des polynômes quelconques à l'aide d'une unique fonction. Nous concluons la deuxième partie avec un algorithme issu des récentes améliorations du calcul de logarithme discret. Le fait marquant est la création d'une procédure de descente qui a un nombre quasi-polynomial de noeuds, chacun exigeant un temps polynomial. Cela a conduit à un algorithme quasi-polynomial pour les corps finis de petite caractéristique

International audience; Let F a finite field, Q a given element of F[T] with positive degree and k a positive integer. The goal of this work is to study the Q-automaticity of the set of kth powers of elements of F[T] and to calculate the number of polynomials X ∈ F[T] of degree N such that the sum of digits of Xk in base Q is fixed.

This thesis is devoted to the study of some questions of multiple convergence and recurrence in ergodic theory. We distinguish between systems endowed with a single transformation and systems endowed with several commuting transformations. In the former, characteristic factors and nilsystemsplay an important role in the study of multiple convergence and recurrence. Using these tools, we extend results on convergence of weighted multiple ergodic averages of Host and Kra for the linear case to the polynomial case. As a consequence, we show that for any bounded measurable function f on an ergodic system, the sequence f(T^n x) is universally good for almost every x. In systems endowed with several commuting transformations, we use the machinery of magic systems introduced recently by Host and further properties of magic systems developed in this thesis,to extend results of Host and Kra on convergence of multiple ergodic averages along cubes with a single transformation to commuting transformations. We obtain a quantitative multiple recurrence result for two commuting transformations, similar in flavour to that of a single transformationestablished by Bergelson, Host and Kra, but with a different conclusion, Cette thèse est consacrée à l'étude de certaines questions de convergence et de récurrence multiples en théorie ergodique. Nous distinguons les systèmes munis d'une transformation et ceux munis de plusieurs transformations qui commutent. Dans les premiers, le mécanisme de facteurs caractéristiques et les nilsystèmes jouent un rôle important dans l'étude de convergence et de récurrence multiples. À l'aide de ces outils, nous étendons les résultats sur la convergence de moyennes ergodiquesmultiples pondérées de Host et Kra pour le cas linéaire au cas polynômial. En conséquence, nous montrons que pour toute fonction f mesurable bornée sur un système ergodique, la suite (f(T^n x)) est universellement bonne pour presque tout x. Quand il y a plusieurs transformations qui commutent, à l'aide de la machinerie des systèmes magiques introduite récemment par Host et développée dans cette thèse, nous étendons les résultats sur la convergence de moyennes ergodiques multiples sur les cubes de Host et Kra avec une transformation à plusieurs transformations qui commutent. Nous obtenons aussi un résultat de récurrence multiple quantitatif pour deux transformations qui commutent, similaire en faveur du cas d'une transformation établi par Bergelson, Host et Kra

Soit p un polynôme d'une variable complexe z. On peut trouver plusieurs inégalités reliant le module maximum de p et une combinaison de ses coefficients. Dans ce mémoire, nous étudierons principalement les preuves connues de l'inégalité de Visser. Nous montrerons aussi quelques généralisations de cette inégalité. Finalement, nous obtiendrons quelques applications de l'inégalité de Visser à l'inégalité de Chebyshev., Let p be a polynomial in the variable z. There exist several inequalities between the coefficents of p and its maximum modulus. In this work, we shall mainly study known proofs of the Visser inquality together with some extensions. We shall finally apply the inequality of Visser to obtain extensions of the Chebyshev inequality.

10 pages; Les implantations actuelles de la racine carrée dans des bibliothèques d'opérateurs pour FPGA utilisent presque toutes une récurrence à base d'additions. Ce choix est particulièrement bien adapté à la structure des blocs logiques élémentaires d'un FPGA. Toutefois, il peut être remis en question à présent que la plupart des FPGA haute-performance incluent un grand nombre de blocs multiplieurs et de blocs mémoires. Cet article discute l'implantation d'une racine carrée compatible IEEE-754 en utilisant ces nouvelles ressources, et compare les performances obtenues avec l'approche classique.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Thèse en cotutelle avec l'Italie (université de Udine). Composition du jury : Président : Pr. Michel WALDSCHMIDT, Université de Paris VI. Rapporteurs : Pr. Roger HEATH-BROWN, University of Oxford. Pr. Peter MÜLLER, Universität Würzburg. Examinateurs : Pr. Mohamed AYAD, Université du Littoral. Pr. Pietro CORVAJA, Università degli Studi di Udine.; Hilbert's irreducibility theorem gives the existence of a specialization preserving the irreducibility of a multivariate polynomial with rational coefficients. Effective versions have been given by P. Dèbes (1993) and by A. Schinzel and U. Zannier (1995). We discuss some attempts to improve these effective results : Dörge's method, congruence method inspired by an article of M. Fried and finally the use of a recent result of R. Heath-Brown about rational points on curves. This last attempt leads to a significant improvement of known results. We also give an application to the research of an algorithm for the factorization of bivariate polynomials.; Le théorème d'irréductibilité de Hilbert assure l'existence d'une spécialisation conservant l'irréductibilité d'un polynôme à plusieurs variables et à coefficients rationnels. Des versions effectives ont été données par P. Dèbes (1993) puis par U. Zannier et A. Schinzel (1995). Nous proposons ici diverses tentatives d'améliorer ces résultats effectifs : méthode de Dörge, méthode des congruences inspirée par un article de M. Fried et enfin une utilisation des résultats récents de R. Heath-Brown sur les points entiers d'une courbe algébrique. Cette dernière voie va nous permettre d'améliorer significativement les résultats connus. On finira par une application à la recherche d'un algorithme polynomial pour la factorisation d'un polynôme à deux indéterminées.

Thèse en cotutelle avec l'Italie (université de Udine). Composition du jury : Président : Pr. Michel WALDSCHMIDT, Université de Paris VI. Rapporteurs : Pr. Roger HEATH-BROWN, University of Oxford. Pr. Peter MÜLLER, Universität Würzburg. Examinateurs : Pr. Mohamed AYAD, Université du Littoral. Pr. Pietro CORVAJA, Università degli Studi di Udine.; Hilbert's irreducibility theorem gives the existence of a specialization preserving the irreducibility of a multivariate polynomial with rational coefficients. Effective versions have been given by P. Dèbes (1993) and by A. Schinzel and U. Zannier (1995). We discuss some attempts to improve these effective results : Dörge's method, congruence method inspired by an article of M. Fried and finally the use of a recent result of R. Heath-Brown about rational points on curves. This last attempt leads to a significant improvement of known results. We also give an application to the research of an algorithm for the factorization of bivariate polynomials.; Le théorème d'irréductibilité de Hilbert assure l'existence d'une spécialisation conservant l'irréductibilité d'un polynôme à plusieurs variables et à coefficients rationnels. Des versions effectives ont été données par P. Dèbes (1993) puis par U. Zannier et A. Schinzel (1995). Nous proposons ici diverses tentatives d'améliorer ces résultats effectifs : méthode de Dörge, méthode des congruences inspirée par un article de M. Fried et enfin une utilisation des résultats récents de R. Heath-Brown sur les points entiers d'une courbe algébrique. Cette dernière voie va nous permettre d'améliorer significativement les résultats connus. On finira par une application à la recherche d'un algorithme polynomial pour la factorisation d'un polynôme à deux indéterminées.

Stage de DEA. Rapport de stage.; L'objectif de ce stage était le développement d'une bibliothèque Coq permettant de certifier les preuves de terminaison par interprétations polynomiales. De plus, à partir d'un prototype de Coq avec réécriture, une extension de Coq V8.0 permettant de définir des systèmes de règles de réécriture, de demander à CiME de trouver une interprétation polynomiale et de générer automatiquement la preuve de correction de cette interprétation a été mise en oeuvre.

This thesis deals with the improvement of residual generation and evaluation approaches for diagnosis of uncertain systems in the particular case where parametric and unknown inputs are considered. The first part of this thesis presents robust diagnosis for uncertain systems. Major approaches proposed in literature are studied and the relevilience of the use of frequency methods for strongly uncertain systems is shown. In the second part, a residual generatorbased on a nominal model of the uncertain system is developed in order to improve fault sensitivity of residuals apd also to attenuate at best the effect of different disturb\lnces due to a natural process working and consequently, not to be detected. The residual generator is based on H_/H_ state observers'which frequency properties allows to consider fault isolation constraints respect to disturbances. The LMI optimisation techniques (Linear MatrixInequalities) are then used. The last part studies parametric uncertainty effect on residual evaluation in such a way that an optimal threshold is determined to detect the smaller fault as possible and remaining insensitive to the largest model error. The considered parametric uncertainties are represented by a polytopic form. The proposed method is based on the use of Kharitonov polynomials and on the computation of bounding sets in the frequency domain. The evaluation is achieved by a RMS type of criterion which is formulated to link the spectral properties of detection signals with their evolution in the time domain., Les travaux présentés dans cette thèse concernent l'amélioration des techniques de génération et d'évaluation de résidus pour le diagnostic des systèmes incertains pour lesquels la prise en compte d'incertitudes paramétriques et d'entrées inconnues perturbatrices est nécessaire. La première partie de la thèse traite du diagnostic robuste des systèmes incertains. Les principales approches proposées dans la littérature sont étudiées dans le cadre du travail effectué et la pertinence de l'utilisation des méthodes fréquentielles pour les systèmes fortement incertains est mise en évidence. Dans la seconde partie, le développement d'un générateur de résidus basé sur un modèle nominal du système incertain est réalisé de manière à augmenter la sensibilité des résidus aux défauts tout en atténuant au mieux l'effet des différentes perturbations inhérentes à un fonctionnement normal du procédé et par conséquentà ne pas détecter. Le générateur de résidus est basé sur les observateurs d'état de type H_/H_ dont les propriétés fréquentielles permettent de considérer au mieux les contraintes d'isolation des défauts par rapport aux incertitudes. Les techniques d'optimisation par formulation LMI (inégalités linéaires matricielles) sont alors utilisées. La troisième et dernière partie concerne l'effet des incertitudes paramétriques sur l'évaluation des résidus de manière à déterminer leseuillage optimal qui permet de détecter un défaut de taille aussi petite que possible tout en restant insensible au plus grand écart de modèle. Les incertitudes paramétriques considérées sont représentées sous une forme polytopique. La méthode proposée se fonde sur l'utilisation des polynômes de Kharitonov et sur le calcul d'enveloppes dans le domaine fréquentiel. Le critère d'évaluation, de type RMS (Root Mean Square), est formulé de manière à établirfacilement le lien entre les propriétés spectrales des signaux de détection (propriétés spectrales directement liées au générateur de résidus) et leur allure temporelle.

Contribution à un ouvrage.; International audience; The main purpose of this chapter is to show how to use algorithms and methodology provided by computer algebra to manipulate in a symbolic way the real solutions of an algebraic system of equations.

Not available, L'ouvrage présente une étude de processus autorégressifs moyenne mobiles à coefficients dépendant du temps, notes ARMA#T. Partant du calcul explicite de la fonction de Green unilatérale de certains opérateurs linéaires à coefficients polynomiaux, on donne la forme exacte de la décomposition de Wold Cramer de processus autorégressifs d'ordre 1 et d'ordre 2 dont les coefficients sont des polynomes de degré 1. Une seconde partie étudie les processus ARMA#T dont les coefficients tendent vers des constantes lorsque le temps tend vers moins l'infini. On établit une condition suffisante d'inversibilité et d'indéterminabilité pure, et on l'applique au problème de prévision. Il a été procédé à une étude par simulation de processus AR#T d'ordre 1 et 2 A coefficients homographiques par rapport au temps ; Elle a mis en évidence pour les AR#T(1) un domaine de stabilité pour l'existence d'estimateurs des coefficients

Cette thèse est consacrée a l'étude de la forme normale d'Hermite et a la conception d'algorithmes parallèles pour son calcul. Nous avons examine deux cas particuliers: le cas entier et le cas polynomial. Ce problème présente de manière intrinsèque une caractéristique du calcul formel: le grossissement des coefficients intermédiaires. Cette particularité en fait un exemple test pour évaluer la parallélisation en calcul formel. La forme normale d'Hermite pour des matrices a coefficients dans un anneau euclidien est présentée. Les concepts et propriétés sur lesquels sont bases les algorithmes sont décrits. Nous introduisons la théorie sur les réseaux et les problèmes qui lui sont attaches, la forme normale d'Hermite étant une forme canonique du réseau engendre par les colonnes de la matrice initiale. Les différents algorithmes séquentiels sont présentes. Nous étudions et comparons leurs complexités. Puis, une approche parallèle est considérée. Après la présentation des résultats théoriques de nc-réductibilité du problème, nous abordons l'étude de la parallélisation sur modèles expérimentaux. Nous définissons différents algorithmes pour les modèles a mémoire partagée et distribuée. Une implantation a été réalisée sur un hypercube fps t40 (32 processeurs). Le calcul de la forme normale d'Hermite d'une matrice 160160 à coefficients entiers a pu etre effectue en 3 heures. Ce travail s'inscrit dans le cadre du projet massivement Parallele Pac (parallel algebraic computing).

Universités : Université scientifique et médicale de Grenoble et Institut National Polytechnique

Université : Université scientifique et médicale de Grenoble

Pac est un système de calcul formel dédié a une machine Mind massivement parallèle. Dans une première partie, l'architecture du système est décrite. Elle est illustrée par une modélisation théorique et pratique de la parallélisation du produit de deux polynômes. Le système Pac est implante sur la machine t40 de Fps (32 processeurs). Dans une deuxième partie, l'arithmétique nodale en précision infinie sur les rationnels est étudiée. Différents algorithmes sont dégagés, notamment pour la multiplication, la division et le pgcd d'entiers de taille quelconque. Une vectorisation de l'arithmétique de base est discutée et expérimentée

Université : Université scientifique et médicale de Grenoble; Elements de théorie de l'approximation polynomiale par morceaux. Approximation d'une intégrale simple avec poids par une combinaison linéaire de valeurs de la fonction. Approximation d'une intégrale simple avec poids par une combinaison linéaire de valeurs de la fonction et de sa dérivée. Application à l'interpolation affine par morceaux. Approximation d'une intégrale double avec poids

Université : Université scientifique et médicale de Grenoble

Université : Faculté des sciences de l'Université de Grenoble