regular symmetric Hadamard matrices for n=324

[dimpase]

Implements the construction from

Z.Janko, H.Kharaghani, V.D.Tonchev, The existence of a Bush-type Hadamard matrix of order 324
and two new infinite classes of symmetric designs. Des. Codes Cryptogr. 24(2001), 225-232

and use its RSHCD of '+' type to build an srg on v=324, k=153. Also, use it to construct an RSHCD of '-' type and build an srg on v=324, k=152.

Depends on #19861

CC: @nathanncohen

Component: graph theory

Author: Dima Pasechnik

Branch: 567608b

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/19872

[sagetrac-git]

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

afcb53c

RSHCD with n=324, of + type AND of - type, and the graphs

[sagetrac-git]

Changed commit from 988214e to afcb53c

[nathanncohen]

Dependencies: #19861

[nathanncohen]

comment:2

(I guess you intended this dependency as your branch contains a commit from this other ticket)

[nathanncohen]

comment:3

Should this ticket be in needs_review?

What would you think of moving your code to a new function? I understand that it seems a bit silly considering that the code is 10 lines long, but that would give you a proper place to add your doc. As it is, it feels a bit weird to have a lengthy explanation of how this specific RSHCD is built when there is none for the others.

Nathann

[dimpase]

comment:5

Replying to @nathanncohen:

Should this ticket be in needs_review?

What would you think of moving your code to a new function? I understand that it seems a bit silly considering that the code is 10 lines long, but that would give you a proper place to add your doc. As it is, it feels a bit weird to have a lengthy explanation of how this specific RSHCD is built when there is none for the others.

as you please. We will also write a bit about it in our preprint.
It's a nice addition...

[sagetrac-git]

Changed commit from afcb53c to a42d6ac

[sagetrac-git]

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

a42d6ac

moved v=324 to a separate function, deleted some extra spaces

[dimpase]

comment:7

done.
tnx to First Great Western trains for free wifi :-)

[sagetrac-git]

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

d63a13b

moved v=324 to a separate function, deleted some extra spaces

[sagetrac-git]

Changed commit from a42d6ac to d63a13b

[sagetrac-git]

Changed commit from d63a13b to e123de4

[sagetrac-git]

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

659a07f	trac #19872: Merged with 7.0.rc1
e123de4	trac #19872: Review

[nathanncohen]

comment:10

I went over your branch and I agree with it. I added a small commit with a fix for a broken link and a couple of unimportant things. If you agree with it, you can change the ticket's status. Thanks for those graphs !!!

Nathann

[nathanncohen]

Reviewer: Nathann Cohen

[dimpase]

comment:11

I'm working on speeding it up. Already using libgap gives a 3-fold speedup...

diff --git a/src/sage/graphs/generators/smallgraphs.py b/src/sage/graphs/generators/smallgraphs
index 8ea232d..840c346 100644
--- a/src/sage/graphs/generators/smallgraphs.py
+++ b/src/sage/graphs/generators/smallgraphs.py
@@ -4941,7 +4941,7 @@ def JankoKharaghaniTonchevGraph():
 
     EXAMPLES::
 
-        sage: Gamma=graphs.JankoKharaghaniTonchevGraph()  # long time
+        sage: Gamma=graphs.JankoKharaghaniTonchevGraph()  # long time (14 sec)
         sage: Gamma.is_strongly_regular(parameters=True)  # long time
         (324, 153, 72, 72)
 
@@ -4956,7 +4956,7 @@ def JankoKharaghaniTonchevGraph():
     from itertools import product
     from sage.misc.misc_c import prod
     from sage.combinat.permutation import Permutation as P
-    from sage.groups.perm_gps.permgroup import PermutationGroup
+    from sage.libs.gap.libgap import libgap
 
     m1=prod([P((9*x+k,9*x+k+3,9*x+k+6)) for k,x in product(xrange(1,4),xrange(36))])
     m2=prod([P((3*x+1,3*x+2,3*x+3)) for x in xrange(108)])
