Opened 7 years ago
Closed 7 years ago
#16295 closed enhancement (fixed)
Faster is_orthogonal_array
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  combinatorial designs  Keywords:  
Cc:  vdelecroix, knsam, dimpase  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Vincent Delecroix, Brett Stevens 
Report Upstream:  N/A  Work issues:  
Branch:  02f1247 (Commits, GitHub, GitLab)  Commit:  02f12476967dd287ffb47e711098a5518efbddd2 
Dependencies:  #16236  Stopgaps: 
Description
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
Change History (73)
comment:1 Changed 7 years ago by
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
 Branch set to u/ncohen/16295
 Commit set to 0d5c222cc78546cada8ae505197f429781b9595c
comment:3 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:4 followup: ↓ 5 Changed 7 years ago by
Nathann,
The code looks good and I have tested on an example different from your doc test.
The following run fine:
make, doctest, 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 doctest 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.
comment:5 in reply to: ↑ 4 Changed 7 years ago by
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 doctest 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
comment:6 followup: ↓ 7 Changed 7 years ago by
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
comment:7 in reply to: ↑ 6 Changed 7 years ago by
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
comment:8 followup: ↓ 10 Changed 7 years ago by
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
comment:9 Changed 7 years ago by
p.s. where is sage_free documented?
comment:10 in reply to: ↑ 8 Changed 7 years ago by
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
comment:11 Changed 7 years ago by
 Commit changed from 0d5c222cc78546cada8ae505197f429781b9595c to 839acc5a498c2fea319f92b477b1995f31d3bb9d
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

comment:12 Changed 7 years ago by
 Commit changed from 839acc5a498c2fea319f92b477b1995f31d3bb9d to 994324e77dbe8f3126aeba9059dc847feaebe8bc
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
994324e  trac #16295: Doctests and review

comment:13 Changed 7 years ago by
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
comment:14 Changed 7 years ago by
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
comment:15 Changed 7 years ago by
 Commit changed from 994324e77dbe8f3126aeba9059dc847feaebe8bc to b9f8b0388a8cd333bfaf4160896b09be5550896a
