159,059 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
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
Appropriate Similarity Measures for Author Cocitation Analysis
No full textWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Some examples for solving systems of algebraic equations by calculating groebner bases
No full textSome notes on the computation of Groebner Bases using Buchberger's algorithm over different coefficient domains and the solution of systems of algebraic equations using Groebner bases are given. Examples demonstrate applicability and its current timits, and show the wide range of problems tractable by this method. The choices of an appropriate variable ordering and a suitable term ordering are of crucial importance for the computing time and space allocation. The "optimal" variable ordering is considered, and an improvement for the selection of wdid solutions of the system of algebraic equations is described
- …
