RFC: extracting coefficients of a multivariate polynomial

The code displayed makes numerous accesses of lists by index, at cost of
O(n), when they should be done at O(1)
by first/rest.  It appends to the end of a list, taking time O(n^2) instead
of at the front at O(1), then
reversing in O(n).  n =length(exps)
 
It calls ratsimp pointlessly O(n)  times.

Maybe all this cost is submerged in something else that is much more
expensive.
RJF



> -----Original Message-----
> From: maxima-bounces at math.utexas.edu 
> [mailto:maxima-bounces at math.utexas.edu] On Behalf Of S. Newhouse
> Sent: Thursday, April 24, 2008 3:18 PM
> To: andre maute
> Cc: maxima at math.utexas.edu
> Subject: Re: [Maxima] RFC: extracting coefficients of a 
> multivariate polynomial
> 
> andre maute wrote:
> >> You're doing several substitutions, re-assignments, and 
> three loops. Did
> >> you try Fateman's code in his reply? I would bet that it will run
> >> faster. It does one nested loop and functions written in 
> lisp. Also, you
> >> could try the 'compile' option.
> >>     
> >
> > I never got the replies from Fateman with KMail under KDE.
> > Using the web interface of the mailinglist I saw them the 
> first time.
> >
> > the substs can easilly be removed, they are a leftover from 
> a maple migration.
> >
> > the timing for Fateman's
> > my_coeff5 : 14m10.050s
> >
> > the fastest is at the moment
> > my_coeff6: 13m49.501s
> >
> > I'm using maxima 5.13.0 with clisp 2.41
> >
> > -------------------------------------------------------
> > my_coeff6(v,exps,poly) := block(
> >
> >         [c,k,l,h],
> >
> >         c : [],
> >         for k : 1 thru length(exps) do block(
> >                 h : poly,
> >                 for l : 1 thru length(v) do block(
> >                         h : coeff(h,v[l],exps[k][l])
> >                 ),
> >                 h : ratsimp(h),
> >                 c : append(c,[h])
> >         ),
> >
> >         return(c)
> > )$
> > -------------------------------------------------------
> >
> > I expected a more sensational speedup.
> >
> >   
> >> Having written your program, try
> >> compile(all);
> >>     
> >
> > I'll try it.
> >
> >   
> >> Where are these polynomials coming from? Can you convert 
> them to rat form
> >> *once* instead of each time you call my_coeff?
> >>     
> >
> > Polynomials living on 3d solids.
> >
> > Products of different Jacobi Polynomials and Lagrange Polynomials,
> > with an additional nonlinear transformation.
> >
> > They are generated *once*, expanded *once*, then the 
> coefficients are computed
> > *once* and dumped *once* to a text file. ;-)
> >
> > I only wanted to minimize the maintainment hassle
> > for the Maxima part of my application.
> >
> > Nevertheless, thank you all
> >
> > Andre
> >
> >   
> >> and then execute it.
> >>
> >> HTH,
> >> -sen
> >>     
> >
> > _______________________________________________
> > Maxima mailing list
> > Maxima at math.utexas.edu
> > http://www.math.utexas.edu/mailman/listinfo/maxima
> > .
> >
> >   
> clisp is known to be slow. Try gcl, cmucl, and sbcl to see which is 
> better for your purposes.
> 
> -sen
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>