Opened 4 years ago
Closed 4 years ago
#19661 closed enhancement (fixed)
the srgs from Cossidente and Penttila construction of hemisystems in H(3,q^2)
Reported by:  dimpase  Owned by:  

Priority:  major  Milestone:  sage7.0 
Component:  graph theory  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  Dima Pasechnik  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  7c0aac7 (Commits)  Commit:  7c0aac76d2b66a2d481773dae7e0e7b2177cd6be 
Dependencies:  Stopgaps: 
Description
implement the construction from Cossidente and Penttila J.LMS (2) 72(2005), 73141.
In particular this gives (378,52,1,8)srg.
Attachments (2)
Change History (65)
Changed 4 years ago by
comment:1 Changed 4 years ago by
 Cc ncohen added
sage: cope(3).is_strongly_regular(parameters=True) (56, 10, 0, 2) sage: cope(5).is_strongly_regular(parameters=True) # few sec (378, 52, 1, 8) sage: cope(7).is_strongly_regular(parameters=True) # few minutes (1376, 150, 2, 18)
took a while to understand...
comment:2 followup: ↓ 3 Changed 4 years ago by
minutes ? Reaally ? O_o
What's the explanation ? labels ? :P
comment:3 in reply to: ↑ 2 Changed 4 years ago by
Replying to ncohen:
minutes ? Reaally ?
O_o
What's the explanation ? labels ?
:P
cause it takes IntersectionGraph
of relatively few sets on a much bigger set; e.g. for q=5 we work in the set of over 3000 elements (lines of GQ(5,25)), and take 378 subsets, each of size 26, there.
Whether (or rather, how) this can be made more efficient is a good maths research question :)
comment:4 Changed 4 years ago by
Oh. I thought you meant that is_strongly_regular
was slower than expected.
comment:5 Changed 4 years ago by
 Branch set to public/19661
 Commit set to 011f43f66643d79395a94e26b7317b4c21023aac
the flyby patch with moar refs etc
Last 10 new commits:
287f49e  Merge branch 'develop' of trac.sagemath.org:sage into develop

32931b0  Merge branch 'develop' of trac.sagemath.org:sage into develop

7a2872a  Merge branch 'develop' of trac.sagemath.org:sage into develop

ecfc955  Merge branch 'develop' of trac.sagemath.org:sage into develop

2b442c1  Merge branch 'develop' of trac.sagemath.org:sage into develop

3c860d2  Merge branch 'develop' of trac.sagemath.org:sage into develop

a5536bb  Merge branch 'develop' of trac.sagemath.org:sage into develop

a1b0953  Merge branch 'develop' of trac.sagemath.org:sage into develop

0c0e046  Merge branch 'develop' of trac.sagemath.org:sage into develop

011f43f  more refs to Hu75 and BvL84 added, few docstrings improved

comment:6 Changed 4 years ago by
 Milestone changed from sage6.10 to sage7.0
comment:7 Changed 4 years ago by
Dima, your branch contains 18 useless commits, and one useful one. It is time for you to learn the use of "git rebase".
https://www.atlassian.com/git/tutorials/rewritinghistory/gitrebasei/
Nathann
comment:8 Changed 4 years ago by
 Commit changed from 011f43f66643d79395a94e26b7317b4c21023aac to 7f039845b6e4ef8e6703a7392950a8cd948046b6
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
7f03984  more refs to Hu75 and BvL84 added, few docstrings improved

comment:9 Changed 4 years ago by
one does not need i here, no?
comment:10 Changed 4 years ago by
I always use the i. It gives a lot of control (e.g. squash the commits, reorder them, change the commit messages)
comment:11 Changed 4 years ago by
 Commit changed from 7f039845b6e4ef8e6703a7392950a8cd948046b6 to ea9cdab1a268c70b5f89006cfd9635b554637a18
comment:12 Changed 4 years ago by
 Status changed from new to needs_review
