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)
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.
-- 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.
-- Idea 2 ---------------------------------------------------------------------
Similar to the current approach in AC of computing cycle index series via, it
might be possible to compute only certain coefficients of the cycle index
series.
But I do not have the time right now to see whether this is really doable...
> The second thing is that we run on -q1 -DDEBUG, so that is probably another
> factor that causes delay.
Yes, but almost certainly only a constant factor, not an exponential increase.
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
