Loading...
Please wait, while we are loading the content...
Similar Documents
Ideal Membership Problem and Gröbner Basis
| Content Provider | Semantic Scholar |
|---|---|
| Author | Heroor, Chennah |
| Copyright Year | 2015 |
| Abstract | We note that an equivalent formulation of the problem is: Does there exist polynomials g1, ...gm such that f = ∑ figi. We will solve this question by using Gröbner bases. The Gröbner basis gives us a representation of an ideal, that allows us to easily decide membership, and the basis is constructed via Buchberger’s algorithm. An important question regarding Buchberger’s algorithm is its complexity, or given a set of n polynomials with degree m, what is the running time of the algorithm. In order to learn the complexity of this problem, it becomes necessary to determine the degree of the polynomials gi. However, we leave the discussion of the algorithm’s complexity to the next lecture. First, we focus on the idea of finding the remainder of a polynomial modulo an ideal. This problem is simple if we restrict ourselves to univariate polynomials. We order the polynomials by the highest degree and repeatedly take the remainder modulo the highest degree we can remove. However, with multivariate polynomials, we have a notion of preference: which terms would we prefer to reduce? For example, consider the polynomial x2y + y2x divided by x + y. It is unclear what answer should be, as the remainder can be written as either a polynomial purely in x or purely in y, or we can reduce the total degree of the polynomial. The Gröbner basis seeks to solve this question by imposing an order on the division for multivariate polynomials. We first order the monomials in K[x1, . . . , xn] by some total order (called an admissible order) such that |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://people.csail.mit.edu/madhu/ST15/scribe/lect20.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
