search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.33k stars 453 forks source link

skew-Hadamard matrices and related srg's #19418

Closed dimpase closed 8 years ago

dimpase commented 8 years ago

implementing few basic constructions of skew-Hadamard matrices and 3 families of assoc. srg's.

Depends on #19309

CC: @nathanncohen

Component: combinatorics

Author: Dima Pasechnik

Branch/Commit: c50c78d

Reviewer: Nathann Cohen

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

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago
comment:36

Okayokay. Well I'm reviewing the code at the moment.

By the way on my way to here I finished a wonderful script that extracts tables from a pdf file. Some french guys need that to turn into open data what the government releases to feel open (i.e. ugly pdf files).

http://www.performance-publique.budget.gouv.fr/sites/performance_publique/files/farandole/ressources/2016/pap/pdf/jaunes/jaune2016_commissions.pdf

But we'll show 'em.

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago
comment:37

Helloooooooooo Dima,

Here is another pass:

Nathann

dimpase commented 8 years ago
comment:38

Replying to @nathanncohen:

  • In the n%8==0 case you implement the product construction of skew hadamard matrices with a 2x2 matrix only. Is there a reason to that?

huh? I have there

    elif n % 8 == 0:
        if skew_hadamard_matrix(n//2,existence=True, check=False):
            if existence:
                return true()
            H = skew_hadamard_matrix(n//2,check=False)
            M = block_matrix([[H,H], [-H.T,H.T]])

        else: # try Williamson construction
            for d in divisors(n)[2:-2]: # skip 1, 2, n/2, and n
             ... more stuff

so I first check if I can multiply with 2x2 matrix, and if not, I try Williamson construction.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

fd7894acheck that skew_normalize worked
3503d62rest of fixes for hadamard_matrix.py
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 01763fd to 3503d62

dimpase commented 8 years ago
comment:40

Replying to @nathanncohen:

  • I don't think that you need to import functions at the top of every single '::' block. If you imported them in a previous doctest of the same function they are usually around. I say 'usually' because I don't think I read that anywhere, but it just works. If the order in which doctests are run can be 'random', I think that it just shuffles the functions and not the doctests inside of a function.

OK. Removed some of these...

  • docstring of zero_position: bad alignment of 'place it first'. Misses one space.

  • Same line: the sentence is not complete -- what about adding 'When it' at its beginning?

  • You did not doctest your new flag. Also, the code looks wrong.

well, actually in this case the code is not doing what is advertised; without my flag the matrix for n=4k-1 is not symmetric w.r.t. the anti-diagonal; the submatrix obtained by removal of the 1st row and the 1st column is symmetric w.r.t. the anti-diagonal. I changed the doc accordingly. And added a doctest.

  • Docstring of williamson_goethals_seidel_skew_hadamard_matrix. Things seem to miss from the first sentence of the paragraph. Or it's me being sick again. P.S.: syntactically, a ')' is missing at least.

fixed.

  • Same function. The following doc should be in the function that actually returns those matrices:

    +    Matrices for `n=36` and `52` are given in [GS70s]_. Matrices for `n=92` are given
+    in [Wall71]_.

moved

  • _GS_skew_hadamard -- the name of that function is a bit too vague. What about GS_skew_hadamard_smallcases? You don't necessarily need to make it private, by the way. It lives in a module and does not appear in the global namespace, so only the interested guys will find it. And it's not technically complicated to use, the input/output is well defined and reliable. It can't be misused.

renamed as you proposed.

  • private functions need doctests too. 'cdef' is the only situation in which you don't need them.

OK, OK... added

  • def pmtoZ(s): could be defined in the only 'if' that requires it (not very important).

well, if we added more data in +- - format, it would be at the right place as it is.

  • docstring of skew_hadamard_matrix -- in the block of doc about 'existence', one reads 'but that design does not exist'. Could you replace 'design' by 'matrix'?

done

  • I don't see why the following doctest has a 'long' flag

    sage: skew_hadamard_matrix(784,existence=True) # long time

    If you actually built the matrix, however, that would be correct.

good catch - fixed

  • I don't think that check=False is useful when existence=True

    skew_hadamard_matrix(n//2,existence=True, check=False)

uh oh... fixed.

  • if _GS_skew_hadamard(n, existence=True) -- it hardly matters, but it would be 'cleaner' to call this (quick) function before checking the more complicated (recursive) constructions.

Oh, well, if you feel like changing this, go ahead...

  • Shouldn't you also check that the matrix is 'skew-normalized', as we do with the regular normalization?

    +    if skew_normalize:
+        dd = diagonal_matrix(M[0])
+        M = dd*M*dd
+    if check:
+        assert is_hadamard_matrix(M, normalized=False, skew=True)

added a check.

  • If you are too humble to do it yourself, I will change that to 'Return the Pasechnik graph of order n' :-)

    +    Pseudo-`OA(2n-1,4n-1)`-graph from a skew Hadamard matrix of order `4n`

if you must...

  • Please add your new graphs to the graphs.<tab> constructor.

actually, I removed them, but I'll add them again...

New commits:

fd7894acheck that skew_normalize worked
3503d62rest of fixes for hadamard_matrix.py

New commits:

fd7894acheck that skew_normalize worked
3503d62rest of fixes for hadamard_matrix.py
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

595f7e9added graphs to graphs., and doc(test)s additions and fixes
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 3503d62 to 595f7e9

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago
comment:43
sage: skew_hadamard_matrix(816)
...
TypeError: unsupported operand parent(s) for '*': 'Full MatrixSpace of 12 by 12 dense matrices over Integer Ring' and 'Full MatrixSpace of 68 by 68 dense matrices over Integer Ring'
6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago
comment:44

Can you tell me why you apparently refuse my request about the behaviour of 'sparse' in 'circulant'?

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 595f7e9 to 06fd9b4

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

06fd9b4fix the bug, and add docs
dimpase commented 8 years ago
comment:46

Replying to @nathanncohen:

Can you tell me why you apparently refuse my request about the behaviour of 'sparse' in 'circulant'?

oops - forgot about it. Tonight I'll have more time to look at it.

The last commit fixes the n=816 bug (--facepalm--) - thanks for the example. I checked now the values of n up to 1200, they appears to work fine...

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago
comment:47

Okayyy. Thanks for the fix ;-)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

