Opened 6 years ago

Closed 6 years ago

Last modified 6 years ago

#19872 closed enhancement (fixed)

regular symmetric Hadamard matrices for n=324

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: 567608b (Commits, GitHub, GitLab) Commit:
Dependencies: #19861 Stopgaps:

Status badges

Description (last modified by 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.

Change History (21)

comment:1 Changed 6 years ago by git

  • Commit changed from 988214e3f348db7f00d8d5eb282a6636f3b9a61f to afcb53c134fb82502275fc7c5fadec55787b85ef

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

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

comment:2 Changed 6 years ago by ncohen

  • Dependencies set to #19861

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

comment:3 follow-up: Changed 6 years ago by ncohen

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

comment:4 Changed 6 years ago by dimpase

  • Status changed from new to needs_review

comment:5 in reply to: ↑ 3 Changed 6 years ago by dimpase

Replying to ncohen:

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

comment:6 Changed 6 years ago by git

  • Commit changed from afcb53c134fb82502275fc7c5fadec55787b85ef to a42d6ac5db274aff0ce8dcd58c0c9c2fe318e4f8

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

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

comment:7 Changed 6 years ago by dimpase

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

comment:8 Changed 6 years ago by git

  • Commit changed from a42d6ac5db274aff0ce8dcd58c0c9c2fe318e4f8 to d63a13b2129d6a0b358b015367a3469fd5f28c60

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

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

comment:9 Changed 6 years ago by git

  • Commit changed from d63a13b2129d6a0b358b015367a3469fd5f28c60 to e123de45de77715fb84f03697e52d3d2b3c6e8a0

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

659a07ftrac #19872: Merged with 7.0.rc1
e123de4trac #19872: Review

comment:10 Changed 6 years ago by ncohen

  • Reviewers set to Nathann Cohen

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

comment:11 Changed 6 years ago by dimpase

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

comment:12 Changed 6 years ago by dimpase

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

comment:13 Changed 6 years ago by git

  • Commit changed from e123de45de77715fb84f03697e52d3d2b3c6e8a0 to 567608be0b53ec173be1f1a755af202c4a4de564

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

567608b10-fold speedup using libGAP and reducing # of edge orbits

comment:14 Changed 6 years ago by dimpase

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

comment:15 follow-up: Changed 6 years ago by ncohen

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

comment:16 follow-up: Changed 6 years ago by ncohen

  • Status changed from needs_review to positive_review

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

comment:17 in reply to: ↑ 15 Changed 6 years ago by dimpase

Replying to ncohen:

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.

comment:18 in reply to: ↑ 16 Changed 6 years ago by dimpase

Replying to ncohen:

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

comment:19 Changed 6 years ago by dimpase

  • Description modified (diff)

comment:20 Changed 6 years ago by vbraun

  • Branch changed from public/JKandJKT to 567608be0b53ec173be1f1a755af202c4a4de564
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:21 Changed 6 years ago by ncohen

  • Commit 567608be0b53ec173be1f1a755af202c4a4de564 deleted

Coooooool... :-P

Note: See TracTickets for help on using tickets.