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: sage-7.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), 731-41.

In particular this gives (378,52,1,8)-srg.

Attachments (2)

cope.sage (1.8 KB) - added by dimpase 4 years ago.
preliminary implementation as a Sage function
copeopt.g (1.6 KB) - added by dimpase 4 years ago.
an efficient implementation as a GAP/GRAPE function

Download all attachments as: .zip

Change History (65)

Changed 4 years ago by dimpase

preliminary implementation as a Sage function

comment:1 Changed 4 years ago by dimpase

  • 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 follow-up: Changed 4 years ago by ncohen

minutes ? Reaally ? O_o

What's the explanation ? labels ? :-P

comment:3 in reply to: ↑ 2 Changed 4 years ago by dimpase

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 :-)

Last edited 4 years ago by dimpase (previous) (diff)

comment:4 Changed 4 years ago by ncohen

Oh. I thought you meant that is_strongly_regular was slower than expected.

comment:5 Changed 4 years ago by dimpase

  • Branch set to public/19661
  • Commit set to 011f43f66643d79395a94e26b7317b4c21023aac

the fly-by patch with moar refs etc


Last 10 new commits:

287f49eMerge branch 'develop' of trac.sagemath.org:sage into develop
32931b0Merge branch 'develop' of trac.sagemath.org:sage into develop
7a2872aMerge branch 'develop' of trac.sagemath.org:sage into develop
ecfc955Merge branch 'develop' of trac.sagemath.org:sage into develop
2b442c1Merge branch 'develop' of trac.sagemath.org:sage into develop
3c860d2Merge branch 'develop' of trac.sagemath.org:sage into develop
a5536bbMerge branch 'develop' of trac.sagemath.org:sage into develop
a1b0953Merge branch 'develop' of trac.sagemath.org:sage into develop
0c0e046Merge branch 'develop' of trac.sagemath.org:sage into develop
011f43fmore refs to Hu75 and BvL84 added, few docstrings improved

comment:6 Changed 4 years ago by dimpase

  • Milestone changed from sage-6.10 to sage-7.0

comment:7 Changed 4 years ago by ncohen

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/rewriting-history/git-rebase-i/

Nathann

comment:8 Changed 4 years ago by git

  • Commit changed from 011f43f66643d79395a94e26b7317b4c21023aac to 7f039845b6e4ef8e6703a7392950a8cd948046b6

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7f03984more refs to Hu75 and BvL84 added, few docstrings improved

comment:9 Changed 4 years ago by dimpase

one does not need -i here, no?

comment:10 Changed 4 years ago by ncohen

I always use the -i. It gives a lot of control (e.g. squash the commits, reorder them, change the commit messages)

Changed 4 years ago by dimpase

an efficient implementation as a GAP/GRAPE function

comment:11 Changed 4 years ago by git

  • Commit changed from 7f039845b6e4ef8e6703a7392950a8cd948046b6 to ea9cdab1a268c70b5f89006cfd9635b554637a18

Branch pushed to git repo; I updated commit sha1. New commits:

98a10bbMerge branch 'public/19661' of git://trac.sagemath.org/sage into 19661
ea9cdabimplemented Cossidente-Penttila, adjusted doctests of _check_database

comment:12 Changed 4 years ago by dimpase

  • Status changed from new to needs_review

ok, here we are, took a while...

comment:13 follow-up: Changed 4 years ago by ncohen

All the '\' are useless, because the opening parenthesis of function_factory.

Nathann

comment:14 in reply to: ↑ 13 Changed 4 years ago by dimpase

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 ncohen

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 follow-ups: Changed 4 years ago by dimpase

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 ncohen

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 ncohen

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 dimpase

It is correct that a part of GAP code computes elements e and nu of GF(q2) 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 C-like 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 follow-up: Changed 4 years ago by ncohen

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 dimpase

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 ncohen

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 follow-up: Changed 4 years ago by dimpase

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 ; follow-up: Changed 4 years ago by 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.

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

Last edited 4 years ago by ncohen (previous) (diff)

comment:25 in reply to: ↑ 24 ; follow-up: Changed 4 years ago by dimpase

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 C-source-file.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 ; follow-up: Changed 4 years ago by 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.

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 git

  • Commit changed from ea9cdab1a268c70b5f89006cfd9635b554637a18 to 16f1f711fce54ae770c81dd957e5cad2baea8fe1

Branch pushed to git repo; I updated commit sha1. New commits:

