One other thought - if we do manage to get this search routine to work
"sequentially" (ie not necessarily to have to hold all things in memory at
the same time), then perhaps we can extend this philosophy right back to
the definition of "N_1" (my candidate vectors with norm 1 etc), because
once again for p>5 and d>3 and N>=d even the size of N_1 becomes so large
that Jason's algorithm also grinds to an effective halt in subsequently
trying to generate all of the orthogonal "bases" (they are bases obviously
iff d=N, but let me refer to them all as bases for simplicity), let alone
trying then to search through them ... I should mention that a simple rule
of thumb for the size of our search set of vectors N_1 is that it is of
order something like q^((N+1)/2) in low dimensions, where q is the size of
the underlying field.
So I need to *begin to construct* and test N_1, most fundamentally, and
while doing that "catch" each successive d-tuple of vectors forming a
basis, and store it in its own parallel tree, and then while doing *that* in
turn catch each successive 2-, 3-, 4- tuple of such bases {B,C,D,...}
satisfying B_R_C and B_R_D and ... and C_R_D and .... It is in these final
tuples of bases of possibly varying length that we are ultimately
interested; in my original posting I mentioned a "holy grail" number M =
M(q,d,N) which is the maximum size of the last type of tuple of bases - eg
it is a big deal (in some cases!) if we can find a set satisfying M=d+1.
But in essence the point I am trying to get across is that *I do not care
at all what N_1 looks like, nor do I care about the bases, **other than if
they constitute one of the growing sets of bases at the end of the "tree" -
ie we may discard all "dead-end" information as we go along*.
Would it perhaps help for me to post a simplified meta-code version of this
algorithm? The unnecessary details buried in the actual code are very
distracting ...
On Mon, Apr 1, 2013 at 10:42 AM, Gary McConnell
<garymako...@googlemail.com>wrote:
> 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
> <jason-s...@creativetrax.com>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%2bunsubscr...@googlegroups.com>
>> .
>> To post to this group, send email to sage-support@googlegroups.com.
>> 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 sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
