Unformatted text preview:

Gröbner Basis ReductionSolving systems of polynomial equationsTypical problem. (From von zur Gathen, p 565)Slide 4The ideal (polynomial)Trivial observationsSimplest may not be smallestOrdering MonomialsEvery non-zero poly P can be written this wayCan a polynomial P be reduced?Does that tell us what to do?Def. of Standard or Grobner BasisThe idea behind Buchberger’s methodBuchberger’s algorithmBuchberger’s algorithm, improvementsApplications of “ideal theory”Richard Fateman CS 282 Lecture 14b 1Gröbner Basis ReductionLecture 14bRichard Fateman CS 282 Lecture 14b 2Solving systems of polynomial equations•Two (or more) polynomials p, q in one variable X, find the common solutions: Compute g=GCD(p,q). Find the roots of g. They are the common roots of p and q.•Two (or more) LINEAR equations in some set of variables: Compute the solution via Gaussian elimination or similar method.•Both are special cases of Gröbner/Grobner/Groebner basis calcs.•[named by Bruno Buchberger for his thesis advisor, (1965); who first “discovered” it is in dispute, but Buchberger clearly popularized it.]Richard Fateman CS 282 Lecture 14b 3Typical problem. (From von zur Gathen, p 565)•Set up a robot arm and joint: governed by simple equations. Where can it reach?1 2 x,yz,wx2 + y2 - 4 = 0 and(x-z)2+(y-w)2-1 = 0 determines a POLYNOMIAL IDEALRichard Fateman CS 282 Lecture 14b 4Typical problem. (From von zur Gathen, p 565)•Set up a robot arm and joint: governed by simple equations. Where can it reach?1 2 x,yz,wQuestion: can the robot reach a point on the line u= v + Richard Fateman CS 282 Lecture 14b 5The ideal (polynomial)•The ideal generated by a family of generators consists of the set of linear combinations of these generators, with constant coefficients. P,Q are equivalent wrt an ideal if their difference belongs to the ideal.Richard Fateman CS 282 Lecture 14b 6Trivial observations•There are many systems of generators for each ideal. We can add any linear combination of them to the description.•We want to find the “simplest.”•To find the simplest, for each polynomial, find its most complex monomial, and try to get rid of it, by simplification using other identities in the idea.Richard Fateman CS 282 Lecture 14b 7Simplest may not be smallest•(s20-1,s2+c3-1}  •{ - 10c3 + 45c6 - 120c9 + 210c12 - 252c15 + 210c18 - 120c21 + 45c24 - 10c27 + c30, -1 + c3 + s2}•Simpler if any polynomial in c is simpler than any polynomial in s. If you are counting number of characters, it can grow exponentially.•(Grobner basis program in Mathematica did this)Richard Fateman CS 282 Lecture 14b 8Ordering Monomials•Lexicographic: a<b<c…<d•a2 < ab < ac..•Same lex, then go by degree a2<a3<a4 •In general x< y then xc < yc•Alternative: total degree then lex. E.g. b3<a4•Alternative: total degree then reverse lex.Richard Fateman CS 282 Lecture 14b 9Every non-zero poly P can be written this way•Principal monomial plus lower order terms:• i0 aiXi with Xi being a product of powers. If we let X0 be the “largest” then a0X0 is the principal monomial•Then P = a0X0+ i1 aiXi and MP=a0X0.•A polynomial P is reduced with respect to G, a finite set of polys and > a fixed order if no principal monomial of an element of G divides the principal monomial of P.Richard Fateman CS 282 Lecture 14b 10Can a polynomial P be reduced?•P = a0X0+ i1 aiXi •A polynomial P is COMPLETELY reduced with respect to G, a finite set of polys and > a fixed order if no principal monomial of an element of G divides the any principal monomial of P.•If P is NOT completely reduced, we can subtract from it a multiple of an element of G and eliminate this monomial, get a new polynomial less than the previous one. That is, for some h, P-hgi is in the same ideal but simpler. (maybe c*P-h*gi )Richard Fateman CS 282 Lecture 14b 11Does that tell us what to do?•If P is NOT completely reduced, we can subtract from it a multiple of an element of G and eliminate this monomial, get a new polynomial less than the previous one. That is, for some h, P-hgi is in the same ideal but simpler. Which element matters for efficiency. Also, there are variations by analogy with the GCD / PRS discussions.Richard Fateman CS 282 Lecture 14b 12Def. of Standard or Grobner Basis•A system of generators (or basis) G of an ideal I is called a standard basis or Grobner basis (with respect to a given order <) if every reduction of a polynomial P of I to a reduced polynomial (wrt G) always gives 0.•Dividing P wrt a system of polynomials.. Keep dividing as long as you can (see vzg sec. 21)Richard Fateman CS 282 Lecture 14b 13The idea behind Buchberger’s method•An arbitrary ideal basis does not, in general constitute a Grobner basis. Buchberger proposed to “complete” the basis by adding a finite number of new polynomials to it. This requires only consideration of a finite number of “S polynomials” of pairs of polynomials from the initial ideal.•Spoly(p,q)=lcm(Mp,Mq)(p/Mp-q/Mq) where Mq is the principal monomial for polynomial q.Richard Fateman CS 282 Lecture 14b 14Buchberger’s algorithm•Start with a collection of polynomials G representing an ideal.•Pick 2 different polynomials p,q from G.•Suppose Spoly(p,q) reduces (in G) to r. If r=0, then pick another pair until there aren’t any more distinct pairs. If r is not 0, add it to G, and repeat.•If you want a unique / reduced GB, reduce each P with respect to G-{P}.Richard Fateman CS 282 Lecture 14b 15Buchberger’s algorithm, improvements•If you want a unique / reduced GB, reduce each P with respect to G-{P}.•If you want to improve efficiency, you can check various cases (“criterion 1,2”) which vastly reduce the time, though it is still exponential. •Total degree ordering is usually much faster.•Parallel computation has been explored several times.Richard Fateman CS 282 Lecture 14b 16Applications of “ideal theory”•Computing modulo side-relations (e.g. our running example of sin2(x)+cos2(x)=1).•Geometry theorem proving (Wu, Chou, Kapur, Kutzler and Stifter).•Large stream of publications on variations.--additional


View Full Document
Download Gröbner Basis Reduction
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Gröbner Basis Reduction and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Gröbner Basis Reduction 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?