Faster is_orthogonal_array

[nathanncohen]

As the ticket claims this ticket implements a Cython version of is_orthogonal_array, which is then called by is_transversal_design and are_mutually_orthogonal_latin_squares.

Also sets a check=False in the code which slowed things down. As a resultthe tests are checked faster in the designs/ folder !

Nathann

Depends on #16236

CC: @videlec @KPanComputes @dimpase

Component: combinatorial designs

Author: Nathann Cohen

Branch/Commit: 02f1247

Reviewer: Vincent Delecroix, Brett Stevens

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

[nathanncohen]

Branch: u/ncohen/16295

[nathanncohen]

Last 10 new commits:

31a53f2	trac #16235: update the MOLS table
1a13ff8	trac #16241: New MOLS shared by Ian Wanless
2af2acf	trac #16241: missing links and tests
7e77f90	trac #16241: Broken doctests
83b0d2c	trac #16241: Merged with updated #16235
c212bf9	trac #16241: Broken doctests
e655b36	trac #16236: Five mutually orthogonal latin squares of order 12
b516266	trac #16236: Merged with updated #16241
f5339fa	trac #16236: Broken doctests
0d5c222	trac #16295 : Faster is_orthogonal_array

[nathanncohen]

Commit: 0d5c222

[brettpim]

comment:4

Nathann,

The code looks good and I have tested on an example different from your doc test.

The following run fine:

make,
doc-test,
docbuild html,
code coverage is 100%

I had trouble making the pdf documentation and then went back to devel branch to check it worked Ok there. It did and then when I moved back to u/ncohen/16295 it worked. I am not sure what happened

I think this needs two things:

• it needs to be as consistent as possible with the purely python version inside orthogonal_arrays.py. That is, it will react the same way on the same input. This change should be done and then a doc-test written to verify it.

• it needs to have a doctest that demonstrates the speed improvement that cycthon gives over the purely python version inside orthogonal_arrays.py.

[nathanncohen]

comment:5

Hellllooooo !!

I had trouble making the pdf documentation and then went back to devel branch to check it worked Ok there. It did and then when I moved back to u/ncohen/16295 it worked. I am not sure what happened

Yeah, we had the same problems just one hour ago when Volker tried to merge #16277 or #16235... And it does not happen again because Sphinx is totall unreliable. I expect it to ocome from the dependencies, not from this ticket

I think this needs two things:

• it needs to be as consistent as possible with the purely python version inside orthogonal_arrays.py. That is, it will react the same way on the same input. This change should be done and then a doc-test written to verify it.

Once this patch is applied there is no python version inside of orthogonal_arrays.py, as this patch removes it. We can add any doctest you want, but what could it be ? Remember that this function is already tested a LOT by all constructions of OA/TD/MOLS as it is run on those instances every time one is built.

• it needs to have a doctest that demonstrates the speed improvement that cycthon gives over the purely python version inside orthogonal_arrays.py.

Once more, this function removes the purely python one.

Nathann

[videlec]

comment:6

Hi Nathann,

You should avoid using any in Cython. This is not properly cythonized. The following is better by 15%:

for i in range(len(OA)):
    if len(OA[i]) != k:
        if verbose:
            print {"OA"   : "Some row does not have length "+str(k),
                   "MOLS" : "The number of matrices is not "+str(k)}[terminology]

If you do so, you need to move up the cdef int i,j,l.

Vincent

[nathanncohen]

comment:7

Yoooooooo !!

You should avoid using any in Cython. This is not properly cythonized. The following is better by 15%:

It is good to know, but I really do not think that this is the critical part here :-D

Nathann

[brettpim]

comment:8

Sorry, I had changed branches and then opened orthogonal_array.py in an editor and so thought is_orthogonal_array was still there.

Here is my timing data

with Cython:

sage: time is_orthogonal_array(OA,8,9)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 27.2 µs
False
sage: time is_orthogonal_array(OA,12,11)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 239 µs
True

with Python:

sage: time is_orthogonal_array(OA,8,9,2)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 29.1 µs
False
sage: time is_orthogonal_array(OA,12,11,2)
CPU times: user 12 ms, sys: 4 ms, total: 16 ms
Wall time: 13.1 ms
True

this shows a significant improvement in speed.

However I think this needs to be fixed:

sage: is_orthogonal_array(OA,12,11,3)
True

If it is passed t=3 it should at least alert the user that it is going to override this with t=2

Here is what I think should be done:

• fix t>2 bug
• remove "any" as Vincent suggested
• implement a doc test for
  • all your bad input/format tests
  • memory test
  • t>2 test

[brettpim]

comment:9

p.s. where is sage_free documented?

[nathanncohen]

comment:10

Hello !

• fix t>2 bug

Done.

• remove "any" as Vincent suggested

Guys, it is very important that you understand that this is what is called "taste", and that it makes absolutely no difference in the runtimes. If you want to make changes like that, it would be cool to implement it yourself instead of asking me to do it for you.

I just did it, because I need the patch to get in quick.

• implement a doc test for
  • all your bad input/format tests

Done.

• memory test

I cannot test that.

• t>2 test

Done.

Nathann

[sagetrac-git]

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

411a759	trac #16286: Merged with updated #16277
11eff2c	trac #16235: Merged with 6.2
5a0e3fe	trac #16235: Merged with #16231
c0b13c4	trac #16235: Merged with updated #16286
9fb0f62	trac #16241: useless if condition in MOLS constructor
67ab2d2	trac #16241: Merged with updated #16235
2d7da8a	trac #16236: Merged with updated #16241
973b926	trac #16236: Merged with #16272
37681e2	trac #16295 : Faster is_orthogonal_array
839acc5	trac: Doctests and review

[sagetrac-git]

Changed commit from 0d5c222 to 839acc5

[sagetrac-git]

Changed commit from 839acc5 to 994324e

[sagetrac-git]

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

994324e

trac #16295: Doctests and review

[nathanncohen]

comment:13

Brett : the performance improvements are particularly nice for LARGE designs ! I implemented this because I wanted to check that we could indeed produce all the OA promised in our MOLS table, but some (in particularly prime powers, for k gets very large) took VERY long. With this, it is really faster and checking that the OA is an OA is not the bottleneck anymore when playing with designs.

Nathann

[nathanncohen]

comment:14

A bugfix. u=1 was disregarded by mistake in wilson_construction. Julian R. Abel spotted this from only looking at the MOLS table. That's scary O_O;;;;

Nathann

[sagetrac-git]

Changed commit from 994324e to b9f8b03

[sagetrac-git]

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

fc6de73	trac #16295: Merged with 6.3.beta1
b9f8b03	trac #16295: bugfix in wilson's construction

[brettpim]

comment:16

Vincent,

What does it mean that "any" is not properly cythonized. Does this just mean it is not efficient or does it mean there could be problems with future versions of cython?

brett

[brettpim]

comment:17

To look at the new code for this patch, I updated master and develop. Then I tried

git checkout u/ncohen/16295
git pull --ff-only trac u/ncohen/16295

and recieved

From trac.sagemath.org:sage
 * branch            u/ncohen/16295 -> FETCH_HEAD
fatal: Not possible to fast-forward, aborting.

how do I update this branch?

thanks
brett

[brettpim]

comment:18

As suggestedin the developers guide, I just ran

$git checkout master
Switched to branch 'master'
Your branch is ahead of 'origin/master' by 1992 commits.
$ git reset --hard trac/master
fatal: ambiguous argument 'trac/master': unknown revision or path not in the working tree.
Use '--' to separate paths from revisions

I am not sure what to do, the developers guide does not help here.

brett

[dimpase]

comment:19

Replying to @brettpim:

As suggestedin the developers guide, I just ran

$git checkout master

Why do you need this? This brings you to the stable Sage release (6.2).
Of course you are miles ahead of it, being around 6.3.beta1 or even later.

[dimpase]

comment:20

Replying to @brettpim:

To look at the new code for this patch, I updated master and develop. Then I tried