comment:16 Changed 7 years ago by
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
comment:17 followup: ↓ 20 Changed 7 years ago by
To look at the new code for this patch, I updated master and develop. Then I tried
git checkout u/ncohen/16295 git pull ffonly trac u/ncohen/16295
and recieved
From trac.sagemath.org:sage * branch u/ncohen/16295 > FETCH_HEAD fatal: Not possible to fastforward, aborting.
how do I update this branch?
thanks brett
comment:18 followup: ↓ 19 Changed 7 years ago by
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 help here.
brett
comment:19 in reply to: ↑ 18 ; followup: ↓ 21 Changed 7 years ago by
Replying to brett:
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.
comment:20 in reply to: ↑ 17 ; followup: ↓ 22 Changed 7 years ago by
Replying to brett:
To look at the new code for this patch, I updated master and develop. Then I tried
git checkout u/ncohen/16295 git pull ffonly trac u/ncohen/16295
how about doing this without ffonly
?
comment:21 in reply to: ↑ 19 ; followup: ↓ 23 Changed 7 years ago by
Replying to dimpase:
Replying to brett:
As suggestedin the developers guide, I just ran
$git checkout masterWhy 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.
I keep a current stable release branch for reference and stability if I need it. I think I have done something to it.
comment:22 in reply to: ↑ 20 ; followup: ↓ 24 Changed 7 years ago by
Replying to dimpase:
Replying to brett:
To look at the new code for this patch, I updated master and develop. Then I tried
git checkout u/ncohen/16295 git pull ffonly trac u/ncohen/16295how about doing this without
ffonly
?
Ok I tried
$ git checkout u/ncohen/16295 Switched to branch 'u/ncohen/16295' $ git pull trac u/ncohen/16295 From trac.sagemath.org:sage * branch u/ncohen/16295 > FETCH_HEAD Automerging src/sage/schemes/hyperelliptic_curves/monsky_washnitzer.py Automerging src/sage/combinat/designs/orthogonal_arrays.py CONFLICT (content): Merge conflict in src/sage/combinat/designs/orthogonal_arrays.py Automerging src/sage/combinat/designs/latin_squares.py Automerging src/sage/combinat/designs/designs_pyx.pyx CONFLICT (add/add): Merge conflict in src/sage/combinat/designs/designs_pyx.pyx Automerging src/sage/combinat/designs/block_design.py Automerging src/module_list.py Automatic merge failed; fix conflicts and then commit the result.
Have I somehow changed the files? I certainly did not intend to.
brett
comment:23 in reply to: ↑ 21 Changed 7 years ago by
Replying to brett:
as you see switching to the branch master
rather than already on branch master
, and you're ahead of master
by a zillion commits, you are most probably on
develop
, or on some other branch you got onto while reviewing a ticket.
comment:24 in reply to: ↑ 22 Changed 7 years ago by
Replying to brett:
Replying to dimpase:
Replying to brett:
To look at the new code for this patch, I updated master and develop. Then I tried
git checkout u/ncohen/16295 git pull ffonly trac u/ncohen/16295how about doing this without
ffonly
?Ok I tried
$ git checkout u/ncohen/16295 Switched to branch 'u/ncohen/16295' $ git pull trac u/ncohen/16295 From trac.sagemath.org:sage * branch u/ncohen/16295 > FETCH_HEAD Automerging src/sage/schemes/hyperelliptic_curves/monsky_washnitzer.py Automerging src/sage/combinat/designs/orthogonal_arrays.py CONFLICT (content): Merge conflict in src/sage/combinat/designs/orthogonal_arrays.py Automerging src/sage/combinat/designs/latin_squares.py Automerging src/sage/combinat/designs/designs_pyx.pyx CONFLICT (add/add): Merge conflict in src/sage/combinat/designs/designs_pyx.pyx Automerging src/sage/combinat/designs/block_design.py Automerging src/module_list.py Automatic merge failed; fix conflicts and then commit the result.Have I somehow changed the files? I certainly did not intend to.
are you updating from develop
? Or master
?
On the other hand I just tried git trac pull 12345
(I am using gittraccommand, which I would recommend!) it is worked.
Perhaps you should try checking out develop
and then trying again...
comment:25 Changed 7 years ago by
Guys guys, all this is happening because I rewrote history here. The only thing to do brett is to checkout my branch, or to checkout "develop" and then to pull my branch.
The copy of my branch that you have on your computer has been abandonned. If you do a checkout on it THEN pull my branch then you are trying to apply the same modifications twice, and it fails.
If you can delete the copy of my branch that you have on my computer, do it.
It is a bit hard to debug without having both hands on your keyboard, though :/
Nathann
comment:26 Changed 7 years ago by
Everything is good except I am still having trouble building the documentation
$sage docbuild reference html . . . c_functions writing output... [ 99%] tableaux writing output... [100%] words [combinat ] None:38: WARNING: citation not found: Schiffmann Error building the documentation. Traceback (most recent call last): File "/home/brett/Projects/SAGE/sage/src/doc/common/builder.py", line 1477, in <module> getattr(get_builder(name), type)() File "/home/brett/Projects/SAGE/sage/src/doc/common/builder.py", line 487, in _wrapper x.get(99999) File "/home/brett/Projects/SAGE/sage/local/lib/python/multiprocessing/pool.py", line 554, in get raise self._value OSError: [combinat ] None:38: WARNING: citation not found: Schiffmann
Do you get this error too Nathann?
comment:27 followup: ↓ 28 Changed 7 years ago by
Helloooooo Brett !!
No I don' get this error and apparently it does not come from the designs code but somewhere else.. I think you should run "make docclean && make" which will rebuild the doc. Takes some time, but not tooo long either. Sorry, I think you hit a lot of walls on this tickets ^^;
Nathann
comment:28 in reply to: ↑ 27 Changed 7 years ago by
Replying to ncohen:
Helloooooo Brett !!
No I don' get this error and apparently it does not come from the designs code but somewhere else.. I think you should run "make docclean && make" which will rebuild the doc. Takes some time, but not tooo long either. Sorry, I think you hit a lot of walls on this tickets
^^;
Nathann
It is not a problem. The coding part of this patch is clear and easy so this is a good ticket to hit the other kinds of problems that might show up when reviewing.
comment:29 Changed 7 years ago by
make docclean && make worked fine. Does this build both html and pdf documentation?
comment:30 Changed 7 years ago by
I think it only build the html one. "make docpdf" builds the pdf version :)
Nathann
comment:31 followup: ↓ 32 Changed 7 years ago by
# Filling times_n for i in range(n+1): times_n[i] = i*n
Ahem, you care for speed? ;)
(And there's no times_n2[]
either.)
comment:32 in reply to: ↑ 31 ; followup: ↓ 35 Changed 7 years ago by
Ahem, you care for speed? ;)
Yeah. And it turns out that I am totally incompetent.
When caching the multiplication
sage: OA=designs.orthogonal_array(None,2**7,check=False) sage: %timeit is_orthogonal_array(OA,2**7+1,2**7,2) 1 loops, best of 3: 618 ms per loop
When you don't
sage: OA=designs.orthogonal_array(None,2**7,check=False) sage: %timeit is_orthogonal_array(OA,2**7+1,2**7,2) 1 loops, best of 3: 375 ms per loop
.......................................................
(And there's no
times_n2[]
either.)
times_n2
? What for ?
Anyway, this caching was the only thing keeping me from implementing this for all t, so now I will be able to implement it generally now. Cool _
Nathann
comment:33 followup: ↓ 34 Changed 7 years ago by
Does this data show that it is faster to simply do the multiplications?
comment:34 in reply to: ↑ 33 Changed 7 years ago by
Replying to brett:
Does this data show that it is faster to simply do the multiplications?
In general depends on your CPU and your (C) compiler. (And in conjunction with Cython, the kind of code the latter generates, i.e., whether the C compiler can "guess" what's meant or whether the code is to obfuscated.)
comment:35 in reply to: ↑ 32 ; followup: ↓ 36 Changed 7 years ago by
Replying to ncohen:
times_n2
? What for ?
It's used twice, in the outer loop and the first inner loop:
for i in range(k): # For any column C1 C1 = OAc+i*n2 for j in range(i+1,k): # For any column C2 > C1 C2 = OAc+j*n2 ...
One would usually not look up multiples of n^2
(or n
in the earlier case), but do
C1 = OAc i = 0 while i < k: ... # similar for C2, j C1 += n2 i++
In C, you'd presumably drop j
(and perhaps also i
) altogether, and just compare the pointers to the address of the (current sub)array end.
(And inlining the bitset operations would of course make it even faster. Afterwards specialcase for n
=2^{m} ... :) )
comment:36 in reply to: ↑ 35 Changed 7 years ago by
It's used twice, in the outer loop and the first inner loop:
Come on... This is not the bottleneck :P
(And inlining the bitset operations would of course make it even faster. Afterwards specialcase for
n
=2^{m} ... :) )
They may be inlined already ! I didn't check though.
Anyway. Let's remove this useless caching, and then I will go sleep a bit. I couldn't do this earlier because my laptop is totally breaking and my screen refused to turn on T_T
Nathann
comment:37 Changed 7 years ago by
 Commit changed from b9f8b0388a8cd333bfaf4160896b09be5550896a to 2414b81b0ace07a1c0febb54dc86712b2cbafc73