ok, here we are, took a while...
comment:13 followup: ↓ 14 Changed 4 years ago by
All the '\' are useless, because the opening parenthesis of function_factory
.
Nathann
comment:14 in reply to: ↑ 13 Changed 4 years ago by
Replying to ncohen:
All the '\' are useless, because the opening parenthesis of
function_factory
.
well, it's a one long string!
comment:15 Changed 4 years ago by
Arggggg... It's all GAP code? O_o
Can't you write that in Sage commands only?... Either way the \ should still be useless somehow.
Nathann
comment:16 followups: ↓ 17 ↓ 18 Changed 4 years ago by
In Sage the code will be less readable, longer, and littered with libgap.
Or just too slow.
The main reason is absence of a Sage graph backend that takes symmetries into account.
comment:17 in reply to: ↑ 16 Changed 4 years ago by
In Sage the code will be less readable, longer, and littered with
libgap.
Or just too slow.
Perhaps you could make it easier to write by adding some individual functions to Sage?
Nathann
comment:18 in reply to: ↑ 16 Changed 4 years ago by
The main reason is absence of a Sage graph backend that takes symmetries into account.
P.S. Only the last three lines of your graph code seems to involve graphs. Everything else seems to be group theory and linear algebra.
comment:19 Changed 4 years ago by
It is correct that a part of GAP code computes elements e and nu of GF(q^{2}) described in the docstring. One can do this in Sage with Sage finite fields, but converting the results to GAP finite fields is painful and error prone (and slow). (Or one can use libgap to do these computations with GAP objects using Sage syntax  but then letting these objects be known to GAP's libgap to be used in function_factory
call is a painful hack, as far as I can see).
Anyway, it's done, it works very fast, and I don't see why this needs to be changed. GAP language is very easy, too, as easy as Python, if not easier.
One major shortcoming of function_factory
is that it does not allow comments in GAP string, as it's just one line of GAP code, and GAP does not have Clike comments, i.e. a=1; /* blah */ b=2;
is not possible. I can add more comments if needed (out of the code body).
PS. last but not least I ideally should take at least few days away from keyboard/mouse, as I seem to have a case of "mouse elbow", a.k.a. RSI...
comment:20 followup: ↓ 21 Changed 4 years ago by
Man, most of your code is a *string* that you give to another software. Ask anyone > it's dirty.
Nathann
comment:21 in reply to: ↑ 20 Changed 4 years ago by
Replying to ncohen:
Man, most of your code is a *string* that you give to another software. Ask anyone > it's dirty.
It is just a GAP function. It is a clean functional programming solution, if you ask me. One can store it in a separate file, and load/run in a GAP session, except that we don't seem to have infrastructure to support such foreign language files.
If it was C/C++, not GAP, you won't be having this questions, right?
comment:22 Changed 4 years ago by
Sorry, I barely understand the mathematical code as it is, I don't plan to review it when I don't even agree with the implementation.
We would of course have the same conversation if you were compiling C/C++ code from a Python string.
Nathann
comment:23 followup: ↓ 24 Changed 4 years ago by
It is unclear to me what particular part of implementation you don't agree with.
Do you think that function_factory
facilities (apart from GAP, there are these for Singular, for Maxima, probably even more) must not be used? Or something else?
You also have not said a word about the unclear to you mathematical parts.
comment:24 in reply to: ↑ 23 ; followup: ↓ 25 Changed 4 years ago by
It is unclear to me what particular part of implementation you don't agree with.
I don't agree with your defining a rather long gap script as a *string* and executing it. It seems that it can be avoided.
You also have not said a word about the unclear to you mathematical parts.
The mathematics are unclear to me, but I was just looking at the GAP code (and getting scared). I have not spent enough time over your documentation to make the sligthest remark over it yet.
Nathann
comment:25 in reply to: ↑ 24 ; followup: ↓ 26 Changed 4 years ago by
Replying to ncohen:
It is unclear to me what particular part of implementation you don't agree with.
I don't agree with your defining a rather long gap script as a *string* and executing it. It seems that it can be avoided.
It is not a GAP script, it is a GAP function. If you know other ways to define a new GAP function within Sage library code, pray tell me how to do it. Apart from it, I only know eval
functions (libgap/gap), which are much uglier.
I hope you don't want me to replace what I have with a sequence of libgap.eval...
.
(Hint: libgap.function_factory
was created for a reason...)
There ways for doing this with C/C++ (in Cython files you can do something like `cdef extern from Csourcefile.c"), but it's because they have to be compiled. Whereas GAP functions are interpreted.
If you really want I can move computations of e and nu over to Python.
comment:26 in reply to: ↑ 25 ; followup: ↓ 28 Changed 4 years ago by
I hope you don't want me to replace what I have with a sequence of
libgap.eval...
.
Ideally, you should only call Sage/libgap function and give them Sage/gap objects as parameters. Not strings.
(Hint:
libgap.function_factory
was created for a reason...)
Consequently you must use it right now, in this patch, for whatever you want to do with it? Fuzzy logic.
What I mean is that there are apparently some mathematical computations tht you do not know how to perform with Sage only. If there is no way to do it in Sage directly, do you think there could be a way to add those features to Sage (calling gap in the background)?
If you really want I can move computations of e and nu over to Python.
e and nu are no variables of your gap script, so I do not understand.
Nathann
comment:27 Changed 4 years ago by
 Commit changed from ea9cdab1a268c70b5f89006cfd9635b554637a18 to 16f1f711fce54ae770c81dd957e5cad2baea8fe1
Branch pushed to git repo; I updated commit sha1. New commits:
16f1f71  renamed mu to nu and eps to e in the nameless GAP function

comment:28 in reply to: ↑ 26 ; followup: ↓ 29 Changed 4 years ago by
Replying to ncohen:
I hope you don't want me to replace what I have with a sequence of
libgap.eval...
.Ideally, you should only call Sage/libgap function and give them Sage/gap objects as parameters. Not strings.
(Hint:
libgap.function_factory
was created for a reason...)Consequently you must use it right now, in this patch, for whatever you want to do with it? Fuzzy logic.
Nothing fuzzy  it's the right tool for the job. You don't know a better one, right? In fact many functions in this file would've become much cleaner, had I known about it then...
What I mean is that there are apparently some mathematical computations tht you do not know how to perform with Sage only.
yes, I do know how to do them in Sage, in C, or on a Turing machine if I must... But it's suboptimal, for reasons of efficiency, and of the code length.
If there is no way to do it in Sage directly, do you think there could be a way to add those features to Sage (calling gap in the background)?
Well, every time I talk to you guys about a graph backend that can do things with symmetric graphs as good as GRAPE does it in Sage, I don't hear cheers and screams "yes, let's do it!" I rather hear "hmm, how do we remove an edge then" or something equally compelling...
I still think it would be great for this (SRGs) project to have such a backend. But not on this ticket...
If you really want I can move computations of e and nu over to Python.
e and nu are no variables of your gap script, so I do not understand.
oops, sorry, mea maxima culpa. Fixed in the last commit.
comment:29 in reply to: ↑ 28 ; followup: ↓ 34 Changed 4 years ago by
Okay, before anything let's be clear: I won't give a review to this patch if it injects 10 lines of GAP code. Perhaps you will find somebody who will, but I will not. Now let us discuss.
Nothing fuzzy  it's the right tool for the job. You don't know a better one, right? In fact many functions in this file would've become much cleaner, had I known about it then...
It may be a necessary tool for libgap, and I quite agree that this function is necessary. I claim that it is not necessary here, and in particular that the mathematical features you need from gap should not be called *directly* from gap, and that we should instead expose in the Sage mathematical objects those features from GAP that you need.
This code could then be Sage/Python? code that calls other Sage/Python? functions. Those other functions may have reasons to rely on this function_factory
function, or they may not. I have absolutely no idea a priori, and neither do I have any objection to that a priori.
What I mean is that there are apparently some mathematical computations tht you do not know how to perform with Sage only.
yes, I do know how to do them in Sage, in C, or on a Turing machine if I must... But it's suboptimal, for reasons of efficiency, and of the code length.
We try to build a software that can handle all kind of maths. If you must inject GAP code to get it to do what you want, then it means that we should expose some feature somewhere. At least that's how I interpret it.
Well, every time I talk to you guys about a graph backend that can do things with symmetric graphs as good as GRAPE does it in Sage, I don't hear cheers and screams "yes, let's do it!" I rather hear "hmm, how do we remove an edge then" or something equally compelling...
I don't feel guilty of not writing your code for you.
On the other hand, I have to admit that I still do not know what you exactly want this backend to be. So no, I don't feel terribly overjoyed when you answer my "you code is ugly" remarks with "it's because we don't have a backend for symmetric graphs".
Which, again, would not simplify in any way your need for GAP code injection.
Nathann
comment:30 followup: ↓ 31 Changed 4 years ago by
Come on, why do you think that 10 lines of libgap.blah(libgap.foo...)
, e.g. in _polar_graph()
in the same file are better than an honest 10line GAP function? Is the following a beacon of beauty in your eyes:
W=libgap.FullRowSpace(libgap.GF(q), m) # F_q^m B=libgap.Elements(libgap.Basis(W)) # the standard basis of W V = libgap.Orbit(g,B[0],libgap.OnLines) # orbit on isotropic points gp = libgap.Action(g,V,libgap.OnLines) # make a permutation group s = libgap.Subspace(W,[B[i] for i in range(m//2)]) # a totally isotropic subspace # and the points there sp = [libgap.Elements(libgap.Basis(x))[0] for x in libgap.Elements(s.Subspaces(1))] h = libgap.Set(map(lambda x: libgap.Position(V, x), sp)) # indices of the points in s L = libgap.Orbit(gp, h, libgap.OnSets) # orbit on these subspaces
Is it contrary to your religion, or something? I just don't get it, sorry. This piece above is a good example of a GAP function getting lost while in search of function_factory
...
comment:31 in reply to: ↑ 30 ; followup: ↓ 32 Changed 4 years ago by
Replying to dimpase:
Come on, why do you think that 10 lines of
libgap.blah(libgap.foo...)
, e.g. in_polar_graph()
in the same file are better than an honest 10line GAP function?
If you make a syntax error somewhere you see it when the module is loaded, not when the file is run. The error is a Python error. On the other hand, if you wait till the code is loaded, you may get a GAP error. Or may not if the error is not well reported. Syntax highlight too, which you cannot have if you feed a string. Plus you can debug with Python commands.
Is the following a beacon of beauty in your eyes:
I find it much better than the big string. And worse than being able to work directly on Sage objects.
Is it contrary to your religion, or something? I just don't get it, sorry.
I answered above. You can write to sagedevel if you need other people's advice, too.
This piece above is a good example of a GAP function getting lost while in search of
function_factory
...
Ideally, the mathematical features should be exposed in Sage objects.
Nathann
comment:32 in reply to: ↑ 31 ; followup: ↓ 33 Changed 4 years ago by
Replying to ncohen:
Replying to dimpase:
Come on, why do you think that 10 lines of
libgap.blah(libgap.foo...)
, e.g. in_polar_graph()
in the same file are better than an honest 10line GAP function?If you make a syntax error somewhere you see it when the module is loaded, not when the file is run. The error is a Python error. On the other hand, if you wait till the code is loaded, you may get a GAP error. Or may not if the error is not well reported. Syntax highlight too, which you cannot have if you feed a string. Plus you can debug with Python commands.
Python commands are pretty useless for debugging code like this, believe me. On the other hand,
GAP error reporting is pretty good. (Jeez, people, try GAP once, don't be lazy :)). Plus, you can debug a GAP function in GAP, as a GAP function, while debugging the above libgap...()....
Python (or `gap...()) code is a nightmare, cause GAP errors aren't wellreported then.
It is much quicker to write a GAP function, debug/test it in GAP, and feed it to function_factory
, than to write/debug libgap...()....
Python, and I do know what I am talking about.
Is the following a beacon of beauty in your eyes:
I find it much better than the big string. And worse than being able to work directly on Sage objects.
Has it ever crossed your mind that strings are Sage objects, too? Every piece of code is a string, you know...
By the way, I wrote that libgap
code, and it did cost me some grey hair, as opposed to the GAP
code you are objecting to on very unclear grounds.
comment:33 in reply to: ↑ 32 ; followup: ↓ 35 Changed 4 years ago by
I am convinced to have voiced my objections to the best of my abilities. I do not believe that there is anything I may add that I did not say already, which may make my point clearer.
On the other hand, I also object to the way the branch is written right now, and so I will not review it as it is. I will not object if anybody else reviews it, for I do not think it is contrary to any of the *written* rules we have in the manual.
Has it ever crossed your mind that strings are Sage objects, too? Every piece of code is a string, you know...
I take this sentence as a proof that you are making conscious efforts to pretend you do not understand what I am saying.
Nathann
comment:34 in reply to: ↑ 29 Changed 4 years ago by
Replying to ncohen:
Okay, before anything let's be clear: I won't give a review to this patch if it injects 10 lines of GAP code. Perhaps you will find somebody who will, but I will not. Now let us discuss.
Nothing fuzzy  it's the right tool for the job. You don't know a better one, right? In fact many functions in this file would've become much cleaner, had I known about it then...
It may be a necessary tool for libgap, and I quite agree that this function is necessary. I claim that it is not necessary here, and in particular that the mathematical features you need from gap should not be called *directly* from gap, and that we should instead expose in the Sage mathematical objects those features from GAP that you need.
No, we don't need to force objects to cross the still nontrivial Sage/GAP border unnecessarily. There is absolutely no reason for this piece of GAP code, that takes a number as an input, and returns a graph, to expose its finite fields and matrix groups guts to Sage, for this exposure does not benefit anything here, it only degrades the performance.
This code could then be Sage/Python code that calls other Sage/Python functions. Those other functions may have reasons to rely on this
function_factory
function, or they may not. I have absolutely no idea a priori, and neither do I have any objection to that a priori.
You might see that the code already calls a Sage/Python function, which relies on this function_factory
function. In that sense we are already here, and I don't see what you're trying to tell me here.
What I mean is that there are apparently some mathematical computations tht you do not know how to perform with Sage only.
yes, I do know how to do them in Sage, in C, or on a Turing machine if I must... But it's suboptimal, for reasons of efficiency, and of the code length.
We try to build a software that can handle all kind of maths. If you must inject GAP code to get it to do what you want, then it means that we should expose some feature somewhere. At least that's how I interpret it.
Well, every time I talk to you guys about a graph backend that can do things with symmetric graphs as good as GRAPE does it in Sage, I don't hear cheers and screams "yes, let's do it!" I rather hear "hmm, how do we remove an edge then" or something equally compelling...
I don't feel guilty of not writing your code for you.
On the other hand, I have to admit that I still do not know what you exactly want this backend to be. So no, I don't feel terribly overjoyed when you answer my "you code is ugly" remarks with "it's because we don't have a backend for symmetric graphs".
yes, we create graphs in GAP, and copy them into Sage, completely ignoring the underlying symmetries. Instead, we could be using GRAPE/GAP Graph as a backend. We could be handling sufficiently symmetric dense graphs on 10000 vertices with ease. E.g. with GAP/GRAPE it takes about 3 sec to create the graph on the ticket for q=13, it's 15386 vertices... (testing adjacency is still instant, by the way)
comment:35 in reply to: ↑ 33 Changed 4 years ago by
Replying to ncohen:
I am convinced to have voiced my objections to the best of my abilities. I do not believe that there is anything I may add that I did not say already, which may make my point clearer.
On the other hand, I also object to the way the branch is written right now, and so I will not review it as it is. I will not object if anybody else reviews it, for I do not think it is contrary to any of the *written* rules we have in the manual.
Has it ever crossed your mind that strings are Sage objects, too? Every piece of code is a string, you know...
I take this sentence as a proof that you are making conscious efforts to pretend you do not understand what I am saying.
No, I honestly do not understand what you are trying to say.
You seem to be saying that I should write some amazing and huge piece of code that would then make the code one would write on this ticket more acceptable for you.
You also seem to be saying that I can use function_factory
on one hand, but I cannot using it one the other hand.
You also seem to be saying that you fear and distrust GAP code (despite using GAP left and right in your work...).
None of this makes any sense to me.
comment:36 Changed 4 years ago by
sagedevel thread about the presence of GAP code: https://groups.google.com/forum/#!topic/sagedevel/JNeNYJhReE8
comment:37 Changed 4 years ago by
 Commit changed from 16f1f711fce54ae770c81dd957e5cad2baea8fe1 to 8acd99c169e139d18f0953c3ea00a714b37b32bb