16f1f71renamed mu to nu and eps to e in the nameless GAP function

comment:28 in reply to: ↑ 26 ; follow-up: Changed 4 years ago by dimpase

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 ; follow-up: Changed 4 years ago by 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.

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 follow-up: Changed 4 years ago by 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 10-line 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...

Last edited 4 years ago by dimpase (previous) (diff)

comment:31 in reply to: ↑ 30 ; follow-up: Changed 4 years ago by 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 10-line 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 sage-devel 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 ; follow-up: Changed 4 years ago by dimpase

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 10-line 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 well-reported 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 ; follow-up: Changed 4 years ago by 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.

Nathann

Last edited 4 years ago by ncohen (previous) (diff)

comment:34 in reply to: ↑ 29 Changed 4 years ago by dimpase

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 dimpase

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.

Last edited 4 years ago by dimpase (previous) (diff)

comment:36 Changed 4 years ago by ncohen

sage-devel thread about the presence of GAP code: https://groups.google.com/forum/#!topic/sage-devel/JNeNYJhReE8

comment:37 Changed 4 years ago by git

  • Commit changed from 16f1f711fce54ae770c81dd957e5cad2baea8fe1 to 8acd99c169e139d18f0953c3ea00a714b37b32bb

Branch pushed to git repo; I updated commit sha1. New commits:

8acd99cmissing # optional added

comment:38 Changed 4 years ago by git

  • Commit changed from 8acd99c169e139d18f0953c3ea00a714b37b32bb to 16b8d7cd1973cf8f425c638a0a39d86448e2803d

Branch pushed to git repo; I updated commit sha1. New commits:

b736207trac #19777: Three new SRGs and db update
5aca3d8trac #19777: Convert the other 2-intersection set
6696d1eMerge branch 'develop' of git://trac.sagemath.org/sage into develop
16b8d7cmerging with 7.0.beta3

comment:39 Changed 4 years ago by ncohen

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 follow-up: Changed 4 years ago by dimpase

  • 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 git

  • Commit changed from f287e7ba534e30d7d842b48d1651421a56b8a5d6 to 7c0aac76d2b66a2d481773dae7e0e7b2177cd6be

Branch pushed to git repo; I updated commit sha1. New commits:

7c0aac7trac #19661: Some cleaning

comment:42 in reply to: ↑ 40 ; follow-up: Changed 4 years ago by 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 sage-devel. 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 ; follow-up: Changed 4 years ago by dimpase

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 sage-devel. 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 2-variable function that tells edges from non-edges, 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 memory-hungry).

(*) 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 ; follow-up: Changed 4 years ago by 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 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 2-variable function that tells edges from non-edges, 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 memory-hungry).

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 ncohen

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 ; follow-up: Changed 4 years ago by dimpase

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 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 2-variable function that tells edges from non-edges, 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(n2) calls to f, lambda or no lambda, GAP or Sage. There is no way around that O(n2) 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 memory-hungry).

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 brain-damaged, 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 ; follow-up: Changed 4 years ago by ncohen

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(n2) calls to f, lambda or no lambda, GAP or Sage. There is no way around that O(n2) 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 dimpase

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 follow-up: Changed 4 years ago by 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

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 dimpase

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 0-1 vectors of length n2, 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 ncohen

Okay... Well, if we can get it from Grape anyway...

comment:52 Changed 4 years ago by dimpase

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 follow-up: Changed 4 years ago by 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? :-/

Nathann

comment:54 in reply to: ↑ 53 Changed 4 years ago by dimpase

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 jdemeyer

Can this be replaced by a try/except instead?

+    if not is_package_installed('gap_packages'):
+        raise PackageNotFoundError('gap_packages')

comment:56 follow-up: Changed 4 years ago by 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.

Nathann

comment:57 in reply to: ↑ 56 ; follow-up: Changed 4 years ago by dimpase

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 ; follow-up: Changed 4 years ago by ncohen

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) 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.

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 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.

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 ; follow-up: Changed 4 years ago by dimpase

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 ncohen

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 ncohen

  • Authors set to Dima Pasechnik
  • Reviewers set to Nathann Cohen

comment:62 Changed 4 years ago by dimpase

  • Status changed from needs_review to positive_review

ok, ok...

comment:63 Changed 4 years ago by vbraun

  • Branch changed from public/19661b to 7c0aac76d2b66a2d481773dae7e0e7b2177cd6be
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.