Ralf Hemmecke <[EMAIL PROTECTED]> writes:
> Fixing the datastructure is probably rather easy.
I doubt it :-)
> Record(p: P, complete?: Boolean, zeros: P)
* advantage: no overhead at creation time
* drawbacks: it might be difficult to check whether everything is there. Well,
maybe not, since we could simply compute the number of partitions
and check whether the number is correct.
it might be difficult to see which terms are missing.
higher memory consumption - is that irrelevant?
> Record(p: P, rest: P)
* drawbacks: trivial to check whether everything is there
* advantage: some overhead at creation time
> And I have not thought about, how difficult all the operations +, *,
> integrate(?), exponentiate, etc. become with that data structure.
I hope that the design of the datastructure could be done in such a way that
computing all terms of total degree n is just as easy as it is now.
> 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?
Do you see an example where you really save time when you compute all monomials
at once - as you do it now?
One fact that might favor polynomial-oriented algorithms is that you do not
have to consider all monomials, rather, only those which are actually
there. This is important, for example, for species built only using Plus and
Times and Singletons, since in this case the CIS depends only on x_1.
For example multiplication:
[x^\sigma] Z_{f*g} = \sum_{\tau <= \sigma} [x^\tau] Z_f [x^{\sigma-\tau}] Z_g
vs currently (I believe ?)
Z_{f*g} = \sum_n \sum_k [x^n] Z_f * [x^{n-k}] Z_g
where
* n denotes total degree
* \sigma is a cycle type
* x^\sigma = x1^{\sigma_1} x2^{\sigma_2} ...
* [x^\sigma] Z_f denotes the coefficient in Z_f
* \tau <= \sigma is to be understood componentwise.
I'm too lazy to count operations right now. But I guess that it does make a
difference... For some reason, computing monomials we do not "see" as much of
the argument cycleindexfunctions Z_f and Z_g as if we were computing
polynomials.
Martin
-------------------------------------------------------------------------
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