c50c78dfixing circulant's behaviour
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 06fd9b4 to c50c78d

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago
comment:50

Okayyyyyyyyyyyy... Thanks for this branch ! ;-)

Nathann

dimpase commented 8 years ago
comment:51

OK, with all the changes, patchbots (most of them) seem to be happy. And the reviewer?

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago
comment:52

He's happy too.

dimpase commented 8 years ago
comment:53

Thanks! By the way, _check_database() now says for me:

...
Sage can build a (1024, 462, 206, 210), Brouwer's database cannot
Sage can build a (1024, 561, 308, 306), Brouwer's database cannot

In Andries Brouwer's database:
- 448 impossible entries
- 2950 undecided entries
- 1140 realizable entries (Sage misses 36 of them)

On the other hand the graphs above can be found in http://www.win.tue.nl/~aeb/graphs/srg/srgtab1001-1050.html Does it mean that Sage's copy of the DB needs an update?

OK, so should I next take out Mathon's v=45?

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 8 years ago
comment:54

Does it mean that Sage's copy of the DB needs an update?

Yes. We gave him info to update his database but we didn't update our copy. By the way, the difference between our copy and his can be seen as 'one of the side-effects' of the work we have been doing. We may need that info.

OK, so should I next take out Mathon's v=45?

Take as many as you can out. I don't think that there is any left that I can implement: those that I thought manageable were apparently wrong constructions, and the authors 'play dead'.

Nathann

vbraun commented 8 years ago

Changed branch from public/19418 to c50c78d