Branch pushed to git repo; I updated commit sha1. New commits:
8acd99c  missing # optional added

comment:38 Changed 4 years ago by
 Commit changed from 8acd99c169e139d18f0953c3ea00a714b37b32bb to 16b8d7cd1973cf8f425c638a0a39d86448e2803d
comment:39 Changed 4 years ago by
At public/19661b I pushed a rebased branch without useles merge commits. By the way one of your commit messages says that you adjusted doctests of _check_database
, but I see no such thing.
comment:40 followup: ↓ 42 Changed 4 years ago by
 Branch changed from public/19661 to public/19661b
 Commit changed from 16b8d7cd1973cf8f425c638a0a39d86448e2803d to f287e7ba534e30d7d842b48d1651421a56b8a5d6
Thanks for rebasing; I should throw away my 'develop' branch, it seems. I've switched to the branch you provided. The adjusting of doctests of _check_database was also done in #19777, which is now part of beta3  that's why you don't see them anymore.
Should I proceed with Volker's suggestion to move GAP code to a file in SAGEROOT/src/ext/ ?
comment:41 Changed 4 years ago by
 Commit changed from f287e7ba534e30d7d842b48d1651421a56b8a5d6 to 7c0aac76d2b66a2d481773dae7e0e7b2177cd6be
