On 03/13/2007 11:24 PM, Martin Rubey wrote:
> 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
You probably meant to exchange drawback/advantage.
So let me suggest another representation, that consumes less memory, but
costs a bit more time. Instead of rest: P one could store
uncomputed: BitVector or uncomputed: Integer (which is equivalent)
which is for degree n of length P(n) (number of integer partitions of n).
In order to check whether a given cycle type (which is an integer
partition) is there one has to rank it and check the bit. If the bit
vector is zero, we are complete.
>> 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.
That is what we just discuss. Don't you see that the entry p:P can
always computed as before? Just ignore the bit vector and compute
everything as we have it now. BTW, I have introduced a macro P in
src/gseries.as.nw if that is redefined to some other "Pseudo-Polynomial"
domain that we discuss now, there would probably be no modification of
the current implementation. It then just works over another domain.
>> 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.
You give the example yourself. Unfortunately, I have no experience, but
I would rather guess, that the polynomials of degree n almost never
contain every P(n) power products. But that's a wild guess.
> 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.
You see the problem with the first thing term-wise approach is that I
have to loop over all cycle types even those that correspond to zero
coefficients.
BTW, do you really think we (which probably means just me) should invest
more time into making cycle index series from polynomial-wise to
term-wise? Wouldn't it make more sense to just create SimpleGraph as
macro {
CS == CombinatorialSpecies;
E == SetSpecies;
E2 == RestrictedSpecies(E, 2);
WP == Times(E, E);
P2 == Times(E2, E);
}
SimpleGraph(L: LabelType): CS L == FunctorialCompose(WP, P2)(L) add;
and override the generic CIS and isomorphismTypeSeries with more
efficient versions?
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
