Made available in DSpace on 2018-08-01T22:30:14Z (GMT). No. of bitstreams: 1 tese_6990_Correção_dissert_Flavio_28_10 (1).pdf: 746942 bytes, checksum: d24587836883c9d3d4a30408eb30dc57 (MD5) Previous issue date: 2015-08-21 / O estudo de Equações Diferenciais sob o ponto de vista algébrico foi iniciado por volta de 1932 por J. F. Ritt com o trabalho "Differential Equations from de Algebraic Standpoint". Posteriormente, em 1948, Ritt publicou o livro "Differential Algebra". Trata-se de se utilizar as ferramentas da Geometria Algébrica e da Álgebra Comutativa para estudar operadores diferenciais e consequentemente, conjuntos soluções de sistemas de equações diferenciais parciais. Nesta dissertação, pretendemos fazer um estudo preliminar da Álgebra Diferencial com o objetivo principal de aplicar em problemas de soluções de equações diferenciais parciais. Os trabalhos de referências principais são Implicitization of differential rational parametric equations de X. S. Gao (2003) e Implicitization of DPPES and Deifferential Resultants de S. L. Rueda e J. R. Sendra (2008).

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2015-11-17T17:21:34Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Algebra diferencial e equacoes diferenciais polinomiais.pdf: 747919 bytes, checksum: b5dbcdc52b480ea6d11cdad84343b1c0 (MD5) / Approved for entry into archive by Morgana Andrade (morgana.andrade@ufes.br) on 2016-01-07T11:49:42Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Algebra diferencial e equacoes diferenciais polinomiais.pdf: 747919 bytes, checksum: b5dbcdc52b480ea6d11cdad84343b1c0 (MD5) / Made available in DSpace on 2016-01-07T11:49:42Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Algebra diferencial e equacoes diferenciais polinomiais.pdf: 747919 bytes, checksum: b5dbcdc52b480ea6d11cdad84343b1c0 (MD5) Previous issue date: 2015 / CAPES / O objetivo deste trabalho é estudar sistemas de equações diferenciais polinomiais paramétricas, cujo resultado principal é a determinação de uma expressão explícita para uma equação implícita. / In this dissertation we study systems of parametric differential polynomial equations. The main result is the determination of an explicit expression for an implicit such equation.

Estudaremos a teoria de bases de Gröbner em anéis de polinômios comutativos com coeficientes em uma nelnoetheriano e em anéis de operadores diferencias. Apresentaremos, em ambos casos, uma generalização do algoritmo da divisão, do S-polinômio e do algoritmo de Buchberger para calcular bases de Gröbner. / We study the theory of Gröbner bases for commutative polynomials rings over a noetherian ring and of rings of differential operators. In both cases we exhibit a generalization of the division algorithm, the S -polynomial and the Buchberger algorithm for computing Gröbner bases.

Estudaremos a teoria de bases de Gröbner em anéis de polinômios comutativos com coeficientes em uma nelnoetheriano e em anéis de operadores diferencias. Apresentaremos, em ambos casos, uma generalização do algoritmo da divisão, do S-polinômio e do algoritmo de Buchberger para calcular bases de Gröbner. / We study the theory of Gröbner bases for commutative polynomials rings over a noetherian ring and of rings of differential operators. In both cases we exhibit a generalization of the division algorithm, the S -polynomial and the Buchberger algorithm for computing Gröbner bases.