Branch pushed to git repo; I updated commit sha1. New commits:
2414b81  trac #16295: Undoing useless """optimizations"""

comment:38 Changed 7 years ago by
 Component changed from combinatorics to combinatorial designs
comment:39 Changed 7 years ago by
Would anybody have some time for this ticket ? :P
Nathann
comment:40 followups: ↓ 41 ↓ 42 Changed 7 years ago by
Nathann
I am in Finland visiting a colleague. My plan is to produce a patch on top of this that implements Vincent's code for "any" and does some small work on English and once I commit it and if you are OK with my changes we can finish with this patch. I am sorry I am working in spurts on these sage patches, but I am trying to make the most of my time with my colleague here. It will be soon.
regards brett
comment:41 in reply to: ↑ 40 Changed 7 years ago by
Hello !
I am in Finland visiting a colleague.
Okayyyyyyyyy.... !
My plan is to produce a patch on top of this that implements Vincent's code for "any"
This is already done, I updated the code last time and there is no "any" anymore.
and does some small work on English
Okay.
and once I commit it and if you are OK with my changes we can finish with this patch. I am sorry I am working in spurts on these sage patches, but I am trying to make the most of my time with my colleague here. It will be soon.
Got it ! Have fun there.
Nathann
comment:42 in reply to: ↑ 40 Changed 7 years ago by
Replying to brett:
My plan is to produce a patch on top of this that [...] does some small work on English and once I commit it and if you are OK with my changes we can finish with this patch.
Yes, there are some typos, and the first sentence of the docstring refers to M
while the parameter's name is OA
.
comment:43 Changed 7 years ago by
 Commit changed from 2414b81b0ace07a1c0febb54dc86712b2cbafc73 to f1c7fa1da662e2ca6863ba5bc600fd15e1e3af26
