Opened 3 years ago
Closed 2 years ago
#30312 closed enhancement (fixed)
Graphs: more classical parameters distance regular graphs
Reported by: | gh-Ivo-Maffei | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.2 |
Component: | graph theory | Keywords: | |
Cc: | dimpase | Merged in: | |
Authors: | Ivo Maffei | Reviewers: | Dima Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | 9e69f0d (Commits, GitHub, GitLab) | Commit: | 9e69f0dc82fe102a853bb3cefe6c874c094227c2 |
Dependencies: | #30303 | Stopgaps: |
Description
Added three families of distance regular graphs, they are based, respectively, on bilinear forms, alternating forms and hermitian forms.
Also moved AztecDiamondGraph
to families of graphs rather than basic structures.
Change History (57)
comment:1 Changed 3 years ago by
Branch: | → public/graphs/30312 |
---|---|
Cc: | dimpase added |
Commit: | → b921ccf7637edff34fc263f8c680e6918bd077be |
Status: | new → needs_review |
comment:2 Changed 2 years ago by
Status: | needs_review → needs_work |
---|
comment:3 Changed 2 years ago by
..FormGraph
should be ..FormsGraph
, as these are graphs with vertex sets being sets of forms, right?
comment:4 Changed 2 years ago by
Yes, I've changed it and also merged #30303 (with the update to 9.2.beta8).
If #29886 will take too much time, I could remove the dependency and generate the needed matrices with the ...FormsGraph
method.
This is what I initially did ages ago.
Of course as soon as #29886 or something similar gets fixed, I can change back these functions to something neater.
comment:5 Changed 2 years ago by
Commit: | b921ccf7637edff34fc263f8c680e6918bd077be → 503bc12a821a89facd557b40096148583b12e911 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
19b859e | moved and renamed orthogonal dual polar
|
d6a403b | Merge branch 9.2.beta8 into 30303
|
d7453fa | removed cython code; added imports
|
562283f | Merge branch 30303 (and sage 9.2.beta8) into 30312
|
503bc12 | renamed functions; added meataxe flag to doctests
|
comment:6 Changed 2 years ago by
Commit: | 503bc12a821a89facd557b40096148583b12e911 → 38577a8a39c027b1ee7d6f6c577e25063910290d |
---|
comment:7 Changed 2 years ago by
Dependencies: | #30303, #29886 → #30303 |
---|---|
Status: | needs_work → needs_review |
Now this should work without #29886. It's much slower but it should do for now.
comment:8 follow-up: 10 Changed 2 years ago by
Reviewers: | → Dima Pasechnik |
---|---|
Status: | needs_review → needs_work |
very long doctests that need more than 1 minute, say, should be tagged as # not tested
- by the way, on my machine some long doctests with meataxe used crash with Memory Error
, while complete if run at the sage prompt (due to doctest parallelism I guess).
Also, there is a typo: bilienar
-> bilinear
comment:9 Changed 2 years ago by
Commit: | 38577a8a39c027b1ee7d6f6c577e25063910290d → cf5243dd6deda6d48ad3d19b45da4f3a31fce0b7 |
---|
comment:10 Changed 2 years ago by
Status: | needs_work → needs_review |
---|
I added the # not tested
flag and run all doctests with and without the --long
flag.
They all pass in roughly 2 min.
comment:12 Changed 2 years ago by
I also think that the Hermitian case should take not q=r2 as input, but r itself.
comment:13 follow-up: 15 Changed 2 years ago by
As you are on the forms graph here, let's add the missing case of the symmetric 3x3 forms graph, as discussed in [BCN] corrections: https://www.win.tue.nl/~aeb/drg/ch9
For $n = 3$ we find a distance-regular graph with intersection array $"{"q sup 3 -1 , q sup 3 -q , q sup 3 -q sup 2 + 1 ;~ 1,q,q sup 2 -1"}"$ (in the diagram on p. 286, merge the balloons for the forms of rank 3 and the alternating forms of rank 2).
comment:14 follow-up: 16 Changed 2 years ago by
Having the latter should allow a more economic definition of the Hermitian case, as a product of the symmetric forms graph over GF(r) and alternating forms graph over GF(r).
It's the product, in the sense that vertices are pairs, 2 vertices (a,b) and (c,d) are adjacent iff rk(a-c+i(b-d))=1, where i is a generator of GF(q) over GF(r). (If I'm not mistaken, rk(a-c+i(b-d))=1 may be expressed as "either rk(a-c)+rk(b-d)<2, or rk(a-c)=rk(b-d)=1, Ker(a-c)=Ker(b-d).)
comment:15 follow-up: 17 Changed 2 years ago by
Replying to dimpase:
As you are on the forms graph here, let's add the missing case of the symmetric 3x3 forms graph, as discussed in [BCN] corrections: https://www.win.tue.nl/~aeb/drg/ch9
For $n = 3$ we find a distance-regular graph with intersection array $"{"q sup 3 -1 , q sup 3 -q , q sup 3 -q sup 2 + 1 ;~ 1,q,q sup 2 -1"}"$ (in the diagram on p. 286, merge the balloons for the forms of rank 3 and the alternating forms of rank 2).
I think these graphs have the same intersection array of the Brouwer-Pasechnik graph (https://arxiv.org/abs/1107.0475). You definitely know if I'm wrong.
The construction given for that graph is easy and works in O(E), so I chose that one over the symmetric matrices one. Of course we could have both if you wish.
comment:16 follow-up: 18 Changed 2 years ago by
Replying to dimpase:
Having the latter should allow a more economic definition of the Hermitian case, as a product of the symmetric forms graph over GF(r) and alternating forms graph over GF(r).
It's the product, in the sense that vertices are pairs, 2 vertices (a,b) and (c,d) are adjacent iff rk(a-c+i(b-d))=1, where i is a generator of GF(q) over GF(r). (If I'm not mistaken, rk(a-c+i(b-d))=1 may be expressed as "either rk(a-c)+rk(b-d)<2, or rk(a-c)=rk(b-d)=1, Ker(a-c)=Ker(b-d).)
I'll still try this construction. Could you clarify what you mean by "a generator of GF(q) over GF(r)"? Do you mean $i \in GF(q)$ s.t. $i$ generated $GF(q) / GF(r)$ as vector spaces over $GF(r)$?
comment:17 Changed 2 years ago by
Replying to gh-Ivo-Maffei:
Replying to dimpase:
As you are on the forms graph here, let's add the missing case of the symmetric 3x3 forms graph, as discussed in [BCN] corrections: https://www.win.tue.nl/~aeb/drg/ch9
For $n = 3$ we find a distance-regular graph with intersection array $"{"q sup 3 -1 , q sup 3 -q , q sup 3 -q sup 2 + 1 ;~ 1,q,q sup 2 -1"}"$ (in the diagram on p. 286, merge the balloons for the forms of rank 3 and the alternating forms of rank 2).I think these graphs have the same intersection array of the Brouwer-Pasechnik graph (https://arxiv.org/abs/1107.0475). You definitely know if I'm wrong.
The construction given for that graph is easy and works in O(E), so I chose that one over the symmetric matrices one. Of course we could have both if you wish.
in fact, yes, sure, https://arxiv.org/abs/1107.0475 points out to https://www.win.tue.nl/~aeb/drg/ch9 and discusses the relation between the two. There is something with q being even or odd there, so beware of details.
comment:18 Changed 2 years ago by
Replying to gh-Ivo-Maffei:
I'll still try this construction. Could you clarify what you mean by "a generator of GF(q) over GF(r)"? Do you mean $i \in GF(q)$ s.t. $i$ generated $GF(q) / GF(r)$ as vector spaces over $GF(r)$?
yes. That is, any i in GF(q)\GF(r) will do.
comment:19 follow-up: 20 Changed 2 years ago by
Status: | needs_review → needs_work |
---|
at the moment graphs.HermitianFormsGraph(2,9)
is horribly slow.
E.g. it could in part be due to slowness in computing the below-diagonal part. Taking to r
-th power is perhaps the worst possible way to compute the map in question. Instead, choose i
as above, compute i
r (once), then for a,b in GF(r) one has (a+ib)r= a+irb.
Another place is rank 1 Hermitian matrices. Each such nxn matrix has form vv*, for v in GF(q)n, and * denoting the map induced by taking to r-th power. So no need to compute ranks and filter on rank 1.
comment:20 Changed 2 years ago by
Replying to dimpase:
at the moment
graphs.HermitianFormsGraph(2,9)
is horribly slow.
Totally agree, also graphs.AlternatingFormsGraph
is too slow.
I thought that the "product" construction was meant to solve the issue with the HermitianFormsGraph
.
comment:21 Changed 2 years ago by
The "product" boils down pretty much to modifications I just explained, anyway. Also, there seems to be no need to even construct matrices (I think the only place you needed them is to compute rank, but this can be skipped, as we just saw) - just keep everything as vectors.
comment:22 Changed 2 years ago by
Commit: | cf5243dd6deda6d48ad3d19b45da4f3a31fce0b7 → 0dcb91194e64a9bb8ff20c5b4c2382bef9085c73 |
---|
comment:23 Changed 2 years ago by
Status: | needs_work → needs_review |
---|
Now the function is quite fast. I wish AlternatingFormsGraph
could be as fast.
comment:24 Changed 2 years ago by
Hermitean forms tests don't need to be tagged by # meataxe
.
There is also a typo tow
-> two
.
comment:25 Changed 2 years ago by
It seems to me that any alternating rank 2 nxn form can be obtained from two n-vectors v,u, as vuT - uvT. This way alternating forms graphs can be dealt with in a similar way as Hermitean, without using meataxe and matrix spaces.
comment:26 Changed 2 years ago by
Commit: | 0dcb91194e64a9bb8ff20c5b4c2382bef9085c73 → cfcf928007c57be935f05cea9c7acdaf2610c4ac |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
9a69985 | removed doctest flag meataxe; fix typo
|
747b3bc | Merge 9.2.beta10 into 30312
|
c7a4c92 | initial attempt to speed up alternating forms
|
be34815 | added sig_check; code uses only upper triangular entries
|
cfcf928 | cleaned some docstring and code
|
comment:27 Changed 2 years ago by
The AlternatingFormsGraph
still builds some redundant rank 2 matrices.
For instance, AlternatingFormsGraph(4, 3)
builds 2080 rank 2 matrices, but only 260 of them are distinct.
comment:28 Changed 2 years ago by
You can normalise one of the vectors, say u, to have the 1st non-zero coordinate equal to 1.
comment:29 Changed 2 years ago by
There is still quite a lot of redundancy:
AlternatingFormsGraph(4, 3)
builds 1040 instead of 260 and
AlternatingFormsGraph(3, 4)
builds 315 instead of 63.
If getting the exact number is too complex, then I won't push further.
comment:30 Changed 2 years ago by
Commit: | cfcf928007c57be935f05cea9c7acdaf2610c4ac → 582b480ccc33e3d196c377c268f76efbc01122b0 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
582b480 | normilised vector in alternating forms graph
|
comment:31 Changed 2 years ago by
it seems that for AlternatingFormsGraph(4, 3)
one somehow gets one rank 2 matrix in 4 different ways. Could you post an example?
comment:32 Changed 2 years ago by
For instance:
[0 2 2 1] [1 0 0 1] [1 0 0 1] [2 2 2 0] # the above is obtained by the following 4 pairs (v, u) [((2, 2, 2, 0), (0, 1, 1, 2)), ((2, 1, 1, 1), (0, 1, 1, 2)), ((2, 0, 0, 2), (0, 1, 1, 2)), ((0, 1, 1, 2), (1, 0, 0, 1))]
Not all matrices are constructed by pairs where 1 vectors is in all pairs (above (0, 1, 1, 2)):
[0 1 2 0] [2 0 0 2] [1 0 0 1] [0 1 2 0] #given by [((0, 2, 1, 0), (1, 0, 0, 1)), ((1, 0, 0, 1), (0, 1, 2, 0)), ((1, 2, 1, 1), (0, 1, 2, 0)), ((1, 1, 2, 1), (0, 1, 2, 0))]
This time the vector (0, 1, 2, 0) in multiplied by 2 when it appears as v
comment:33 Changed 2 years ago by
One further optimisation would be to take unordered pairs of u,v, both with 1st non-zero coordinates equal to 1, remove duplicates, and then scale the resulting matrices by the non-zero elements of GF(q). This would cut the duplication by 2, I believe.
I give up on further improving this for the time being (this seems to be a non-trivial maths question).
I believe for our purposes it is fast enough.
comment:34 Changed 2 years ago by
Commit: | 582b480ccc33e3d196c377c268f76efbc01122b0 → dd0514777a3cd1493dcc280de5ec00a518f04115 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
dd05147 | normalised v and multiply all matrices by all non-zero scalars; unordered pairs
|
comment:35 Changed 2 years ago by
Commit: | dd0514777a3cd1493dcc280de5ec00a518f04115 → 1b8db43d9fd3b49d9345c74c716c6fda7a870351 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
1b8db43 | fix typos
|
comment:36 follow-up: 37 Changed 2 years ago by
Can we also get rid of meataxe in BilinearFormsGraph ? Again, the idea is that every rank 1 mxn matrix can be written as uvT, for m-vector u and n-vector v, and so the adjacency may be computed without actually doing through matrices and their ranks.
comment:37 Changed 2 years ago by
Replying to dimpase:
Can we also get rid of meataxe in BilinearFormsGraph ? Again, the idea is that every rank 1 mxn matrix can be written as uvT, for m-vector u and n-vector v, and so the adjacency may be computed without actually doing through matrices and their ranks.
I can avoid computing ranks, but while in AlternatingFormsGraph
and HermitianFormsGraph
I was representing a form by the vector of the upper triangular entries, in BilinearFormsGraph
I need the whole matrix.
I can try using the MatrixSpace without implementation=meataxe
or "flattening" all matrices to vectors, but we'll lose speed.
comment:40 Changed 2 years ago by
Commit: | 1b8db43d9fd3b49d9345c74c716c6fda7a870351 → 339b4f58a50e812550493e3657085dddcad3bc7b |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
e9cdce9 | generate rank 1 bilienear forms without computing ranks
|
91bc5bc | removed testing code
|
383397d | expanded outer_product into cython; now as fast as initial implementation
|
48395a1 | use integer vectors in bilinear form to represents matrices
|
339b4f5 | fix docstrings
|
comment:41 Changed 2 years ago by
Using integer vectors to iterate over the matrices cuts all times to half respect to the initial implementation with meataxe.
comment:42 Changed 2 years ago by
not sure how you encode elements of GF(q) as integers, in particular for nonprime q
comment:43 Changed 2 years ago by
I use integers only in matricesOverq
and the encoding is given by Fqelems
which maps integers to elements of GF(q).
The inverse GF(q) -> Int is not needed but it is given by toInt = {n: x for n, x in enumerate(Fqelems)}
.
All arithmetic is done with elements of GF(q). The integers are only used to speed up the iteration for m1 in matricesOverq
.
comment:44 Changed 2 years ago by
by the way, nothing prevents you from trying to use the meataxe backend for matrices, and falling back on the default one if it's not available.
comment:45 follow-up: 46 Changed 2 years ago by
Status: | needs_review → positive_review |
---|
If you like to add the meataxe speed up option, please do, else it's good as it is.
comment:46 Changed 2 years ago by
Replying to dimpase:
If you like to add the meataxe speed up option, please do, else it's good as it is.
The current code is faster than any previous version that used meataxe I'm not sure how to speed things up more with meataxe
comment:47 Changed 2 years ago by
Branch: | public/graphs/30312 → 339b4f58a50e812550493e3657085dddcad3bc7b |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
comment:48 Changed 2 years ago by
Commit: | 339b4f58a50e812550493e3657085dddcad3bc7b |
---|---|
Resolution: | fixed |
Status: | closed → new |
comment:49 Changed 2 years ago by
********************************************************************** File "src/sage/graphs/generators/distance_regular.pyx", line 629, in sage.graphs.generators.distance_regular.BilinearFormsGraph Failed example: G = graphs.BilinearFormsGraph(3,3,3) # long time (20 s) Exception raised: Traceback (most recent call last): File "/var/lib/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 715, in _run self.compile_and_execute(example, compiler, test.globs) File "/var/lib/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1139, in compile_and_execute exec(compiled, globs) File "<doctest sage.graphs.generators.distance_regular.BilinearFormsGraph[2]>", line 1, in <module> G = graphs.BilinearFormsGraph(Integer(3),Integer(3),Integer(3)) # long time (20 s) File "sage/graphs/generators/distance_regular.pyx", line 679, in sage.graphs.generators.distance_regular.BilinearFormsGraph (build/cythonized/sage/graphs/generators/distance_regular.c:11661) m3 = tuple([m1[i] + m2[i] for i in range(d*e)]) MemoryError ********************************************************************** File "src/sage/graphs/generators/distance_regular.pyx", line 630, in sage.graphs.generators.distance_regular.BilinearFormsGraph Failed example: G.order() # long time (due to above) Expected: 19683 Got: 512 **********************************************************************
comment:50 Changed 2 years ago by
Branch: | 339b4f58a50e812550493e3657085dddcad3bc7b → public/graphs/30312 |
---|---|
Commit: | → 4675366ff4d5f48f69968f66fa2dc7abe4a5f5ad |
Status: | new → needs_review |
I made the same changes of #30337 commit 59776810db8b3352985cc688c82b9ea6e48a70dc
comment:51 Changed 2 years ago by
Commit: | 4675366ff4d5f48f69968f66fa2dc7abe4a5f5ad → 97f045062e412beaeaeec5abf2bcceb9030140e7 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
97f0450 | Merge branch 'develop' into t/30312
|
comment:52 Changed 2 years ago by
some tests should still be tagged long:
Trying (line 388): G = graphs.distance_3_doubly_truncated_Golay_code_graph() Expecting nothing ok [10.27 s] ... Trying (line 582): G = graphs.UstimenkoGraph(5, 2) Expecting nothing ok [22.18 s] Trying (line 583): G.order() Expecting: 2295 ok [0.00 s] Trying (line 585): G.is_distance_regular(True) Expecting: ([310, 224, None], [None, 1, 35]) ok [11.42 s] Trying (line 633): G.is_distance_regular(True) Expecting: ([105, 84, 48, None], [None, 1, 6, 28]) ok [17.22 s]
comment:53 Changed 2 years ago by
Commit: | 97f045062e412beaeaeec5abf2bcceb9030140e7 → 5344f35562db78a3456124f2af0b7ffbd2a47d5a |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
5344f35 | added long time flags and fixed van Lint name
|
comment:54 Changed 2 years ago by
#long
tag missing on line 588, leading to a failing doctest:
File "src/sage/graphs/generators/distance_regular.pyx", line 588, in sage.graphs.generators.distance_regular.UstimenkoGraph Failed example: G.is_distance_regular(True) Expected: ([390, 243, None], [None, 1, 130]) Got: ([70, 32, None], [None, 1, 35])
comment:55 Changed 2 years ago by
Commit: | 5344f35562db78a3456124f2af0b7ffbd2a47d5a → 9e69f0dc82fe102a853bb3cefe6c874c094227c2 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
9e69f0d | missing # long time
|
comment:56 Changed 2 years ago by
Status: | needs_review → positive_review |
---|
long tests are still a bit too long to my taste, but OK.
comment:57 Changed 2 years ago by
Branch: | public/graphs/30312 → 9e69f0dc82fe102a853bb3cefe6c874c094227c2 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Last 10 new commits:
some code formatting
added some sig_checks
code for symmetric matrices
added examples and tests
fixed formatting
removed trailing whitespaces
fixed more code formatting; allow f=None for nomal symmetric matrices
added bilinear, alternating and hermitian form graphs
removed sporadic g; fixed doctests
removed random s