En cinématique il n'existe aucune méthode permettant de générer les conditions d'assemblage sous forme symbolique pour les systèmes de solides, éventuellement surcontraints. En revanche il existe un grand nombre de formules permettant- en principe - de calculer la mobilité. Les noms de Kutzbach, Grübler et Tchebytcheff sont associés à différentes formules bien connues mais aucune formule infaillible n'a jamais été trouvée. C'est ce qui motive notre proposition de méthodes numériques et symboliques constructives. Celles-ci permettent de générer automatiquement les conditions d'assemblage et de mobilité à partir de la connaissance des équations de fermeture des boucles de solides. Les méthodes numérique et symbolique présentées dans cette thèse se basent sur un socle commun. Elles utilisent les paramètres de Denavit-Hartenberg et les classent en deux catégories: la première catégorie, notée u pour usinage, représente les dimensions géométriques des solides, la seconde, notée m pour mobilité, représente les paramètres de position relative de deux solides en contact. Ensuite, les équations de fermeture sont obtenues par une méthode ''coordinate free'' à partir d'une matrice de Gram. C'est à cette étape que les deux méthodes diffèrent. Dans le cas de l'analyse numérique locale, le système d'équations est linéarisé. La décomposition en valeur singulière est utilisée pour l'élimination des paramètres. Nous obtenons ensuite les conditions d'assemblage dans un voisinage de la configuration initiale. Les conditions de mobilité sont calculées à partir des conditions d'assemblage issues d'un nombre fini de configurations. Dans le cas de l'analyse symbolique, nous calculons formellement la base de Gröbner associée aux équations de fermeture et cela grâce à l'algorithme FGb de Faugère. Il existe peu de références sur l'utilisation des Bases de Gröbner en cinématique, et aucune ne présente une analyse exhaustive du problème. Avec l'ordre lexicographique, nous ne gardons que des paramètres u et éliminons tous les autres. Lorsque ces relations en u sont vérifiées, elles représentent les conditions d'assemblage, dites relations de surcontraintes. Cet ensemble peut être vide lorsque le système est isocontraint. Pour générer les conditions de mobilité, nous gardons tous les u et un paramètre de mobilité. En annulant les coefficients en facteur de ce paramètre de mobilité, un nouveau système qui ne dépend que de u est construit. Les conditions de mobilité sont obtenues en calculant la base de Gröbner du nouveau système. Pour atteindre les résultats désirés, nous avons également proposé deux outils: saturation et contrainte. Ils permettent de parcourir un sous-ensemble de solutions représentées par une base de Gröbner. La confrontation des résultats obtenus dans la thèse avec ceux de la littérature, pour quelques de mécanismes connus, permet d'affirmer la validité et la complétude de la méthode.

