bursejan@gmail.com schrieb:   
   >   
   > I am using a Gröbner Bases algorithm to compute the   
   > GCD of two multi-variate polynomials.   
   > For two polynomials p,q just apply the algorithm   
   > to [p*t,q*(1-t)] where t is a fresh variable,   
   > you can then read of the LCM, and from this get   
   > the GCD. I am currently experimenting with a randpoly   
   > to generate test cases, and observed the Gröbner Bases   
   > algorithm I am using has extremly varying runtime,   
   > for polynomials of degree 3 it varies from a few millis   
   > to a few secs. I read already about this horrible   
   > complexity issue and in some cases heuristics might help.   
   > For example this co-prime case runs through the roof:   
   >   
   > ?- X is 5+(5+A^2)*B-A*B^2,   
   > Y is 5*A^2*B-(A+4*A^2)*B^2,   
   > time(Z is X/Y).   
   >   
   > % Up 5,878 ms, GC 442 ms, Thread Cpu 5,438 ms (Current 06/08/17 01:07:39)   
   >   
   > Z is (1+1/4+(1+1/4+1/4*A^2)*B-1/4*A*B^2)/((1+1/4)*A^2*B-(1/4*A+A^2)*B^2)   
   >   
   > Any test cases around, that also show the corners of   
   > the various heuristics that are around. Note: I am using   
   > a very simple lexical ordering for the moment, different   
   > orderings could of course also help.   
   >   
      
   Five seconds for the GCD or LCM of low-degree bivariate polynomials is   
   absolutely ridiculous.   
      
   Using its POLY_GCD procedure, Derive 6.10 instantaneously (a fraction of   
   a millisecond on a modern CPU) finds:   
      
     POLY_GCD(5 + (5 + a^2)+b - a*b^2, 5*a^2*b - (a + 4*a^2)*b^2)   
      = 1   
      
   and, using its GROEBNER_BASIS procedure, somewhat less instantaneously   
   (a few milliseconds on a modern CPU) finds:   
      
     FIRST(GROEBNER_BASIS([(5 + (5 + a^2) + b - a*b^2)*t,   
       (5*a^2*b - (a + 4*a^2)*b^2)*(1 - t)], [t]))   
      = a^4*(4*b^2 - 5*b) - a^3*(4*b^4 - 5*b^3 - b^2)   
        - a^2*(b^4 - 4*b^3 - 35*b^2 + 50*b) + a*(b^3 + 10*b^2)   
      
   the result equalling the negated product of the two polynomials:   
      
     - (5 + (5 + a^2) + b - a*b^2)*(5*a^2*b - (a + 4*a^2)*b^2).   
      
   Experiments with larger bivariate polynomials confirm that Derive's   
   POLY_GCD procedure can easily be orders of magnitude faster than the   
   equivalent LCM computation relying on its GROEBNER_BASIS procedure. No   
   wonder, actually, since the size of the unused basis elements can easily   
   exceed the size of the decisive first element by orders of magnitude.   
      
   Martin.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)