Generalising the divisibility relation of terms we introduce the lattice of so-called involutive divisions and define the admissibility of such an involutive division for a given set of terms. Based on this theory we present a new approach for building up a general theory of involutive bases of polynomial ideals. In particular, we give algorithms for checking the involutive basis property and for completing an arbitrary basis to an involutive one. It turns out that our theory is more constructive and more exible than the axiomatic approach to general involutive bases due to Gerdt and Blinkov. Finally, we show that an involutive basis contains more structural information about the ideal of leading terms than a Gröbner basis and that it is straight forward to compute the (affine) Hilbert function of an ideal I from an arbitrary involutive basis of I.

This paper covers basic theory of Grobner Bases and an algebraic analysis of the linear constant coefficient partial differential operators, specifically the Cauchy-Fueter operator. We will review examples and theory of regular and biregular functions in several quaternionic variables. / text

<p>New emission legislations introduced in the European Union and the U.S. have made truck manufacturers face stricter requirements for low emissions and on-board diagnostic systems. The on-board diagnostic system typically consists of several tests that are run when the truck is driving. One way to construct such tests is to use so called consistency relations. A consistency relation is a relation with known variables that in the fault free case always holds. Calculation of a consistency relation typically involves eliminating unknown variables from a set of equations.</p><p>To eliminate variables from a differential polynomial system, methods from differential algebra can be used. In this thesis, the purely algebraic Gröbner basis algorithm and the differential Rosenfeld-Gröbner algorithm implemented in the Maple package Diffalg have been compared and evaluated. The conclusion drawn is that there are no significant differences between the methods. However, since using Gröbner basis requires differentiations to be made in advance, the recommendation is to use the Rosenfeld-Gröbner algorithm.</p><p>Further, attempts to calculate consistency relations using the Rosenfeld-Gröbner algorithm have been made to a real application, a model of a Scania diesel engine. These attempts did not yield any successful results. It was only possible to calculate one consistency relation. This can be explained by the high complexity of the model.</p>

New emission legislations introduced in the European Union and the U.S. have made truck manufacturers face stricter requirements for low emissions and on-board diagnostic systems. The on-board diagnostic system typically consists of several tests that are run when the truck is driving. One way to construct such tests is to use so called consistency relations. A consistency relation is a relation with known variables that in the fault free case always holds. Calculation of a consistency relation typically involves eliminating unknown variables from a set of equations. To eliminate variables from a differential polynomial system, methods from differential algebra can be used. In this thesis, the purely algebraic Gröbner basis algorithm and the differential Rosenfeld-Gröbner algorithm implemented in the Maple package Diffalg have been compared and evaluated. The conclusion drawn is that there are no significant differences between the methods. However, since using Gröbner basis requires differentiations to be made in advance, the recommendation is to use the Rosenfeld-Gröbner algorithm. Further, attempts to calculate consistency relations using the Rosenfeld-Gröbner algorithm have been made to a real application, a model of a Scania diesel engine. These attempts did not yield any successful results. It was only possible to calculate one consistency relation. This can be explained by the high complexity of the model.

We present a method for determining the reduced Gröbner basis with respect to a given admissible term order of order type ! of the intersection ideal of an infinite sequence of polynomial ideals. As an application we discuss the Lagrange type interpolation on algebraic sets and the 'approximation' of the ideal I of an algebraic set by zero dimensional ideals, whose affine Hilbert functions converge towards the affine Hilbert function of I.

Les nombres p-adiques sont un analogue des nombres réels plus proche de l’arithmétique. L’avènement ces dernières décennies de la géométrie arithmétique a engendré la création de nombreux algorithmes utilisant ces nombres. Ces derniers ne peuvent être de manière générale manipulés qu’à précision finie. Nous proposons une méthode, dite de précision différentielle, pour étudier ces problèmes de précision. Elle permet de se ramener à un problème au premier ordre. Nous nous intéressons aussi à la question de savoir quelles bases de Gröbner peuvent être calculées sur les p-adiques. / P-Adic numbers are a field in arithmetic analoguous to the real numbers. The advent during the last few decades of arithmetic geometry has yielded many algorithms using those numbers. Such numbers can only by handled with finite precision. We design a method, that we call differential precision, to study the behaviour of the precision in a p-adic context. It reduces the study to a first-order problem. We also study the question of which Gröbner bases can be computed over a p-adic number field.

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.

<p>Let S be a polynomial ring K[x1,...,xn] over a field K and let F be a non-negatively graded free module over S generated by m basis elements. In this thesis, we study four kinds of upper bounds: degree bounds for Gröbner bases of submodules of F, bounds for arithmetic degrees of S-ideals, regularity bounds for radicals of S-ideals, and Stillman bounds. </p> <p><br></p> <p>Let M be a submodule of F generated by elements with degrees bounded above by D and dim(F/M)=r. We prove that if M is graded, the degree of the reduced Gröbner basis of M for any term order is bounded above by 2[1/2((Dm)^{n-r}m+D)]^{2^{r-1}}. If M is not graded, the bound is 2[1/2((Dm)^{(n-r)^2}m+D)]^{2^{r}}. This is a generalization of bounds for ideals in a polynomial ring due to Dubé (1990) and Mayr-Ritscher (2013).</p> <p><br></p> <p>Our next results are concerned with a homogeneous ideal I in S generated by forms of degree at most d with dim(S/I)=r. In Chapter 4, we show how to derive from a result of Hoa (2008) an upper bound for the regularity of sqrt{I}, which denotes the radical of I. More specifically we show that reg(sqrt{I})<= d^{(n-1)2^{r-1}}. In Chapter 5, we show that the i-th arithmetic degree of I is bounded above by 2*d^{2^{n-i-1}}. This is done by proving upper bounds for arithmetic degrees of strongly stable ideals and ideals of Borel type.</p> <p><br></p> <p>In the last chapter, we explain our progress in attempting to make Stillman bounds explicit. Ananyan and Hochster (2020) were the first to show the existence of Stillman bounds. Together with G. Caviglia, we observe that a possible way of making their results explicit is to find an effective bound for an invariant called D(k,d) and supplement it into their proof. Although we are able to obtain this bound D(k,d) and realize Stillman bounds via an algorithm, it turns out that the computational complexity of Ananyan and Hochster's inductive proof would make the bounds too large to be meaningful. We explain the bad behavior of these Stillman bounds by giving estimates up to degree 3.</p>

In the presented work we define non-commutative Gröbner bases including the necessary basis of non- commutative algebra theory and notion admissible ordering. We present non-commutative variant of the Buchberger algorithm and study how the algorithm can be improved. Analogous to the Gebauer-Möller criteria lead us to detect almost all unnecessary obstructions in the non-commutative case. The obstructions are graphically ilustrated. The Buchberger algorithm can be improved within redundant polynomials. This work is a summary and its specification of the results of some known authors engaged in this field. Presented definitions are ilustrated on examples. We perform proves of some of the statements which have been proven differently by other authors. Powered by TCPDF (www.tcpdf.org)