On 03/13/2007 10:06 PM, Martin Rubey wrote: > Somehow I overlooked that email. Sorry about the delay. > > Ralf Hemmecke <[EMAIL PROTECTED]> writes: > >> That is a *major* rewrite. Since if you compute a series coefficient of >> degree n all coefficients for smaller degree are currently computed. If you >> don't like this then internally I would have to store whether a coefficient >> has already been computed. > > I'm afraid, it's exactly what should be done. Namely, in another mail you > wrote > that you currently store the CIS as > >> Stream(List(Integer,PowerProduct)) >> >> (because this is basically what I have now, only that I call >> >> List(Integer,PowerProduct) = Polynomial(x1,...xn,...) > > At first I thought one could simply "interpret" this datastructure > differently: > if a coefficient is absent in the list, it has not yet been computed. If it > has > been computed, it gets added to the list, possibly with zero > coefficient. However, doing so one never knows when all coefficients of a > certain degree have been computed, so a flag would be necessary here anyway, I > guess. Unless one checks that all possible monomials are there, but that > doesn't feel like the right thing to do...
Aaahh, you also see the problem. Today I thought a few minutes about it... Fixing the datastructure is probably rather easy. For example instead of Stream(P) where P contains the homogeneous CIS polynomial of degree n one could use Stream(A) where A would be something like Record(p: P, complete?: Boolean, z: P) with the following meaning: any cycletype (encoded as a power product x^j) that has been computed and has a nonzero coefficient is added to p. Those with a zero coefficient are remembered in z (actually it would be enough if z is a list of power products). If "complete?" is false then it is not known whether p contains all the non-zero terms of degree n. So if one asks for a term and it is not in p or q then one has to start to compute that coefficient. If "complete?" is true, then p contains all non-zero terms just as we have it now and z becomes irrelevant. However, it looks a bit difficult to ensure that *all* cycletypes of degree n have been considered. So it would probably be better to have Record(p: P, r: P) where at creation time r contains a list of *all* cycle types and an element is removed from r if its coefficient has been computed. If the coefficient is non-zero, the term is added to p, if it is zero, the cycletype is thrown away. Hmmm, I have no idea whether this makes sense. And I have not thought about, how difficult all the operations +, *, integrate(?), exponentiate, etc. become with that data structure. Additionally, assume I ask for the polynomial of degree n and in the data structure p already has some terms but r is not zero (or not the empty list), then what is the fastest way to compute the correct p? Should I start computation for each of the elements in r or would it be wiser to throw away p and r and compute p in a similar fashion as is done now, ie always consider the polynomial of degree n as *one* thing? Ralf ------------------------------------------------------------------------- Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV _______________________________________________ Aldor-combinat-devel mailing list Aldor-combinat-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/aldor-combinat-devel
