On 03/13/2007 09:23 AM, Martin Rubey wrote:
> Dear Ralf,
>
> Ralf Hemmecke <[EMAIL PROTECTED]> writes:
>
>> I've found the problem with the seemingly slow functorial compose.
>> In the middle of the computation of functorialCompose(f,g), there is a
>> need to compute
>>
>> count(f, t)
>>
>> for t=x4^1*x8^3
>
> A little more information would have saved me half an hour :-)
>
> So, spelled out, with a smaller example:
>
>
> f= Subset, g= Combination(2), f\square g = Graph
>
> Z=Z_{f\square g}
>
> n=4
>
> We have to compute, for example, the coefficient of x1*x3 in Z. Thus
> sigma=(1,0,1). We first need to compute
>
> (g[sigma])_1, (g[sigma])_2, (g[sigma])_3.
>
> Computational effort for this increases reasonably as n gets larger: it
> involves coefficients in Z_g of degree at most n. In this case, the result
> turns out to be (0,0,2). Now, however, we have to compute
>
> f[(0,0,2)]
>
> which is slow, since the degree is not bounded by n anymore, but rather by ???
> (shouldn't be too difficult to get a bound here, but I'm lazy)
Of course f[(0,0,2)] = [x2^2] f just needs to compute the series of f up
to (weighted) degree 4.
Your example is not illutrative. Look at my documentation for
functorialCompose in AC. We had the discussion before and you came up
with a bound.
In general we have to computed the cycle type of G[sigma].
Suppose sigma \in S_n, then then length of the longest cycle in G[sigma]
is bounded by the minimum of
\card G[n]
and
lcm [k for k in 1..n | sigma_k > 0].
And as it happens for n=8 in the CIS of graphs, that minimum is
something like 28.
> I see one possible *major* speedup: although we need many (all?) coefficients
> of degree n of Z_g, we need only very few coefficients of Z_f, albeit of high
> degree. So, possibly it makes sense to compute only these coefficients, rather
> than the whole thing here.
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. Currently, I rely on the fact
that if the internal array has length n then all coefficients for 0..n-1
are stored.
> -- Idea 1
> ---------------------------------------------------------------------
> A possible approach to do that *might* also yield a brute force approach of
> generating isotypes. I'll give an example:
>
> To compute the coefficient of x3^2/aut(0,0,2) in Z_f, we generate a
> permutation
> of cycle type (0,0,2). Any permutation will do, so we take (1 2 3) (4 5 6).
> Now
> we have to find all f-structures on {1,2,3,4,5,6} that are fixed points under
> this permutation. In the present case (f = Subset), we obtain
>
> {}, {1 2 3}, {4 5 6}, {1 2 3 4 5 6}
>
> (More thinking is needed to see *how* to obtain these fixed points...)
>
> So the coefficient we were looking for equals 4.
You think the computation of number of fixed points is easier? I don't
see that.
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