Branch pushed to git repo; I updated commit sha1. New commits:
f1c7fa1  trac #16295: Typo

comment:44 Changed 7 years ago by
 Commit changed from f1c7fa1da662e2ca6863ba5bc600fd15e1e3af26 to 31e84b82913815b2005b5e2e45650c1568a45761
comment:45 Changed 7 years ago by
Okay guys... Well it has been two weeks, so if the only problem of this patch is a typo perhaps it can be dealt with ?... There are several branches depending on this one...
Nathann
comment:46 Changed 7 years ago by
I am just back from Scandinavia. I will do this today.
brett
comment:47 followup: ↓ 48 Changed 7 years ago by
I have made almost all the changes. In the code line
if verbose: print {"OA" : "Columns {} and {} are not orthogonal".format(i,j), "MOLS" : "Matrices {} and {} are not orthogonal".format(i,j)}[terminology] return False
Is there a compact way of switching depending on the values of i and j in the case that terminology=MOLS? if i = 0 and j>1 then "square j2" is not row latin. if i=1 and J> 1 then square j2 is not column latin" if both i,j >2 then "square i2 is not orthogonal to square j2"
if i=0 and j=1 I have not found the right way to word the error message yet. Perhaps something like "the row and column indices are not orthogonal"
brett
comment:48 in reply to: ↑ 47 Changed 7 years ago by
Hello !
Replying to brett:
I have made almost all the changes. In the code line
if verbose: print {"OA" : "Columns {} and {} are not orthogonal".format(i,j), "MOLS" : "Matrices {} and {} are not orthogonal".format(i,j)}[terminology] return FalseIs there a compact way of switching depending on the values of i and j in the case that terminology=MOLS? if i = 0 and j>1 then "square j2" is not row latin. if i=1 and J> 1 then square j2 is not column latin" if both i,j >2 then "square i2 is not orthogonal to square j2"
This block of code is not about each matrix being a latin square. Actually, this is not checked anywhere so I will add a commit.
This block of code is about the orthogonality of two matrices, i.e. do you find all possible pairs of integers when you read them simultaneously cell by cell.
Nathann
comment:49 followups: ↓ 50 ↓ 51 Changed 7 years ago by
Nathann,
I understand what the code is doing. When I say "square" I mean "latin square" and in the language of MOLS column 0 of an OA is the row index of the Squares, column 1 is the column index and column i is latin square i2. I am just making the error reporting consistent with the way that a MOLS person would interpret it. Please do not change the branch yet as I am in the middle of editing the code. I was just curious if there was a compact way to use a more complex case/switch in cython. But I think there is not so I will just make the changes with nested if statements.
brett
comment:50 in reply to: ↑ 49 Changed 7 years ago by
Still, it must be checked that each matrix is a latin square, because right now we have this :
sage: from sage.combinat.designs.latin_squares import are_mutually_orthogonal_latin_squares sage: m1 = matrix([[0,0,0],[1,1,1],[2,2,2]]) sage: m2 = matrix([[0,1,2],[0,1,2],[0,1,2]]) sage: are_mutually_orthogonal_latin_squares([m1,m2], verbose=True) True
I added a commit on u/ncohen/16295_v2 to fix that. Do not worry about possible conflicts with what you are doing : when you will be done, push your commit wherever you want on a branch of yours, give me its name and I will deal with the merge.
Nathann
comment:51 in reply to: ↑ 49 ; followup: ↓ 52 Changed 7 years ago by
Hello,
I understand what the code is doing. When I say "square" I mean "latin square" and in the language of MOLS column 0 of an OA is the row index of the Squares, column 1 is the column index and column i is latin square i2.
Right now when are_mutually_latin_squares
calls is_orthogonal_array
it does not check that the resulting OA is a OA(k+2,n)
but only that it is a OA(k,n)
. This, because the OA that is produced has only k columns and not k+2. This, because the columns corresponding to the row indices and the columns indices are not added to the OA.
This way, when the sequence of matrices is not a MOLS, the error message is that "matrix i is not orthogonal with matrix j" or that "matrix i is not a latin squares".
Which is, I believe, clearer to the user and easier to implement than by messing with the error messages of is_orthogonal_design
.
Nathann
comment:52 in reply to: ↑ 51 ; followup: ↓ 53 Changed 7 years ago by
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?
comment:53 in reply to: ↑ 52 Changed 7 years ago by
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
comment:54 followups: ↓ 55 ↓ 60 Changed 7 years ago by
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'
comment:55 in reply to: ↑ 54 Changed 7 years ago by
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
comment:56 followups: ↓ 57 ↓ 58 Changed 7 years ago by
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?
comment:57 in reply to: ↑ 56 Changed 7 years ago by
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
comment:58 in reply to: ↑ 56 ; followup: ↓ 59 Changed 7 years ago by
Replying to brett:
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/16295Does 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.
comment:59 in reply to: ↑ 58 Changed 7 years ago by
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.
comment:60 in reply to: ↑ 54 Changed 7 years ago by
Replying to brett:
The Sage developers guide says "git trac puch" not "git push trac"
git trac
means invoke gittrac git extension
. (see http://github.com/sagemath/gittraccommand)
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/TRACUSERNAME branch, that's why
comment:61 followup: ↓ 62 Changed 7 years ago by
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
comment:62 in reply to: ↑ 61 ; followup: ↓ 63 Changed 7 years ago by
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 MOLSspecific 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
comment:63 in reply to: ↑ 62 ; followup: ↓ 64 Changed 7 years ago by
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
comment:64 in reply to: ↑ 63 Changed 7 years ago by
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 callis_orthogonal_array
. This will have the effect of checking that all the squares are, in fact latin and you will not have to haveare_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 MOLSspecific 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
comment:65 Changed 7 years ago by
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
comment:66 Changed 7 years ago by
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
comment:67 Changed 7 years ago by
 Commit changed from 31e84b82913815b2005b5e2e45650c1568a45761 to b66a187a35ff81525f42ddf4d93611ec2bd9fb6b
comment:68 Changed 7 years ago by
Brett ?
comment:69 Changed 7 years ago by
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
comment:70 Changed 7 years ago by
 Branch changed from u/ncohen/16295 to u/vdelecroix/16295
 Commit changed from b66a187a35ff81525f42ddf4d93611ec2bd9fb6b to 02f12476967dd287ffb47e711098a5518efbddd2
 Status changed from needs_review to positive_review
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

comment:71 Changed 7 years ago by
 Reviewers set to Vincent Delecroix, Brett Stevens
comment:72 Changed 7 years ago by
OK,
I am (mostly) happy. What do I do to approve this patch?
brett
comment:73 Changed 7 years ago by
 Branch changed from u/vdelecroix/16295 to 02f12476967dd287ffb47e711098a5518efbddd2
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
trac #16235: update the MOLS table
trac #16241: New MOLS shared by Ian Wanless
trac #16241: missing links and tests
trac #16241: Broken doctests
trac #16241: Merged with updated #16235
trac #16241: Broken doctests
trac #16236: Five mutually orthogonal latin squares of order 12
trac #16236: Merged with updated #16241
trac #16236: Broken doctests
trac #16295 : Faster is_orthogonal_array