452 research outputs found
Groebner bases and algorithms
No full textLet R be a polynomial ring in n variables over k and f be an element of R. An ideal I of R generated by s polynomials f_(1),···,f_(s) is denoted by ◁수식 삽입▷(원문을 참조하세요)
In this thesis, we study definition of Groebner bases of ideals in R and investigate properties of Groebner bases and algorithms to find them.
In particular, we give a different proof to show the Buchberger Algorithm and construct an algorithm to find a reduced Groebner basis.
We also use two algoritms to find universal Groebner basis.;R을 n개의 변수를 갖는 polynomial ring이라 하자. 유한개의 다항식으로 생성되는 R의 ideal I는 다음과 같다. ◁수식 삽입▷(원문을 참조하세요)
이 논문에서 우리는 ideal I의 Groebner bases의 정의를 공부하고 그들의 성질과 그들을 찾는 알고리즘에 대해 조사한다.
특별히 Buchberger의 알고리즘을 다른 방법으로 증명해 보고 reduced Groebner basis를 찾는 알고리즘을 구성한다. 또한 이들 알고리즘을 이용하여 주어진 ideal I의 universal Groebner basis를 찾아본다.1. INTRODUCTION 1
2. Monomials and Groebner basis 3
3. Minimal Groebner Basis 14
4. Reduced Groebner Basis 18
S Universal Groebner basis 24
Reference 35
논문초록 3
Experiments with the Groebner Walk
No full textThe Groebner Walk is an algorithm which converts a given Groebner basis of a polynominal ideal I of arbitrary dimension to a Groebner basis of I with respect to another term order. The conversion is done in several steps (the walk) following a path in the Groebner fan of I. We report on our experiences with a first implementation of the walk connected with a state-of-the-art Groebner basis package. We can thus give an estimation when it is promising to apply the walk for the computation of lexicographic Groebner Bases. Then, we discuss several algorithmic variations as well as important implementation techniques. Based on our experience, we improved the walk algorithm further performing fewer intermediate reductions, for additional speed-ups. We also describe path perturbation a refinement in path-planning, and evaluate its performance implications in practice. These different improvements elevate the walk to a new level of performance. (orig.)SIGLEAvailable from TIB Hannover: RR 4367(96-15) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDEGerman
Symbolic Analysis for Boundary Problems: From Rewriting to Parametrized Groebner Bases
No full textWe review our algebraic framework for linear boundary problems (concentrating on ordinary differential equations). Its starting point is an appropriate algebraization of the domain of functions, which we have named integro-differential algebras. The algebraic treatment of boundary problems brings up two new algebraic structures whose symbolic representation and computational realization is based on canonical forms in certain commutative and noncommutative polynomial domains. The first of these, the ring of integro-differential operators, is used for both stating and solving linear boundary problems. The other structure, called integro-differential polynomials, is the key tool for describing extensions of integrodifferential algebras. We use the canonical simplifier for integro-differential polynomials for generating an automated proof establishing a canonical simplifier for integro-differential operators. Our approach is fully implemented in the THEOREMA system; some code fragments and sample computations are included
Groebner Rings and Modules (Extended Abstract)
No full textOriginally, the theory of Groebner bases has been introduced, in [Buchberger 1970], for the case of commutative polynomials over coefficient fields. Since then, several generalizations of the theory for more general classes of rings have been proposed in the literature. Most of these generalizations prove theorems of the following kind: If Groebner bases can be constructed in a certain (commutative) ring R then Groebner bases can also be constructed in the polynomial ring over R. In [Buchberger 1984] I proposed a different approach for generalizing Groebner bases theory which I think is more natural and more useful: I formulated axioms for a ring R that guarantee that one can construct Groebner bases in R ("Construction Theorem") and then I proved that, if R satisfies these axioms, then also the polynomial ring over R satisfies these axioms ("Conservation Theorem"). S. Stifter, a PhD student of mine, later proved that conservation theorems can also be proved for other ring constructions, e.g. the construction of direct products of rings, see [Stifter 1987]. The axioms I proposed were, however, quite involved. In particular, I had to introduce a "set of multipliers " in R. In this talk, I would like to propose a new approach to the axiomatization of Groebner bases theory, which is still along the lines of [Buchberger 1984] but avoids speaking about sets of multipliers. In the talk, I will report on the current state of formulating the appropriate axioms in the new approach and proving the corresponding construction and conservation theorems. I wil
Groebner bases
No full textConsider a polynomial ring k[χ] in one indeterminate over a field k. Given a polynomial in k[χ], one is able to determine whether that polynomial lies in a given ideal I C k[χ] by applying the Division Algorithm in one variable. The condition r = 0 is necessary and sufficient for membership to the ideal. However, this is not the case for the polynomial ring k[χl...,χn] because remainders generated by the Division Algorithm in n variables are not unique.By the Hilbert Basis Theorem, any given ideal J C k[χl...,χn] has a finite generating set, that is, J = 〈gl,...,gt〉. Then gl,...,gt are a basis of J. They are also known as generators of J. A Groebner basis of J is a special basis whereby the remainder on division by the generators is unique with respect to some fixed ordering. We can then determine ideal membership by checking the remainder.Besides studying the basic theory of Groebner bases, we will look at how we can construct them using the Buchberger's Algorithm and S-polynomials.. Groebner bases also have several applications. The two applications that we are going to study are ideal membership and solving systems of polynomial equations
Bigraded Castelnuovo-Mumford regularity and Groebner bases
No full textInternational audienceWe study the relation between the bigraded Castelnuovo-Mumford regularity of abihomogeneous ideal in the coordinate ring of the product of two projective spaces and the bidegrees of a Groebner basis of with respect to the degree reverse lexicographical monomial order in generic coordinates. For the single-graded case, Bayer and Stillman unraveled all aspects of this relationship forty years ago and these results led to complexity estimates for computations with Groebner bases. We build on this work to introduce a bounding region of the bidegrees of minimal generators of bihomogeneous Groebner bases for . We also use this region to certify the presence of some minimalgenerators close to its boundary. Finally, we show that, up to a certain shift, this region is related to the bigraded Castelnuovo-Mumford regularity of
MATHsAiD: A Mathematical Theorem Discovery Tool
No full textIn the field of automated reasoning, one of the most challenging (even if perhaps, somewhat overlooked) problems thus far has been to develop a means of discerning, from amongst all the truths that can be discovered and proved, those which are either useful or interesting enough to be worth recording. As for human reasoning, mathematicians are well known for their predilection towards designating certain discoveries as theorems, lemmas, corollaries, etc., whilst relegating all others as relatively unimportant. However, precisely how mathematicians determine which results to keep, and which to discard, is perhaps not so well known. Nevertheless, this practice is an essential part of the mathematical process, as it allows mathematicians to manage what would otherwise be an overwhelming amount of knowledge. MATHsAiD is a system intended for use by research mathematicians, and is designed to produce high quality theorems, as recognised by mathematicians, within a given theory. The only input required is a set of axioms and definitions for each theory. In this paper we briefly describe some of the more important methods used by MATHsAiD, most of which are based primarily on the human mathematical proces
The Groebner fan of a differential ideal in the ring of differential polynomials
No full textBy the Newton's lemma the author mean that the coefficient of the dominant term of a series solution of an equation satisfies the characteristic equation related to an edge of the Newton polygon of the equation, while the dominant exponent equals the slope of the edge. Originally, Newton considered an algebraic equation, later these considerations have been extended to systems of equations and also to differential equations. The Newton's lemma is proved in a general setting of the valuations on extensions of the ring of Laurent polynomials , as solutions, and on the ring of differential polynomials, induced by linear functions on exponent vectors. This allows the author to introduce the Groebner fan of a differential ideal
Solving polynomial equation systems II: Macaulay's Paradigm and Groebner Techology
No full textThe second volume of this comprehensive treatise focusses on Buchberger theory and its application to the algorithmic view of commutative algebra. In distinction to other works, the presentation here is based on the intrinsic linear algebra structure of Groebner bases, and thus elementary considerations lead easily to the state-of-the-art in issues of implementation. The same language describes the applications of Groebner technology to the central problems of commutative algebra. The book can be also used as a reference on elementary ideal theory and a source for the state-of-the-art in its algorithmization. Aiming to provide a complete survey on Groebner bases and their applications, the author also includes advanced aspects of Buchberger theory, such as the complexity of the algorithm, Galligo's theorem, the optimality of degrevlex, the Gianni-Kalkbrener theorem, the FGLM algorithm, and so on. Thus it will be essential for all workers in commutative algebra, computational algebra and algebraic geometry
Groebner Basis in Geodesy and Geoinformatics
No full textIn geodesy and geoinformatics, most problems are nonlinear in nature and often require the solution of systems of polynomial equations. Before 2002, solutions of such systems of polynomial equations, especially of higher degree remained a bottleneck, with iterative solutions being the preferred approach. With the entry of Groebner basis as algebraic solution to nonlinear systems of equations in geodesy and geoinformatics in the pioneering work “Gröbner bases, multipolynomial resultants and the Gauss Jacobi combinatorial algorithms : adjustment of nonlinear GPS/LPS observations", the playing field changed. Most of the hitherto unsolved nonlinear problems, e.g., coordinate transformation problems, global navigation satellite systems (GNSS)'s pseudoranges, resection-intersection problems in photogrammetry, and most recently, plane fitting in point clouds in laser scanning have been solved. A comprehensive overview of such applications are captured in the first and second editions of our book Algebraic Geodesy and Geoinformatics published by Springer. In the coming third edition, an updated summary of the newest techniques and methods of combination of Groebner basis with symbolic as well as numeric methods will be treated. To quench the appetite of the reader, this presentation considers an illustrative example of a two-dimension coordinate transformation problem solved through the combination of symbolic regression and Groebner basis
- …
