Hi everyone
following on from the great help I got at
https://groups.google.com/forum/#!topic/sage-support/GFJdjFvKCvo and
https://groups.google.com/forum/#!topic/sage-combinat-devel/Oj40TFshcYA, I
have finally boiled the remaining sluggishness in my search problem down to
this. Note that my code is very quick for "small" cases (eg q<100, d<5 in
notation below) but horrendously slow, in fact pretty much stationary, for
larger q,d.
Fix F = GF(q) = a finite field of char p; d = an integer>=2; N integer >=d;
S = a subset of F of size q+1. My search "space" (it is a subset of the
vector space F^N but not a subspace) consists of the cartesian product N_1
= S^d x F^(N-d).
Let B be a set of size d consisting of vectors/tuples in N_1 which are
"orthonormal" in the sense that for v,w in B: v.v=w.w=1 and v.w=0 for v!=w;
where the "." denotes the dot product of vectors.
Given such a set B, I want to find similar "orthonormal" sets C, D etc
which are again subsets of N_1 and which further satisfy:
*(*) for any b in B and any c in C and any d in D etc etc:
**b.c and b.d and c.d and ... all lie in S.*
Note that S does not contain 0 or 1 so in particular all of these sets
B,C,D,... are pairwise disjoint and none of the vectors are isotropic.
Ultimately the aim is to find the cardinality of the largest such
collection {B,C,D,...} - we do not need to store any other information
along the way.
Naive searching in low dimensions/characteristics is very fast,
particularly when randomized: but my search machine grinds to a halt
whenever |N_1|.d exceeds around 1 million, since it has to store the entire
space N_1 in memory. I know this is not surprising - only I cannot think of
a better way of achieving the sifting process I need. I am relying heavily
on the inbuilt python functions like all() and any() etc.
Imagine that N_1 is a dark dormant forest whose trees are my vectors. I can
randomize the position of the trees; then what I do is to shine a spotlight
on a patch of the forest and see whether a suitable initial set B is in
there; then I cut out all of the trees which do not satisfy (*) with
respect to B, and then re-shine the spotlight and see whether my next set C
can be taken from there, and so on. This is effectively what my current
algorithm does.
*So my question is: is there a way in which I can achieve this same
algorithm without having to instantiate the vectors in N_1 initially in
memory?*
That is, as in the title to this post, is there a way of only making the
set of vectors picked out by my spotlight exist in memory once my spotlight
is shined upon them, with the remaining part of the forest remaining
somehow dark and not in memory?
I should mention that I have tried the obvious thing of not storing N_1 and
just creating small patches of random trees, and it is hopeless. In other
words, relying on Python's randoms and all() any() etc functions seems to
be infinitely better than trying to do them myself in some way.
But I am wondering whether the combinatorial algorithms you guys have
written might do this in some way I don't yet understand? I tried some
(naive) backtracking stuff but I was unable to do it in any way which
didn't require an equivalent amount of up-front or along-the-way storage ...
Thanks a lot for your ongoing help.
Gary.
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
