Opened 9 months ago

Closed 7 months 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:

Status badges

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 9 months ago by gh-Ivo-Maffei

  • Branch set to public/graphs/30312
  • Cc dimpase added
  • Commit set to b921ccf7637edff34fc263f8c680e6918bd077be
  • Status changed from new to needs_review

Last 10 new commits:

efa9340some code formatting
be18963added some sig_checks
7f4d042code for symmetric matrices
e4957c2added examples and tests
10f063ffixed formatting
c4f1e6fremoved trailing whitespaces
7528f25fixed more code formatting; allow f=None for nomal symmetric matrices
e171598added bilinear, alternating and hermitian form graphs
7fcf73eremoved sporadic g; fixed doctests
b921ccfremoved random s

comment:2 Changed 8 months ago by gh-Ivo-Maffei

  • Status changed from needs_review to needs_work

Remainder to update once #30303 and #29886 are sorted

comment:3 Changed 8 months ago by dimpase

..FormGraph should be ..FormsGraph, as these are graphs with vertex sets being sets of forms, right?

comment:4 Changed 8 months ago by gh-Ivo-Maffei

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 8 months ago by git

  • Commit changed from b921ccf7637edff34fc263f8c680e6918bd077be to 503bc12a821a89facd557b40096148583b12e911

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

19b859emoved and renamed orthogonal dual polar
d6a403bMerge branch 9.2.beta8 into 30303
d7453faremoved cython code; added imports
562283fMerge branch 30303 (and sage 9.2.beta8) into 30312
503bc12renamed functions; added meataxe flag to doctests

comment:6 Changed 8 months ago by git

  • Commit changed from 503bc12a821a89facd557b40096148583b12e911 to 38577a8a39c027b1ee7d6f6c577e25063910290d

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

9a3e609reverted changes to matrix_space.py
e78c2d0removed dependecies from symmetric generator
38577a8fixed bug with matrix generation; added meataxe flag to tests

comment:7 Changed 8 months ago by gh-Ivo-Maffei

  • Dependencies changed from #30303, #29886 to #30303
  • Status changed from needs_work to needs_review

Now this should work without #29886. It's much slower but it should do for now.

comment:8 follow-up: Changed 8 months ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to 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 8 months ago by git

  • Commit changed from 38577a8a39c027b1ee7d6f6c577e25063910290d to cf5243dd6deda6d48ad3d19b45da4f3a31fce0b7

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

ad6944fMerge branch 9.2.beta9 into 30312
cf5243dfix doctests

comment:10 in reply to: ↑ 8 Changed 8 months ago by gh-Ivo-Maffei

  • Status changed from needs_work to 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:11 Changed 8 months ago by dimpase

more typos

  • adjecent -> adjacent
  • aprime -> a prime

comment:12 Changed 8 months ago by dimpase

I also think that the Hermitian case should take not q=r2 as input, but r itself.

comment:13 follow-up: Changed 8 months ago by 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).

comment:14 follow-up: Changed 8 months ago by 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).)

comment:15 in reply to: ↑ 13 ; follow-up: Changed 8 months ago by 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.

comment:16 in reply to: ↑ 14 ; follow-up: Changed 8 months ago by gh-Ivo-Maffei

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)$?

Last edited 8 months ago by gh-Ivo-Maffei (previous) (diff)

