RFC: extracting coefficients of a multivariate polynomial

hmm, I didn't get the same timing results, maybe because I set
ratvars:[x,y,z] first ....
 
%o40)                                             [x, y, z]
(%i41) ex:rat((x+y+z)^200)$
Evaluation took 00.90 seconds (00.90 elapsed)
(%i42) thru 10 do ratcoef(ex,x,100)$
Evaluation took 7.34 seconds (7.34 elapsed)
(%i43) thru 10 do ratcoef(ex,z,100)$
Evaluation took 00.90 seconds (00.90 elapsed)
 
 
 


  _____  

From: macrakis at gmail.com [mailto:macrakis at gmail.com] On Behalf Of Stavros
Macrakis
Sent: Friday, April 25, 2008 7:32 AM
To: fateman at EECS.Berkeley.EDU; andre maute
Cc: maxima at math.utexas.edu
Subject: Re: [Maxima] RFC: extracting coefficients of a multivariate
polynomial


First of all, it is hard to know where the time is going without knowing
what your actual inputs are and what the 'driver' function is (the function
that calls my_coeff N times).  "thru 1000 do mycoef(rat(ex))" will perform
very differently from "(rex: rat(ex), thru 1000 do mycoef(rex))" if ex is
not already in rat form.

Secondly, be aware that coeff and ratcoeff have quite different semantics.
coeff looks for a top-level syntactic coefficient while ratcoeff looks
(effectively) for the coefficient in the full polynomial expansion:

     coeff((x+1)*(x-1),x,2) => 0
     ratcoeff((x+1)*(x-1),x,2) => 1

not to mention cases you probably don't care about...


     coeff((x+1)*(x-1),(x-1),1)  =>  x + 1
     ratcoeff((x+1)*(x-1),(x-1),1) =>  2    because (x-1)*(x+1) == (x-1)^2 +
2*(x-1)

Third, ratcoeff is not as efficient as I'd expect it to be when selecting
top-level terms:

ex:rat((x+y+z)^200,z,y,x)$  showtime:all$
thru 10 do ratcoef(ex,x,100)$  Evaluation took 4.85 seconds (4.85 elapsed)
thru 10 do ratcoef(ex,y,100)$  Evaluation took 6.34 seconds (6.34 elapsed)
thru 10 do ratcoef(ex,z,100)$  Evaluation took 4.76 seconds (4.76 elapsed)


I would have expected the "x" case to be far faster than the other cases --
it should be just picking out the x^100 term.

I am also surprised that some simple cases run out of memory:
   ex:ratcoef((x+y+z)^1000,z,y,x)$
   ratcoef(ex,x,500) => storage for cons exhausted
This term should be far smaller than the expression as a whole, and I'd
think it would for that matter share all its list structure with it.

RJF?

          -s