Branch pushed to git repo; I updated commit sha1. New commits:
7c0aac7  trac #19661: Some cleaning

comment:42 in reply to: ↑ 40 ; followup: ↓ 43 Changed 4 years ago by
Should I proceed with Volker's suggestion to move GAP code to a file in SAGEROOT/src/ext/ ?
Don't know. It may be a clean solution from the point of view of a release manager who does not care what the code does for as long as it is technically 'clean', but really it would be cool to have it all in Constructor??
as you said on sagedevel. Really Dima, what is it that you can do in GAP and that you cannot do in Sage directly?..
Nathann
comment:43 in reply to: ↑ 42 ; followup: ↓ 44 Changed 4 years ago by
Replying to ncohen:
Should I proceed with Volker's suggestion to move GAP code to a file in SAGEROOT/src/ext/ ?
Don't know. It may be a clean solution from the point of view of a release manager who does not care what the code does for as long as it is technically 'clean', but really it would be cool to have it all in
Constructor??
as you said on sagedevel. Really Dima, what is it that you can do in GAP and that you cannot do in Sage directly?..
I certainly can convert the GAP code into something akin to what you see in comment 30 above (with libgap....
all over the place), but it would be uglier, at least from my point of view.
As to really "Sage proper", no, it would require much more work, basically taking an algorithm from GRAPE/GAP and reimplementing it. (why reimplementing, see (*) below).
As you see, GRAPE's Graph is very similar to Sage's construction of a graph given by a set V of vertices and a 2variable function that tells edges from nonedges, but doing this modulo a group G acting on V (and respecting the edges, of course). That is, you only need to check adjacency per orbital of G (i.e. an orbit of G on VxV), not per each pair of vertices. And once you know these, you can use the group to generate (or just to decide  GRAPE does not generate the graph edges) adjacency of the rest.
So by far the hardest part would be code to construct orbital representatives for a permutation group (G,V) in the right way (not in the naive way of just computing orbits of G on VxV and taking representatives of these, for this is too slow and memoryhungry).
(*) While it might be tempting to use GRAPE to do this job, it's not clear how to design a clean interface, as the function to be used by GRAPE to decide adjacency is a GAP function, and I don't know how to create GAP function that will call a Sage function (there are no callbacks implemented in (lib)GAP, that is).
comment:44 in reply to: ↑ 43 ; followup: ↓ 46 Changed 4 years ago by
I certainly can convert the GAP code into something akin to what you see in comment 30 above (with
libgap....
all over the place), but it would be uglier, at least from my point of view.
I admit that I would prefer that. Except that you could create aliases for the libgap stuff that you need often, i.e. Orbit = libgap.Orbit
? Too bad that it cannot be done with an import
:/
As you see, GRAPE's Graph is very similar to Sage's construction of a graph given by a set V of vertices and a 2variable function that tells edges from nonedges, but doing this modulo a group G acting on V (and respecting the edges, of course).
Okay, now I understand because I told you one thousand times to not use those ugly lambda functions everywhere in Sage code. That's because when you do this in GAP the same syntax is actually efficient, while in Python the function is stupidly evaluated n^2
times.
That is, you only need to check adjacency per orbital of G (i.e. an orbit of G on VxV), not per each pair of vertices. And once you know these, you can use the group to generate (or just to decide  GRAPE does not generate the graph edges) adjacency of the rest.
So by far the hardest part would be code to construct orbital representatives for a permutation group (G,V) in the right way (not in the naive way of just computing orbits of G on VxV and taking representatives of these, for this is too slow and memoryhungry).
Can't we ask GAP to give us a representative per orbit, assuming they have a smarter implementation?
Nathann
comment:45 Changed 4 years ago by
I'm not very proud of it, but...
Orbit,Elements,Set = map(libgap.__getattr__, ['Orbit','Elements','Set'])
:P
Nathann
comment:46 in reply to: ↑ 44 ; followup: ↓ 47 Changed 4 years ago by
Replying to ncohen:
I certainly can convert the GAP code into something akin to what you see in comment 30 above (with
libgap....
all over the place), but it would be uglier, at least from my point of view.I admit that I would prefer that. Except that you could create aliases for the libgap stuff that you need often, i.e.
Orbit = libgap.Orbit
? Too bad that it cannot be done with animport
:/
As you see, GRAPE's Graph is very similar to Sage's construction of a graph given by a set V of vertices and a 2variable function that tells edges from nonedges, but doing this modulo a group G acting on V (and respecting the edges, of course).
Okay, now I understand because I told you one thousand times to not use those ugly lambda functions everywhere in Sage code. That's because when you do this in GAP the same syntax is actually efficient, while in Python the function is stupidly evaluated
n^2
times.
If you have a set V and f:VxV>{T,F}, nothing else, then to create a graph from this data you still need O(n^{2}) calls to f, lambda or no lambda, GAP or Sage. There is no way around that O(n^{2}) calls, full stop. And this is why I never understood most of your objections to that lambdas.
That is, you only need to check adjacency per orbital of G (i.e. an orbit of G on VxV), not per each pair of vertices. And once you know these, you can use the group to generate (or just to decide  GRAPE does not generate the graph edges) adjacency of the rest.
So by far the hardest part would be code to construct orbital representatives for a permutation group (G,V) in the right way (not in the naive way of just computing orbits of G on VxV and taking representatives of these, for this is too slow and memoryhungry).
Can't we ask GAP to give us a representative per orbit, assuming they have a smarter implementation?
Talking about the code on this ticket,
yes, you can extract this information from GRAPE's Graph data structure. And? Why is this any better than letting GAP/GRAPE do the whole job of building the adjacencies? Mind you, this is one GAP call: List([1..OrderGraph(G)],x>Adjacency(G,x));
in the last line of the GAP function before end;
. Besides, in GAP I directly work with matrix groups, while in Sage these are a bit braindamaged, and this would mean I would need to do stuff like
W=libgap.FullRowSpace(libgap.GF(q), m) # F_q^m B=libgap.Elements(libgap.Basis(W)) # the standard basis of W
and express vectors I need as linear combinations of elements of B, and not in a natural way, just by coordinates.
comment:47 in reply to: ↑ 46 ; followup: ↓ 48 Changed 4 years ago by
If you have a set V and f:VxV>{T,F}, nothing else, then to create a graph from this data you still need O(n^{2}) calls to f, lambda or no lambda, GAP or Sage. There is no way around that O(n^{2}) calls, full stop. And this is why I never understood most of your objections to that lambdas.
Be sure that I only asked you to remove them in cases where it was an appalling waste of time.
I still remember something like Graph([V,lambda e:G1.has_edge(e) and G2.has_edge(e)])
.
Talking about the code on this ticket, yes, you can extract this information from GRAPE's Graph data structure.
I was trying to see how we could have a constructor of the form Graph([a_group,a_set,a_function])
that would use the symmetries to not call the function too often. If we can ask GAP to give us representants of the orbits of (u,v) under G, then we could only call our function on those pairs and compute the orbits of the actual edges.
And? Why is this any better than letting GAP/GRAPE do the whole job of building the adjacencies?
Because you cannot give GAP a Sage function. You can give the a_group
to GAP, or give it a_set
, but I do not think that you can give it a_function
. Thus having those representants would enable us to write this constructor in Sage, a bit better than it is possible now. If we can give everything to GAP and get the result back then, then it is probably better indeed.
Nathann
comment:48 in reply to: ↑ 47 Changed 4 years ago by
Replying to ncohen:
Talking about the code on this ticket, yes, you can extract this information from GRAPE's Graph data structure.
I was trying to see how we could have a constructor of the form
Graph([a_group,a_set,a_function])
that would use the symmetries to not call the function too often. If we can ask GAP to give us representants of the orbits of (u,v) under G, then we could only call our function on those pairs and compute the orbits of the actual edges.
Somewhat surprisingly, there is no separate functionality in GAP for this; the only place you get it is in GRAPE's Graph.
Perhaps there should be (actually, I just opened a GAP issue on this), but at the moment there is none. By the way, once I already extracted this functionality from GRAPE and put it in (still unfinished) GAP package, described here.
comment:49 followup: ↓ 50 Changed 4 years ago by
Arggggggggg... Hey Dima, don't we already have it here?
http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/integer_vectors_mod_permgroup.html
It is code from Nicolas Borie's thesis. He was quite proud of it.
Nathann
comment:50 in reply to: ↑ 49 Changed 4 years ago by
Replying to ncohen:
Arggggggggg... Hey Dima, don't we already have it here?
http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/integer_vectors_mod_permgroup.html
this is a much more general code, and it's not clear how well it will do for our task. Because to use it we first need to pass from G acting on V, V=n, to G acting on VxV and then, thinking of elements of VxV as 01 vectors of length n^{2}, call IntegerVectorsModPermutationGroup
, specifying sum=max_part=1
. I don't know the code, and if it does not work with sparse vectors then we can forget about it, it won't fly.
comment:51 Changed 4 years ago by
Okay... Well, if we can get it from Grape anyway...
comment:52 Changed 4 years ago by
I just found that with your """
trick to have a multiline input to function_factory
, one can also
add GAP code comments, it works this way. Should I add some?
comment:53 followup: ↓ 54 Changed 4 years ago by
Err.... Do you think that you may come to like the version in which you type only Sage code, where instead of using libgap.Orbit
you type 'Orbit = libgap.Orbit' at the beginning of the file so that the code is not too verbose? :/
Nathann
comment:54 in reply to: ↑ 53 Changed 4 years ago by
Replying to ncohen:
Err.... Do you think that you may come to like the version in which you type only Sage code, where instead of using
libgap.Orbit
you type 'Orbit = libgap.Orbit' at the beginning of the file so that the code is not too verbose?:/
As I already explained in comment 46, I'd also need to work around shortcomings of matrix groups and GAP vectors dealt with this way, and this is really ugly and fragile boilerplate. E.g. I'd need to do something like
W=libgap.FullRowSpace(libgap.GF(q^2), 3) B=libgap.Elements(libgap.Basis(W)) ... v=e*B[0]+B[1]+B[2] # (this order! B[0]=[0,0,0,..,1], B[1]=[0,0,..,0,1,0],...)
So the correctness of this actually relies on B being ordered in this particular way, and can be nuked by a major GAP release quite easily.
While in GAP it is just
... v:=Z(q)^0*[1,1,e];
comment:55 Changed 4 years ago by
Can this be replaced by a try
/except
instead?
+ if not is_package_installed('gap_packages'):
+ raise PackageNotFoundError('gap_packages')
comment:56 followup: ↓ 57 Changed 4 years ago by
Considering the function, I don't think that you will detect the difference in running time. It is probably possible, though probably a bit ugly as we would have to catch the exception raised by GAP and check that the error message is what we expect.
Nathann
comment:57 in reply to: ↑ 56 ; followup: ↓ 58 Changed 4 years ago by
Replying to ncohen:
Considering the function, I don't think that you will detect the difference in running time. It is probably possible, though probably a bit ugly as we would have to catch the exception raised by GAP and check that the error message is what we expect.
I don't actually know how to deal with creating an exception from a libgap function returning fail
. It can be converted to Sage's bool
just fine, and the previous version (in public/19661 branch) did bool(libgap.LoadPackage(...))
and raised an exception based on its result. I don't know the rationale behind this changed to using is_package_installed
.
As a matter of fact, I don't like it. I can install a GAP package directly into SAGE_LOCAL, and this would work with libgap.LoadPackage(...)
, but won't work with is_package_installed
.
The fact that GRAPE lives in gap_packages
at present is an unimportant detail, and might change; what's important is that the corresponding GAP functionality is available, and GAP surely knows better than Sage about it.
comment:58 in reply to: ↑ 57 ; followup: ↓ 59 Changed 4 years ago by
Yo,
I don't actually know how to deal with creating an exception from a libgap function returning
fail
.
If you start the GAP function without the package installed, I think you'll get an exception.
It can be converted to Sage's
bool
just fine, and the previous version (in public/19661 branch) didbool(libgap.LoadPackage(...))
and raised an exception based on its result. I don't know the rationale behind this changed to usingis_package_installed
.
Because that's how it is done everywhere else. I don't care much about the 'if', I just thought that it would make sense to say "install this package" right after having checked that the package was installed.
I can install a GAP package directly into SAGE_LOCAL, and this would work with
libgap.LoadPackage(...)
, but won't work withis_package_installed
. The fact that GRAPE lives ingap_packages
at present is an unimportant detail, and might change; what's important is that the corresponding GAP functionality is available, and GAP surely knows better than Sage about it.
I agree with whatever you just said, but in your original branch the error message was 'install gap_package', and that does not work at all with the case where the guy installed his own version of gap. Once you are set on which situations you want to deal with please change the exception to whatever you like.
The only thing is that if you want to advise the user to install 'gap_package', please do it with PackageNotFoundError
for it generates the appropriate message automatically.
Nathann
comment:59 in reply to: ↑ 58 ; followup: ↓ 60 Changed 4 years ago by
Replying to ncohen: [...]
I agree with whatever you just said, but in your original branch the error message was 'install gap_package', and that does not work at all with the case where the guy installed his own version of gap.
Well, I never said "own version of GAP". I said "own version of GRAPE". And
sage i gap_packages
would do the job just fine.
Once you are set on which situations you want to deal with please change the exception to whatever you like. The only thing is that if you want to advise the user to install 'gap_package', please do it with
PackageNotFoundError
for it generates the appropriate message automatically.
Sure. By the way, how about promoting the GAP function wrapped in function_factory
to a proper member of the module? It can then be doctested by itself, and it will be loaded only once, at import time.
comment:60 in reply to: ↑ 59 Changed 4 years ago by
Well, I never said "own version of GAP". I said "own version of GRAPE". And
sage i gap_packages
would do the job just fine.
Sigh. I can't say that I care enough to discuss the idea. Change the 'if' if it matters to you.
Sure. By the way, how about promoting the GAP function wrapped in
function_factory
to a proper member of the module? It can then be doctested by itself, and it will be loaded only once, at import time.
If you want to do that, then it is probably better to follow Volker's advice and create an individual gap file. Do that if you like, or keep it as it is and switch the ticket's status to 'positive_review'. And let us never mention this ticket again. Ever.
Nathann
comment:61 Changed 4 years ago by
 Reviewers set to Nathann Cohen
comment:63 Changed 4 years ago by
 Branch changed from public/19661b to 7c0aac76d2b66a2d481773dae7e0e7b2177cd6be
 Resolution set to fixed
 Status changed from positive_review to closed
preliminary implementation as a Sage function