git checkout u/ncohen/16295
git pull --ff-only trac u/ncohen/16295

how about doing this without --ff-only ?

[brettpim]

comment:52

I just tried

$git trac push
git: 'trac' is not a git command. See 'git --help'.

but this did not work to push my revision up. What command do I use?

[nathanncohen]

comment:53

Hello !

but this did not work to push my revision up. What command do I use?

You seem to want to use "git trac" but it is not installed. This being said if you downloaded the branch without using "git trac" I don't think that just pushing is going to work.

What is the output of

git push trac HEAD:public/16295

It should push your current branch to public/16295.

Nathann

[brettpim]

comment:54

The Sage developers guide says "git trac puch" not "git push trac"

here is what I get when I do it the right way around:

$ git push trac
Counting objects: 13, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (7/7), done.
Writing objects: 100% (7/7), 937 bytes, done.
Total 7 (delta 6), reused 0 (delta 0)
remote: FATAL: W refs/heads/u/ncohen/16295 sage brett DENIED by fallthru
remote: error: hook declined to update refs/heads/u/ncohen/16295
To git@trac.sagemath.org:sage.git
 ! [remote rejected] u/ncohen/16295 -> u/ncohen/16295 (hook declined)
error: failed to push some refs to 'git@trac.sagemath.org:sage.git'

[nathanncohen]

comment:55

The Sage developers guide says "git trac puch" not "git push trac"

here is what I get when I do it the right way around:

Okay. So you noticed that the "right way" did not work. Can you try the "wrong way", i.e. the line I gave you above ? From the error message you got I think it will work.

The reason is simple : you cannot simply "push" to my branch because you have no write access to it. All branches whose name is u/my_login/whatever can only be written by guys whose login is my_login.

public/whatever branches can be written by anybody, though.

Nathann

[brettpim]

comment:56

your command worked but it creates a new branch and that is inoptimal

$ git push trac HEAD:public/16295
Counting objects: 13, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (7/7), done.
Writing objects: 100% (7/7), 937 bytes, done.
Total 7 (delta 6), reused 0 (delta 0)
To git@trac.sagemath.org:sage.git
 * [new branch]      HEAD -> public/16295

Does this get attached to the right ticket?

[nathanncohen]

comment:57

your command worked but it creates a new branch and that is inoptimal

Don't worry about branches, nobody has to pay for them. Anyway you cannot write on my branch (which is not my doing) so there is no other way.

Does this get attached to the right ticket?

It does not get attached to any ticket. You just added a branch on the trac server. Now I can look at it, we can discuss it, and if we agree with what is inside I will push it on the branch which is on this ticket. Or I will change this ticket's branch to public/16295 if it is easier.

Nathann

[dimpase]

comment:58

Replying to @brettpim:

your command worked but it creates a new branch and that is inoptimal

$ git push trac HEAD:public/16295
Counting objects: 13, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (7/7), done.
Writing objects: 100% (7/7), 937 bytes, done.
Total 7 (delta 6), reused 0 (delta 0)
To git@trac.sagemath.org:sage.git
 * [new branch]      HEAD -> public/16295

Does this get attached to the right ticket?

Why do you think this is not optimal? This is a normal way to go. Surely if there already was public/16295 branch you'd rather pushed there. But there was none. You can't push into someone else's branch. only into public/ ones.

[brettpim]

comment:59

Replying to @dimpase:

Why do you think this is not optimal? This is a normal way to go. Surely if there already was public/16295 branch you'd rather pushed there. But there was none. You can't push into someone else's branch. only into public/ ones.

I thought that that if there was a way for me to write to the patch's branch then having to create another is inoptimal, but if this is how it works then that is no problem.

[dimpase]

comment:60

Replying to @brettpim:

The Sage developers guide says "git trac puch" not "git push trac"