En cinématique il n'existe aucune méthode permettant de générer les conditions d'assemblage sous forme symbolique pour les systèmes de solides, éventuellement surcontraints. En revanche il existe un grand nombre de formules permettant- en principe - de calculer la mobilité. Les noms de Kutzbach, Grübler et Tchebytcheff sont associés à différentes formules bien connues mais aucune formule infaillible n'a jamais été trouvée. C'est ce qui motive notre proposition de méthodes numériques et symboliques constructives. Celles-ci permettent de générer automatiquement les conditions d'assemblage et de mobilité à partir de la connaissance des équations de fermeture des boucles de solides. Les méthodes numérique et symbolique présentées dans cette thèse se basent sur un socle commun. Elles utilisent les paramètres de Denavit-Hartenberg et les classent en deux catégories: la première catégorie, notée u pour usinage, représente les dimensions géométriques des solides, la seconde, notée m pour mobilité, représente les paramètres de position relative de deux solides en contact. Ensuite, les équations de fermeture sont obtenues par une méthode ``coordinate free'' à partir d'une matrice de Gram. C'est à cette étape que les deux méthodes diffèrent. Dans le cas de l'analyse numérique locale, le système d'équations est linéarisé. La décomposition en valeur singulière est utilisée pour l'élimination des paramètres. Nous obtenons ensuite les conditions d'assemblage dans un voisinage de la configuration initiale. Les conditions de mobilité sont calculées à partir des conditions d'assemblage issues d'un nombre fini de configurations. Dans le cas de l'analyse symbolique, nous calculons formellement la base de Gröbner associée aux équations de fermeture et cela grâce à l'algorithme FGb de Faugère. Il existe peu de références sur l'utilisation des Bases de Gröbner en cinématique, et aucune ne présente une analyse exhaustive du problème. Avec l'ordre lexicographique, nous ne gardons que des paramètres u et éliminons tous les autres. Lorsque ces relations en u sont vérifiées, elles représentent les conditions d'assemblage, dites relations de surcontraintes. Cet ensemble peut être vide lorsque le système est isocontraint. Pour générer les conditions de mobilité, nous gardons tous les u et un paramètre de mobilité. En annulant les coefficients en facteur de ce paramètre de mobilité, un nouveau système qui ne dépend que de u est construit. Les conditions de mobilité sont obtenues en calculant la base de Gröbner du nouveau système. Pour atteindre les résultats désirés, nous avons également proposé deux outils: saturation et contrainte. Ils permettent de parcourir un sous-ensemble de solutions représentées par une base de Gröbner. La confrontation des résultats obtenus dans la thèse avec ceux de la littérature, pour quelques de mécanismes connus, permet d'affirmer la validité et la complétude de la méthode. / In mechanical kinematics analysis, no generic method allows to generate symbolic assembly conditions for mechanisms with rigid bodies (especially for overconstrained mechanisms). However, many formulas can help to compute mobility. Kutzbach, Grübler and Tchebitcheff are associated to different formulas but none of them works in every case. For this reason, we propose generic numerical and symbolic methods in order to obtain assembly and mobility conditions from closed-loop equations. The numerical and symbolic methods presented in this thesis have the same starting point. They both use Denavit-Hartenberg parameters. These parameters are divided into two types : the first is called u, representing geometric dimensions of rigid bodies ; the second type is called m (for parameters of mobility), representing the relative motion between two rigid bodies in contact. First of all, closed-loop equation are written using a coordinate free method based on Gram matrix. After this step, the two methods differ. In case of numerical analysis, the system of equations is linearized. The Singular Value Decomposition is used to eliminate parameters. We then compute assembly conditions in the neighborhood of the initial configuration. Mobility conditions are computed based on assembly conditions which result from a finite number of configurations. In case of symbolic analysis, we calculate the Gröbner basis associated with closed-loop equations in order to eliminate parameters of mobility. There are few references talking about the application of Gröbner basis in kinematics analysis. None of these references provides a well explained analysis of kinematics problem. Since we have been collaborating with Mr. Faugère, we use the package “FGb” for the elimination of parameters of mobility. With a specified order, relations between the u parameters could be computed by eliminating the m parameters. When verified, these relations are assembly conditions, also named over-constrained assembly conditions. This set of relations may be empty when the studied system is iso-constrained. To generate mobility conditions, one has to keep all u parameters and only one parameter of mobility. When mobility parameter’s coefficients vanish, the mechanism is mobile with 1 degree of freedom. To determine two kinds of conditions, we propose also two tools : saturation and constraint. They allow browsing a subset of system’s solutions which is represented by a Gröbner basis. Since our results are identical to the ones found in literature, our method is valid and complete.

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. / 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 bases de Gröbner constituent un outil important pour la résolution de systèmes d'équations algébriques, et leur calcul est souvent la partie difficile de la résolution. Cette thèse est consacrée à des analyses de complexité de calculs de bases de Gröbner pour des systèmes surdéterminés (le nombre m d'équations est supérieur au nombre n d'inconnues). Dans le cas générique (”aléatoire”), des outils existent pour analyser la complexité du calcul de base de Gröbner pour un système non surdéterminé (suites régulières, borne de Macaulay). Nous étendons ces résultats au cas surdéterminé, en définissant les suites semi-régulières et le degré de régularité dont nous donnons une analyse asymptotique précise. Par exemple dès que m > n nous gagnons un facteur 2 sur la borne de Macaulay, et un facteur 11,65 quand m = 2n (ces facteurs se répercutent sur l'exposant de la complexité globale). Nous déterminons la complexité de l'algorithme F5 (J-C. Faugère) de calcul de base de Gröbner. Ces résultats sont appliqués en protection de l'information, où les systèmes sont alors considérés modulo 2 : analyse de la complexité des attaques algébriques sur des cryptosystèmes, algorithmes de décodage des codes cycliques. Dans ce dernier cas, une remise en équation complète du problème conduit à utiliser des systèmes de dimension positive dont la résolution est de manière surprenante plus rapide. Nous obtenons ainsi un algorithme de décodage efficace de codes précédemment indécodables, permettant un décodage en liste et applicable à tout code cyclique.