comment:17 in reply to: ↑ 15 Changed 8 months ago by dimpase

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 in reply to: ↑ 16 Changed 8 months ago by dimpase

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: Changed 8 months ago by dimpase

  • Status changed from needs_review to 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 ir (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 in reply to: ↑ 19 Changed 8 months ago by gh-Ivo-Maffei

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 8 months ago by dimpase

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 8 months ago by git

  • Commit changed from cf5243dd6deda6d48ad3d19b45da4f3a31fce0b7 to 0dcb91194e64a9bb8ff20c5b4c2382bef9085c73

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

0f1b679fixed some typos; moved hermitian to use r; added product construction
0dcb911concluded product construction using only upper triangular entries; fix docstrings

comment:23 Changed 8 months ago by gh-Ivo-Maffei

  • Status changed from needs_work to needs_review

Now the function is quite fast. I wish AlternatingFormsGraph could be as fast.

comment:24 Changed 8 months ago by dimpase

Hermitean forms tests don't need to be tagged by # meataxe. There is also a typo tow -> two.

comment:25 Changed 8 months ago by dimpase

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 8 months ago by git

  • Commit changed from 0dcb91194e64a9bb8ff20c5b4c2382bef9085c73 to cfcf928007c57be935f05cea9c7acdaf2610c4ac

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

9a69985removed doctest flag meataxe; fix typo
747b3bcMerge 9.2.beta10 into 30312
c7a4c92initial attempt to speed up alternating forms
be34815added sig_check; code uses only upper triangular entries
cfcf928cleaned some docstring and code

comment:27 Changed 8 months ago by gh-Ivo-Maffei

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 8 months ago by dimpase

You can normalise one of the vectors, say u, to have the 1st non-zero coordinate equal to 1.

comment:29 Changed 8 months ago by gh-Ivo-Maffei

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 8 months ago by git

  • Commit changed from cfcf928007c57be935f05cea9c7acdaf2610c4ac to 582b480ccc33e3d196c377c268f76efbc01122b0

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

582b480normilised vector in alternating forms graph

comment:31 Changed 8 months ago by dimpase

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 8 months ago by gh-Ivo-Maffei

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

Last edited 8 months ago by gh-Ivo-Maffei (previous) (diff)

comment:33 Changed 8 months ago by dimpase

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 8 months ago by git

  • Commit changed from 582b480ccc33e3d196c377c268f76efbc01122b0 to dd0514777a3cd1493dcc280de5ec00a518f04115

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

dd05147normalised v and multiply all matrices by all non-zero scalars; unordered pairs

comment:35 Changed 8 months ago by git

  • Commit changed from dd0514777a3cd1493dcc280de5ec00a518f04115 to 1b8db43d9fd3b49d9345c74c716c6fda7a870351

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

1b8db43fix typos

comment:36 follow-up: Changed 8 months ago by 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.

Last edited 8 months ago by dimpase (previous) (diff)

comment:37 in reply to: ↑ 36 Changed 8 months ago by gh-Ivo-Maffei

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:38 Changed 8 months ago by dimpase

In any event, please remove the rank computation there.

comment:39 Changed 8 months ago by dimpase

Otherwise, it looks good, great speedups!

comment:40 Changed 8 months ago by git

  • Commit changed from 1b8db43d9fd3b49d9345c74c716c6fda7a870351 to 339b4f58a50e812550493e3657085dddcad3bc7b

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

e9cdce9generate rank 1 bilienear forms without computing ranks
91bc5bcremoved testing code
383397dexpanded outer_product into cython; now as fast as initial implementation
48395a1use integer vectors in bilinear form to represents matrices
339b4f5fix docstrings

comment:41 Changed 8 months ago by gh-Ivo-Maffei

Using integer vectors to iterate over the matrices cuts all times to half respect to the initial implementation with meataxe.

comment:42 Changed 8 months ago by dimpase

not sure how you encode elements of GF(q) as integers, in particular for nonprime q

comment:43 Changed 8 months ago by gh-Ivo-Maffei

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 8 months ago by dimpase

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.

Last edited 8 months ago by dimpase (previous) (diff)

comment:45 follow-up: Changed 8 months ago by dimpase

  • Status changed from needs_review to positive_review

If you like to add the meataxe speed up option, please do, else it's good as it is.

comment:46 in reply to: ↑ 45 Changed 8 months ago by gh-Ivo-Maffei

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 8 months ago by vbraun

  • Branch changed from public/graphs/30312 to 339b4f58a50e812550493e3657085dddcad3bc7b
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:48 Changed 8 months ago by vbraun

  • Commit 339b4f58a50e812550493e3657085dddcad3bc7b deleted
  • Resolution fixed deleted
  • Status changed from closed to new

comment:49 Changed 8 months ago by vbraun

**********************************************************************
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 8 months ago by gh-Ivo-Maffei

  • Branch changed from 339b4f58a50e812550493e3657085dddcad3bc7b to public/graphs/30312
  • Commit set to 4675366ff4d5f48f69968f66fa2dc7abe4a5f5ad
  • Status changed from new to needs_review

I made the same changes of #30337 commit 59776810db8b3352985cc688c82b9ea6e48a70dc

comment:51 Changed 8 months ago by git

  • Commit changed from 4675366ff4d5f48f69968f66fa2dc7abe4a5f5ad to 97f045062e412beaeaeec5abf2bcceb9030140e7

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

97f0450Merge branch 'develop' into t/30312

comment:52 Changed 8 months ago by dimpase

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 8 months ago by git

  • Commit changed from 97f045062e412beaeaeec5abf2bcceb9030140e7 to 5344f35562db78a3456124f2af0b7ffbd2a47d5a

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

5344f35added long time flags and fixed van Lint name

comment:54 Changed 8 months ago by dimpase

#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 8 months ago by git

  • Commit changed from 5344f35562db78a3456124f2af0b7ffbd2a47d5a to 9e69f0dc82fe102a853bb3cefe6c874c094227c2

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

9e69f0dmissing # long time

comment:56 Changed 8 months ago by dimpase

  • Status changed from needs_review to positive_review

long tests are still a bit too long to my taste, but OK.

comment:57 Changed 7 months ago by vbraun

  • Branch changed from public/graphs/30312 to 9e69f0dc82fe102a853bb3cefe6c874c094227c2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.