Polynomial Division, Remainder,GCDDivision with remainder, integersDivision with remainder, polynomialsExample (this is typeset from Macsyma)Long division: In detailThat was lucky: Divisible AND we could represent quotient and remainder over Z[x].Slide 7Macsyma writes it out this wayIn general that denominator gets nasty:Symbols (other indeterminates) are worsePseudo-remainder.. Pre-multiplying by power of leading coefficient... a3Order of variables matters too.Some activitives (Gröbner Basis reduction) divide by several polynomialsEuclid’s algorithm (generalized to polynomials): Polynomial remainder sequenceHow bad could this be? (Knuth, vol 2 4.6.1)Making the denominators disappear by premultiplication....Compute the content of each polynomialBetter but costlier, divide by the contentSome AlternativesSample calculation mod 13 drops some coefficients!This modular approach is actually better than this...Another Alternative: the subresultant PRSThe newest thought: Heuristic GCD, the idea is to evaluateThe GCD papers, selected, online in /readings. Recent “reviews”The GCD papers, selected, online in /readings. Classics.The GCD papers, selected, online in /readings. The sparse GCDsSlide 27Richard Fateman CS 282 Lecture 7 1Polynomial Division, Remainder,GCDLecture 7Richard Fateman CS 282 Lecture 7 2Division with remainder, integers•p divided by s to yield quotient q and remainder r: 100 divided by 3•p = s*q + r•100 = 3*33 + 1•by some measure r is less than s: 0<r<sRichard Fateman CS 282 Lecture 7 3Division with remainder, polynomials•p(x) divided by s(x) to yield quotient q(x) and remainder r(x):•p = s*q + r•by some measure (degree in x, usually) r<s•notice there is an asymmetry if we have several variables..Richard Fateman CS 282 Lecture 7 4Example (this is typeset from Macsyma)quotient, remainderRichard Fateman CS 282 Lecture 7 5Long division: In detail) x3+3x2+3x+1x+1 x2x3+ x22x2+3x+ 2x2x2+2xx+1+1x+10Richard Fateman CS 282 Lecture 7 6That was lucky: Divisible AND we could represent quotient and remainder over Z[x].•Consider this minor variation -- the divisor is not monic (coefficient 1) : 2x+1 instead of x+1. This calculation needs Q[x] to allow us to do the division...Richard Fateman CS 282 Lecture 7 7Long division: In detail) x3+ 3x2+ 3x +12x+1 1/2x2x3+ 1/2x25/2x2+3x + 5/4x5/2x2+5/4x7/4x+1+7/87/4x+7/81/8Richard Fateman CS 282 Lecture 7 8Macsyma writes it out this wayRichard Fateman CS 282 Lecture 7 9In general that denominator gets nasty:•5^4 is 625.Richard Fateman CS 282 Lecture 7 10Symbols (other indeterminates) are worseRichard Fateman CS 282 Lecture 7 11Pseudo-remainder.. Pre-multiplying by power of leading coefficient... a3note: we are doing arithmetic in Z[a,b][x] not Q(a,b)[x].Richard Fateman CS 282 Lecture 7 12Order of variables matters too.•Consider x2+y2 divided by x+y, main variable x.•Quotient is x-y, remainder 2y2 . That is,• x2+y2 = (x-y)(x+y) + 2y2 .•Now consider main variable y•Quotient is y-x, remainder 2x2 . That is,• x2+y2 = (-x+y)(x+y) + 2x2 .Richard Fateman CS 282 Lecture 7 13Some activitives (Gröbner Basis reduction) divide by several polynomials•P divided by s1, s2, ... to produce •P= q1s1+12s2+... (not necessarily unique)Richard Fateman CS 282 Lecture 7 14Euclid’s algorithm (generalized to polynomials): Polynomial remainder sequence•P1, P2 input polynomials•P3 is remainder of divide(P1,P2)•.... Pn is remainder of divide(Pn-2,Pn-1)•If Pn is zero, the GCD is Pn-1•At least, an associate of the GCD. It could have some extraneous factor (remember the a3?)Richard Fateman CS 282 Lecture 7 15How bad could this be? (Knuth, vol 2 4.6.1)Euclid’s alg. over QRichard Fateman CS 282 Lecture 7 16Making the denominators disappear by premultiplication....Euclid’s alg. over Z, using pseudoremaindersRichard Fateman CS 282 Lecture 7 17Compute the content of each polynomialEuclid’s alg. over Q. Each coefficient is reduced... not much help.111/99/2550/ 197731288744821/ 543589225Richard Fateman CS 282 Lecture 7 18Better but costlier, divide by the contentEuclid’s alg. over Q, content removed: primitive PRSRichard Fateman CS 282 Lecture 7 19Some Alternatives•Do computations over Q, but make each polynomial MONIC, eg. p2= x6+5/3x4+...•(this does not gain much, if anything. recall that in general the leading coefficient will be a polynomial. Carrying around 1/(a3+b3) is bad news.•Do computations in a finite field (in which case there is no coefficient growth, but the answer may be bogus)Richard Fateman CS 282 Lecture 7 20Sample calculation mod 13 drops some coefficients!x8+x6-3x4-3x3-5x2+2x-5 3x6+5x4-4x2+4x-5 -2x4+3x2+4 6x-5 was 585x2 ... but 585|13 5x-2 0 ... bad result suggests 5x-2 is the gcd, but 5x-2 is not a factor of p1 or p2Richard Fateman CS 282 Lecture 7 21This modular approach is actually better than this...In reality, the choice of 13 is easily avoidable, and there are plenty of “lucky” primes which will tell us the GCD is 1e.g. prime 3571 gives, X8+x6-3x4-3x3-5x2+2x-5 3x6+5x4-4x2+4x-5 x4+714x2+1429 281x2-9x+589 or x2+826x+1095 x+1152 376647 or 1 if monic.Richard Fateman CS 282 Lecture 7 22Another Alternative: the subresultant PRS•Do computations where a (guaranteed) divisor not much smaller than the content can be removed at each stage (subresultant PRS)•In our example, the subresultant’s last 2 lines are 9326x-12300260708 (actually the subres PRS is usually better; our example was an abnormal remainder sequence)Richard Fateman CS 282 Lecture 7 23The newest thought: Heuristic GCD, the idea is to evaluate•In our example, •p1(1234567)=5396563761321934654715861185575219389243022352699•p2(1234567)=10622071959634010638660619508311948074•the integer GCD is 1•Can we conclude that if the GCD is h(x), that h(1234567)=1 ?Richard Fateman CS 282 Lecture 7 24The GCD papers, selected, online in /readings. Recent “reviews”•M. Monagan, A. Wittkopf: •On the design and implementation of Brown's Algorithm (GCD) over the integers and number fields. Proc. ISSAC 2000 p 225-233•http://portal.acm.org/citation.cfm?doid=345542.345639•or the class directory, monagan.pdf•P. Liao, R. Fateman:•Evaluation of the heuristic polynomial GCD Proc ISSAC 1995 p 240-247• http://doi.acm.org/10.1145/220346.220376•or this directory, liao.pdfRichard Fateman CS 282 Lecture 7 25The GCD