git trac means invoke git-trac git extension. (see http://github.com/sagemath/git-trac-command)

git push trac means do git's push to the remote named trac`.

(you can use git remote -v to see which remotes are set up for you)

here is what I get when I do it the right way around:

$ git push trac
Counting objects: 13, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (7/7), done.
Writing objects: 100% (7/7), 937 bytes, done.
Total 7 (delta 6), reused 0 (delta 0)
remote: FATAL: W refs/heads/u/ncohen/16295 sage brett DENIED by fallthru
remote: error: hook declined to update refs/heads/u/ncohen/16295
To git@trac.sagemath.org:sage.git
 ! [remote rejected] u/ncohen/16295 -> u/ncohen/16295 (hook declined)
error: failed to push some refs to 'git@trac.sagemath.org:sage.git'

surely, you can't push in an u/TRAC-USERNAME branch, that's why

[brettpim]

comment:61

Nathann,

I think if MOLS people are going to be using this code then we should add the additional 2 columns in when a MOLS gets transformed to a OA. In that case all the error messages I have changed are correct and this is what MOLS people will expect

[nathanncohen]

comment:62

Brett,

Here is the behaviour of your branch

sage: from sage.combinat.designs.latin_squares import are_mutually_orthogonal_latin_squares
sage: m1 = matrix([[0,1,0],[2,0,1],[1,2,0]]) # not a latin square
sage: m2 = matrix([[0,1,2],[1,2,0],[2,0,1]]) # not a latin square                                     
sage: are_mutually_orthogonal_latin_squares([m1,m2], verbose=True)                         
The row and column indices are not orthogonal
False
sage: m1 = matrix([[0,0,0],[1,1,1],[2,2,2]])  # not a latin square
sage: m2 = matrix([[0,1,2],[0,1,2],[0,1,2]])  # not a latin square
sage: are_mutually_orthogonal_latin_squares([m1,m2],verbose=True)
True
sage: a,b,c,d = designs.mutually_orthogonal_latin_squares(11,4)      
sage: are_mutually_orthogonal_latin_squares([a,b,c,d,d],verbose=True)
Squares 1 and 2 are not orthogonal
False

The index issues come from problem I mentionned in comment 51.

I think if MOLS people are going to be using this code then we should add the additional 2 columns in when a MOLS gets transformed to a OA. In that case all the error messages I have changed are correct and this is what MOLS people will expect

Here is what my branch u/ncohen/16295_v2 (mentionned in comment 50) does :

sage: from sage.combinat.designs.latin_squares import are_mutually_orthogonal_latin_squares
sage: m1 = matrix([[0,1,0],[2,0,1],[1,2,0]]) # not a latin square
sage: m2 = matrix([[0,1,2],[1,2,0],[2,0,1]]) # not a latin square
sage: are_mutually_orthogonal_latin_squares([m1,m2], verbose=True) 
Matrix 0 is not row latin
False
sage: m1 = matrix([[0,0,0],[1,1,1],[2,2,2]])  # not a latin square
sage: m2 = matrix([[0,1,2],[0,1,2],[0,1,2]])  # not a latin square
sage: are_mutually_orthogonal_latin_squares([m1,m2],verbose=True)
Matrix 0 is not row latin
False
sage: from sage.combinat.designs.latin_squares import are_mutually_orthogonal_latin_squares
sage: a,b,c,d = designs.mutually_orthogonal_latin_squares(11,4)
sage: are_mutually_orthogonal_latin_squares([a,b,c,d,d],verbose=True)
Matrices 3 and 4 are not orthogonal
False

Our terminology is almost the same (we can replace "matrix" with "square" if you prefer). The interest of mine is that you do not have to add MOLS-specific code to the is_orthogonal_array function. Thus do you mind if we keep my version of the code to make are_mutually_orthogonal_squares correct and include your typo fix ?

Nathann

[brettpim]

comment:63

Nathann,

I strongly feel that it would be much more consistent with

1. what people in design theory will expect the code to do

2. the equivalence between OAs and MOLS

to have are_mutually_orthogonal_squares add the two extra columns and then simply call is_orthogonal_array. This will have the effect of checking that all the squares are, in fact latin and you will not have to have are_mutually_orthogonal_squares do this extra checking.

in my opinion as a design theorist, the behaviour you cite in comment 62 of my code is all correct. In the second example the squares ARE orthogonal, they are just NOT latin. if you add the additional two columns the behaviour will be reported.

brett

[nathanncohen]

comment:64

Hello !

I strongly feel that it would be much more consistent with

1. what people in design theory will expect the code to do

You claim again that my code does something that somebody (a user ?) "in design theory" might not expect. Can you tell me what it is ? Or is the function okay for the user's point of view, while you think that the way it is coded is "something that people in design theory" would not expect ?

2. the equivalence between OAs and MOLS

to have are_mutually_orthogonal_squares add the two extra columns and then simply call is_orthogonal_array. This will have the effect of checking that all the squares are, in fact latin and you will not have to have are_mutually_orthogonal_squares do this extra checking.

I would have agreed if the function only returned True/False answer. What you are telling me to do is that I should consider all latins squares as k rows of a TD to which I add the two row/column ones, only to differentiate them later in a function that has no reason to contain MOLS-specific code.

This is why it does not make sense to me to build a homogeneous input only to dissassemble it immediately afterwards.

Besides, I expect that my commented code is sufficient for anybody "who does design theory" to understand what exactly happens.

in my opinion as a design theorist, the behaviour you cite in comment 62 of my code is all correct.

It is not. The function is named "are_mutually_orthogonal_latin_squares". It should return True if the input consists of mutually orthogonal latin squares.

In the second example the squares ARE orthogonal, they are just NOT latin. if you add the additional two columns the behaviour will be reported.

I agree with that, I am just showing that your branch returns wrong results. If this is fixed the results will be correct. This being said, if this is fixed then what you said just above, i.e. that the function should return True even when the input does not consist of latin squares, will not hold anymore. And so according to you the function will return wrong results.

Nathann

[nathanncohen]

comment:65

Two details that may help you decide :

1. The current behaviour of the are_mutually_orthogonal_latin_squares is to check that the latin squares are latin squares, and so changing that would mean changing the behaviour of the function

sage: from sage.combinat.designs.latin_squares import are_mutually_orthogonal_latin_squares
sage: are_mutually_orthogonal_latin_squares([Matrix([[1,1],[1,0]])])                       
False

2. All results returned by the constructors of mutually_orthogonal_latin_squares are checked using this function.. If it does not check whether the latin squares are orthogonal then we need to make sure that the output of our constructors are actually latin squares

Nathann

[nathanncohen]

comment:66

I updated my branch starting from u/ncohen/16295_v2 by adding your commit to it. I removed the "if" in is_orthogonal_array that only deal with MOLS input as this was already dealt with in are_mutually_orthogonal_latin_squares. This mixed version of our codes seems good to me...

Nathann

[sagetrac-git]

Changed commit from 31e84b8 to b66a187

[sagetrac-git]

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

6fb1f14	trac #16295: Bugfix
1653790	trac #16295: Merged with 6.3.beta3
b66a187	fixed some small language typos and changed MOLS error messages into context that MOLS researchers will expect.

[nathanncohen]

comment:68

Brett ?

[videlec]

comment:69

Hi Nathann,

We waited too long for that ticket and many tickets are depending on this one. For me the review is basically done as the function does what is specified.

I added one nice doctest at u/vdelecroix/16295... If you like it, set my branch to positive review otherwise set yours to positive review.

Vincent

[nathanncohen]

Changed commit from b66a187 to 02f1247

[nathanncohen]

comment:70

AHahahah. Funny doctest. I was actually thinking that "indeed, this function is used a LOT in the code, but that it is only tested on True instances. With your doctest, it makes it a bit more interesting than

def is_orthogonal_array(*args):
    return True

Thanks !

Nathann

---

New commits:

02f1247

trac #16295: one more doctest

[nathanncohen]

Changed branch from u/ncohen/16295 to u/vdelecroix/16295

[nathanncohen]

Reviewer: Vincent Delecroix, Brett Stevens

[brettpim]

comment:72

OK,

I am (mostly) happy. What do I do to approve this patch?

brett

[vbraun]

Changed branch from u/vdelecroix/16295 to 02f1247