Hi again
well, not that I understand *how*, but that code works *magnificently*! I
see (confusingly for me I am afraid :) ) that the concept of "reserved
words" does not have much currency in SAGE ... !
The only difficulty with using that code is that for the sets I am looking
at, the number of bases in the tree grows horribly quickly with p,d etc and
so I still will need a routine which "checks as I go along", rather than
one which stores everything first and then searches. I tried and failed to
write a forest thing for that, then wrote a dumb nested loop thing which
takes as a starting point your tree of nodes, and verified that in "small"
cases I do indeed get the right results overall. But it is *horrendously *slow,
presumably because of the memory requirements for storing large-ish sets of
bases.
So somehow I need to understand how to incorporate the XRY condition (ie X
and Y as sets of vectors are pairwise related by the R condition - ie xRy
for all x in X and for all y in Y) as I crawl along the tree - then we stop
if we find M examples (ie a node with level M). Presumably knowing "not M"
will be pseudo-equivalent to the Halting Problem, sort-of, so I am not
concerned about that!
Jason I have sent you a separate email regarding the points you made in
your last post - I just need a spot of guidance there - but briefly the xRy
condition is as follows: my original search space consists (essentially
entirely with some boring caveats) of the subSET of vectors of F^N whose
"norm" (ie dot product with itself) is 1 and all of whose entries come from
a fixed (finite!) subset S_d = S(d,F) of the underlying field F, which in
particular does not contain 0 or 1.
Observe by the way that d<=N by definition (I hadn't thought of relaxing
the norm<>0 condition and taking sets with d>N as you did - perhaps some
new research lies there!!). Then xRy iff x.y \in S_d, where x.y can for now
be taken to be the dot product. Also if v \in X and v \in Y then XRY CANNOT
HOLD (since v.v=1 and 1 is not in S_d). So any bases which have a vector in
common do not need to be tested; similarly any pairs of bases containing
one from each which are orthogonal to one another can be discarded (ie v
\in X, w \in Y and v.w=0 but 0 not in S_d so NOT XRY).
So one needs to check that the "Gram matrix" of each pair of bases {X,Y}
contains only entries from S_d; if so, then XRY. My "code" consists of
nothing more than setting up S_d and checking these conditions in a very
obvious way.
Thanks again for the marvellous help so far.
Best regards
Gary
On Sun, Mar 31, 2013 at 3:16 AM, Jason Grout <[email protected]>wrote:
> On 3/30/13 4:56 PM, Gary McConnell wrote:
>
>> OK so thinking about it, even though your code is beautifully compact
>> and elegant, I think I am going to have to revert a little to the
>> "outer-inner-loop" structure in order to achieve what I need. Namely,
>> instead of storing "used" vectors, I store "used" bases and search
>> through the remaining orthogonal sets exhaustively. Otherwise I cannot
>> get at the bases which may share a vector with another basis but have
>> different "xRy" properties. I am trying to program this now - please
>> feel free to tell me a better way!!
>>
>
> Not a problem. I was hoping my code was a good starting off point to
> rethinking the problem. I was playing with a way to just have a function
> that generated all possible orthogonal sets of d vectors each, and then you
> could test your relationship for all of them in all possible ways. Maybe
> that's the best thing.
>
> However, maybe at this point it would be good to ask on, say,
> sage-combinat mailing list. You have a very combinatorial problem here,
> and they have lots of tools for enumerating sets with various constraints.
> For example, looking at http://www.sagemath.org/doc/**
> reference/combinat/sage/**combinat/backtrack.html<http://www.sagemath.org/doc/reference/combinat/sage/combinat/backtrack.html>,
> you could use SearchForest to implement your "find all independent sets of
> size d" pretty easily. The roots would be the list of singletons, and the
> children of a list could be found by:
>
> * if the list has d elements in it, it has no children
> * if the list has less than k<d elements in it, then you return all lists
> of size k+1 where you basically append all vectors that are orthogonal to
> all the things in your list.
> * to make this efficient, you want to iterate through your vectors in some
> sort of order, and then only test and add vectors that are ordered past
> your last vector in your current list.
>
> For example:
>
> V=FiniteField(3)^4
> L = list(V)
> d=9
> def find_children(node):
> if len(node)==d:
> return []
> node_position = L.index(node[-1])
> if len(node)+len(L)-node_position < d:
> # not enough elements to finish off the list
> return []
> children = []
> # find the last element
> for v in L[L.index(node[-1])+1:]:
> if all(v*w==0 for w in node):
> children.append(node+[v])
> return children
>
> def post_process(node):
> # only output nodes with the right length
> if len(node)==d:
> return node
> else:
> return None
>
> s=SearchForest(roots=[[v] for v in L], children=find_children,
> post_process = post_process,
> category=FiniteEnumeratedSets(**))
>
> # mutually orthogonal sets of size 9
> A=list(s.depth_first_search_**iterator())
> print len(A)
> print A
>
> (see http://sagecell.sagemath.org/?**q=e2a9c6b7-bb0c-40e6-9081-**
> 3609aaa3227f<http://sagecell.sagemath.org/?q=e2a9c6b7-bb0c-40e6-9081-3609aaa3227f>
> )
>
> Anyway, s.depth_first_search_iterator(**) gives an iterator over all
> independent sets of size d. Now you can test for your relations between
> the independent sets. In fact, you could set up another SearchForest for
> that too :). The nice thing about SearchForest is that it takes care of
> all the pruning and other things for you. You can do breadth-first or
> depth-first searches in it, etc.
>
> Another way to think about your problem is: you have a graph with vertices
> = vectors in N1, where two vectors are connected if their dot product is
> nonzero. You're trying to find a list of M mutually exclusive independent
> sets of size d, where the independent sets must also satisfy some
> relationship relative to each other. Of course, you could also take the
> complement and look for cliques. The combinat people might have already
> implemented fast searching for independent sets, etc.
>
> Feel free to share your code with us; we might be able to give you further
> pointers. It'd also be fun to see where this research is headed (e.g., a
> link to a paper), if it's appropriate. It'd be cool to see another paper
> in the Sage library links: http://www.sagemath.org/**
> library-publications.html<http://www.sagemath.org/library-publications.html>
>
>
> Thanks,
>
> Jason
>
>
> --
> You received this message because you are subscribed to a topic in the
> Google Groups "sage-support" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/**
> topic/sage-support/**GFJdjFvKCvo/unsubscribe?hl=en<https://groups.google.com/d/topic/sage-support/GFJdjFvKCvo/unsubscribe?hl=en>
> .
> To unsubscribe from this group and all its topics, send an email to
> sage-support+unsubscribe@**googlegroups.com<sage-support%[email protected]>
> .
> To post to this group, send email to [email protected].
> Visit this group at
> http://groups.google.com/**group/sage-support?hl=en<http://groups.google.com/group/sage-support?hl=en>
> .
> For more options, visit
> https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/opt_out>
> .
>
>
>
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-support?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
