RFC: extracting coefficients of a multivariate polynomial

appending to the end of a list of N items requires COPYING N items.
There are many ways of dealing with randomly accessed data structures
including 'hash arrays'.
Or using lists in reverse, which can then be reversed rapidly.
There is a long history of alternatives to two-way lists which
require a bit more thought sometimes but typically are as fast
but use half the memory.
Experienced lisp programmers are familiar with such things.
Of course it is possible to program 2-way lists, if that somehow
turns out to be a good idea.  Not at all necessary in your program.
RJF

> -----Original Message-----
> From: maxima-bounces at math.utexas.edu 
> [mailto:maxima-bounces at math.utexas.edu] On Behalf Of andre maute
> Sent: Friday, April 25, 2008 12:51 AM
> To: maxima at math.utexas.edu
> Subject: Re: [Maxima]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
> 
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>