@@ -4975,7 +4975,7 @@ def JankoKharaghaniTonchevGraph():
                 (18*x+4,18*x+13),(18*x+5,18*x+14),(18*x+6,18*x+15),(18*x+7,18*x+16),
                 (18*x+8,18*x+17),(18*x+9,18*x+18)]))
                  for x in xrange(18))
-    G=PermutationGroup([m1,m2,t,n1,n2,s,k])
+    G=libgap.Group(map(lambda p: libgap.PermList(p), [m1,m2,t,n1,n2,s,k]))
     B1=(19,22,25,29,30,31,33,34,35,37,40,43,47,48,49,51,52,53,55,56,57,65,
         66,67,68,70,72,76,77,78,79,80,81,82,86,90,92,93,95,96,98,99,100,105,107,
         109,110,111,119,120,121,122,124,126,128,129,131,132,134,135,136,141,143,
@@ -4995,6 +4995,6 @@ def JankoKharaghaniTonchevGraph():
     Gamma=Graph(multiedges=False,name='Janko-Kharaghani-Tonchev')
     for i,b in ((1,B1),(163,B163)):
         for j in b:
-            Gamma.add_edges(map(tuple,G.orbit((i,j),action="OnSets")))
+            Gamma.add_edges(map(tuple,G.Orbit(libgap.Set([i,j]), libgap.OnSets)))
     Gamma.relabel()
     return Gamma

[dimpase]

comment:12

hmm:

$ git pull trac public/JKandJKT
fatal: unable to connect to trac.sagemath.org:
trac.sagemath.org[0: 128.208.160.253]: errno=Connection refused

[sagetrac-git]

Changed commit from e123de4 to 567608b

[sagetrac-git]

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

567608b

10-fold speedup using libGAP and reducing # of edge orbits

[dimpase]

comment:14

Hope you like my last commit - otherwise I'm happy with the ticket; please set it positive review then!

[nathanncohen]

comment:15

Dima: in Python a call to 'map' creates a new list in memory. Do you understand of painful that makes it to read changes like that?

-        for j in b:
+        for j in map(lambda x: x[0], st.OrbitsDomain(b)):

A new list in memory only because you want j[0] instead of j?...

Of course we don't care, or course it's totally negligible, but what the hell. Don'you want to write Python code instead of badly translating GAP code into Python?..

Nathann

[nathanncohen]

comment:16

Anyway.

Did you try to figure out where was the loss of time coming from? I don't see Sage ever improving if you switch to using GAP directly whenever Sage's interface is too slow.

Nathann

[dimpase]

comment:17

Replying to @nathanncohen:

Dima: in Python a call to 'map' creates a new list in memory. Do you understand of painful that makes it to read changes like that?

-        for j in b:
+        for j in map(lambda x: x[0], st.OrbitsDomain(b)):

A new list in memory only because you want j[0] instead of j?...

no, it's actually two changes; say, if st was a Sage PermutationGroup it would be

-        for j in b:
+        for j in map(lambda x: x[0], st.orbits(b)):

to discard taking representatives of the same orbit of st (a 3 to 4-fold speedup), and then the translation to libGAP (another 3-fold speedup) is

-        for j in map(lambda x: x[0], st.orbits(b)):
+        for j in map(lambda x: x[0], st.OrbitsDomain(b)):

OK, I should have used imap.

[dimpase]

comment:18

Replying to @nathanncohen:

Did you try to figure out where was the loss of time coming from? I don't see Sage ever improving if you switch to using GAP directly whenever Sage's interface is too slow.

Well, in both cases, it uses GAP, only when one uses libGAP the data goes back and forth much faster, a 3-fold speedup (apart from pipes, it's conversion to/from strings from/to lists of integers that is not needed when libGAP is used). Sage will improve when a fuller switch to libGAP happens...

[vbraun]

Changed branch from public/JKandJKT to 567608b

[nathanncohen]

Changed commit from 567608b to none

[nathanncohen]

comment:21

Coooooool... :-P