Récemment, la géomatique grand public s'est emparée de la représentation 3D des bâtiments. Le besoin d'acquérir des images et de les restituer en 3D, sous forme de maquettes parfaitement fidèles à la réalité, est ainsi devenu immense. On a donc vu depuis une décennie, se construire des véhicules capables de photographier en stéréoscopie des villes entières, et il a fallu concevoir les algorithmes capables de traiter ces énormes quantités d'images. Très naturellement, les industriels en charge de ces problèmes se sont tournés vers les outils de vision par ordinateur et de robotique, très bien adaptés aux calculs temps réel, oubliant l'essentiel de l'héritage de la photogrammétrie, orientée quant à elle vers une extrême précision, jugée ici comme une moindre priorité. Néanmoins, les algorithmes publiés en vision par ordinateur présentaient de réels défauts lorsqu'ils étaient appliqués à des surfaces planes alors que ce cas est extrêmement courant dans des scènes urbaines pour traiter les façades de bâtiments. Les recherches que nous avons menées ont porté sur la recherche de solutions nouvelles, capables d'exploiter les spécificités de telles images : tout d'abord, nos travaux ont cherché à accélérer l'orientation relative des images, en tirant bénéfice des points de fuite figurant dans celles-ci. Pour ce faire, de nouvelles méthodes d'extraction automatique de ces points ont été mises au point et évaluées plus performantes que celles disponibles jusqu'ici. Ensuite, nos recherches ont porté sur les moyens de corriger le défaut évoqué précédemment pour les surfaces planes, et de nouveaux algorithmes capables de donner en temps quasi-réel de bonnes solutions d'orientation relative pour de telles scènes ont été développés. A cette fin, de nouveaux outils mathématiques ont été utilisés : les bases de Gröbner. En rupture complète avec les solutions linéaires habituelles, ils permettent en effet une résolution directe des équations sous leur forme polynomiale. Ils évitent de passer par l'habituelle linéarisation, qui nécessitait une solution approchée parfois difficile à trouver dans les usages de photogrammétrie terrestre. Finalement, nos travaux ont porté sur les moyens d'accélérer les méthodes d'orientation relative en exploitant opportunément la connaissance de la direction verticale, obtenue par exemple à l'aide du nouvel algorithme de détection des points de fuite. Au total, la thèse présente une remise à plat générale des solutions permettant l'orientation et la localisation de tout un ensemble d'images.

Ha Minh Lam et M. Morales ont introduit une classe d'idéaux binomiaux qui est une extension binomiale d'idéaux monomiaux libres de carrés.Étant donné I un idéal monomial quadratique de k[x] libre de carrés et J une somme d'idéaux de scroll de k[z] qui satisfont certaines conditions, nous définissons l'extension binomiale de I comme B=I+J. Le sujet de cette thèse est d'étudier le nombre p plus grand tel que les sizygies de B son linéaires jusqu'au pas p-1. Sous certaines conditions d'ordre imposées sur les facettes du complexe de Stanley-Reisner de I nous obtiendrons un ordre > pour les variables de l'anneau de polynomes k[z]. Ensuite nous prouvons pour un calcul des bases de Gröbner que l'idéal initial in(B), sous l'ordre lexicographique induit par l'ordre de variables >, est quadratique libre de carrés. Nous montrerons que B est régulier si et seulement si I est 2-régulier. Dans le cas géneral, lorsque I n'est pas 2-régulier nous trouverons une borne pour l'entier q maximal qui satisfait que les premier q-1 sizygies de B son linéaires. En outre, en supossant que J est un idéal torique et en imposant des conditions supplémentaires, nous trouveron une borne supérieure pour l'entier q maximal qui satisfait que les premier q-1 sizygies de B son linéaires. En imposant des conditions supplémentaires, nous prouverons que les deux bornes sont égaux.