RFC: extracting coefficients of a multivariate polynomial

On Friday 25 April 2008, Richard Fateman wrote:
> 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)

so there is no O(1) append to lists in maxima?
and the lists are not doubly ended?

> instead  of at the front at O(1), then
> reversing in O(n).  n =length(exps)

I'll look into this 

Andre


>
> 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
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima