Opened 5 years ago

Closed 5 years ago

#16391 closed enhancement (fixed)

Helper functions for OA constructions

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorial designs Keywords:
Cc: vdelecroix, knsam, brett Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 70c9805 (Commits) Commit: 70c98058b2414e3fc873a8825c1db293da0709e3
Dependencies: #16460 Stopgaps:

Description

This adds two helper functions that are heavily used by all the OA construction routines that I currently implement. Aaaaaaand which will be in Sage asap !

Nathann

Attachments (1)

is_incomplete_orthogonal_array.py (3.5 KB) - added by vdelecroix 5 years ago.
an implementation of is_incomplete_orthogonal_array

Download all attachments as: .zip

Change History (53)

comment:1 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/16391
  • Cc vdelecroix knsam brett added; vdele removed
  • Commit set to 395458fdb6487289f5add7702c7c6fe66018ad96
  • Status changed from new to needs_review

New commits:

90a72bdtrac #16370: OA(k,n) strongly regular graphs
395458ftrac #16391: Helper functions for OA constructions

comment:2 Changed 5 years ago by git

  • Commit changed from 395458fdb6487289f5add7702c7c6fe66018ad96 to f86d187a1fdd25bb662663de314fd1528e675fc0

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

0ed318etrac #16391: Merged with 6.3.beta2
f86d187trac #16391: small improvement

comment:3 Changed 5 years ago by ncohen

Small update to find an "independent set of order x" with a Linear Program.

  • Calling Graph.independent_set() would work but the function could take forever trying to decide if there exists an independent set of order 14 or 15 when we only need 2.
  • Calling subgraph_search as was done just before this commit is a bad algorithm when there are no solutions. A VERY bad algorithm :-P

Nathann

comment:4 Changed 5 years ago by git

  • Commit changed from f86d187a1fdd25bb662663de314fd1528e675fc0 to d954b936c11f31d79b5dca0d6b8da579afb53d5f

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

d954b93trac #16391: Independent Set problem with a LP

comment:5 Changed 5 years ago by git

  • Commit changed from d954b936c11f31d79b5dca0d6b8da579afb53d5f to 2090875de8a5d9a0301a85fc35e0e60a068de1ab

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

2090875trac #16391: Small improvement

comment:6 follow-up: Changed 5 years ago by vdelecroix

Hi Nathann,

I switch to this one from #16361 because of the comment I wrote there. But in the function OA_with_holes implemented in the branch associated to that ticket, you do strictly the same thing. You rely heavily on the output of designs.orthogonal_array(k,n) whose specifications are : "Returns an orthogonal array with parameters (k,n)". It is neither intended to be constant over time (and you do not want to impose that) and it is not optimized with respect to any property. One reason is that we want to shortcut as possible the recursive constructions which are time consuming. If someone comes with a nice one parameter family of OA(k, k^2 + 3*k + 19) we would use that first whatever it breaks elsewhere.

You can not reasonably force the implementation of designs.orthogonal_array to output something optimal with respect to the property you are interested in today. It might really be that tomorrow, you would prefer to have a designs.orthogonal_array with very few multiplicity of TD(k,1) in it.

Right now, we have several constructions of OA with the same parameters (for example, several Wilson construction might be available). The multiplicity of TD(k,1) you obtain must strongly depend on the way you did your construction and we do not want that designs.orthogonal_array takes this strategy.

Vincent

comment:7 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_info

comment:8 in reply to: ↑ 6 ; follow-up: Changed 5 years ago by ncohen

Yo Vincent !

I cannot claim that OA_with_holes will always output "optimal results", and I never did.

I need those designs for constructions of OA that we cannot build at the moment, and I have no other way to produce them. What is the problem with seeing this function as

1) When k<=3 we know that it exists 2) When there is a OA(k+1,n) we know that it exists 3) If everything else fails, see if you are lucky

And you want me to remove feature 3), even though it does return helpful things. I never claimed that the results would not change, and what I know for sure is that the results WILL improve as we add new OA. It is true, I cannot prove that eventually feature 3) will never become less powerful.

And so what ? Do I throw all my useful code away because of that ? I really have no other way to generate these designs.

The multiplicity of TD(k,1) you obtain must strongly depend on the way you did your construction

We have no proof of that. And I did not claim the contrary, but we have no proof of that. For instance the proof that it always exists when k<=3 is the proof that any OA contains an independent set of size 3, which means that the result will always hold in this case regardless of which OA is returned.

Nathann

Version 1, edited 5 years ago by ncohen (previous) (next) (diff)

comment:9 Changed 5 years ago by ncohen

  • Status changed from needs_info to needs_review

(by the way, the "independent set" problem makes it independent from the actual labelling of the OA. Even though, of course, it says nothing about non-isomorphic OA)

comment:10 in reply to: ↑ 8 ; follow-up: Changed 5 years ago by vdelecroix

Hi Nathann,

Thanks for your clarification.

Replying to ncohen:

I cannot claim that OA_with_holes will always output "optimal results", and I never did.

I need those designs for constructions of OA that we cannot build at the moment, and I have no other way to produce them. What is the problem with seeing this function as

1) When k<=3 we know that it exists 2) When there is a OA(k+1,n) we know that it exists 3) If everything else fails, see if you are lucky

And you want me to remove feature 3), even though it does return helpful things. I never claimed that the results would not change, and what I know for sure is that the results WILL improve as we add new OA. It is true, I cannot prove that eventually feature 3) will never become less powerful.

I do not want you to remove it but I do not want to see code or doctests that depend on the lucky case 3). Which implies that you should not use k > 3 anywhere. In the current ticket this function is not used at all, so... Where this code is merged with #16391?

The multiplicity of TD(k,1) you obtain must strongly depend on the way you did your construction

We have no proof of that. And I did not claim the contrary, but we have no proof of that. For instance the proof that it always exists when k<=3 is the proof that any OA contains an independent set of size 3, which means that the result will always hold in this case regardless of which OA is returned.

Is there a way to find the largest set of disjoint blocks?

Vincent

comment:11 in reply to: ↑ 10 Changed 5 years ago by ncohen

Yo !

I do not want you to remove it but I do not want to see code or doctests that depend on the lucky case 3). Which implies that you should not use k > 3 anywhere.

....

So I can implement it but I am forbidden to use it ?...

Look at what you are doing : you are telling me that it is very bad that in the future some OA with holes may not exist anymore, for the very same reason that in the future some OA with holes may become available.

Because we may change constructions, and because if a change can occur in one direction it can occur in the other direction too.

So the problem is that the "performance may change" in the future, and in both directions. And more importanty that a doctest may be broken because somebody ADDS a construction of an OA we were already able to build, which should not have any effect...

Look man, I have no way around that. I am quite ready to accept that adding a construction may destroy another whose existence could not be proved formally, because this thing is useful for a lot of stuff.

And that, again, I have no way around.

And that it only returns true results anyway.

It is a heuristic. It returns true things, but it may not always find them.

In the current ticket this function is not used at all, so... Where this code is merged with #16391?

#16391 is the ticket on which we are talking, so I guess you talk about #16361. And the ticket which makes #16361 use this helper function is Wilson's construction #16347. I gave you the updated version of that code in my last comment on #16361.

Is there a way to find the largest set of disjoint blocks?

Well, this is precisely what this function does. It solves a maximum independent set problem on the intersection graph. On a specific OA of course.

If you want to know if theory knows what the largest set of disjoint blocks for any k,n I expect that the answer is no. If there exists an OA(k+1,n) there there exists an OA(k,n)-n.OA(k,1) but it is apparently not an equivalence.

Nathann

comment:12 Changed 5 years ago by git

  • Commit changed from 2090875de8a5d9a0301a85fc35e0e60a068de1ab to 90f828fb2904fc5083baa8b45af97d6dc7740f54

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

74c30a6trac #16370: Merged with 6.3.beta2
e3c1c21trac #16370: Parameters of the SRG in the doc
e469bb5trac #16370: Warnings in the constructor
1a3255ctrac #16370: Merged with 6.3.beta3
7b73bc5trac #16370: Reviewer's comments
d1e272ftrac #16370: Reviewer's comments 2
bdae80atrac #16370: more docs
406aaeftrac #16391: Merged with updated #16370
90f828ftrac #16391: use OrthogonalArrayBlockGraph instead of OrthogonalArrayGraph

comment:13 follow-up: Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_info

Hi,

1) What you called OA with holes are "incomplete orthogonal array" in the Handbook (as well as their sisters "incomplete transversal design" and "incomplete set of MOLS"). See p 193-194. And the one you are interested in, the "OA(k,n) - x.OA(k,1)", are also denoted "OA(k,n; 1, ..., 1)". Am I right? If this is true, I would rather write a function incomplete_orthogonal_array(k,n,holes) where holes is a tuple of integers to fit with the standard names and notations. I also saw some general results in the Handbook (Theorems 4.16 and 4.17) about one hole and k=4,5... and a beautiful table of IMOLS.

2) From the function you wrote, it is very easy to

  • allow x as None, in which case the function tries to optimize the number of holes
  • have an optional argument OA such that, if it is provided, the function looks for holes inside this orthogonal array.

I did the change myself but the function looks a bit uglier so I am not sure what to do. I would like to have those two functions to study the number of holes depending on the OA. But on the other hand, I tried with the OA(4,10) that we have but it took lifetime to obtain the answer 9.

A perhaps cleaner way to do things is to have two functions that would looks like

  • incomplete_orthogonal_array(k,n,holes) (this function would be available from the global namespace)
  • look_for_holes_in_my_OA(OA,k,n,holes)

What do you think?

Vincent

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:14 in reply to: ↑ 13 ; follow-up: Changed 5 years ago by ncohen

  • Status changed from needs_info to needs_review

Yo !

1) What you called OA with holes are "incomplete orthogonal array" in the Handbook

I see I see. Somehow I think that I was mixing together "incomplete TD" and "truncated TD". For me an "incomplete TD" could be an OA truncated in any way, though it seems that it actually is a "nicely truncated TD", i.e. that the missing stuff can potentially be filled with others TD.

Note that I have no clue how I could compute a decomposition of a TD with holes of size > 1. No idea.

(as well as their sisters "incomplete transversal design" and "incomplete set of MOLS"). See p 193-194. And the one you are interested in, the "OA(k,n) - x.OA(k,1)", are also denoted "OA(k,n; 1, ..., 1)". Am I right? If this is true, I would rather write a function incomplete_orthogonal_array(k,n,holes) where holes is a tuple of integers to fit with the standard names and notations. I also saw some general results in the Handbook (Theorems 4.16 and 4.17) about one hole and k=4,5... and a beautiful table of IMOLS.

Okay, then we can implement it like that : incomplete_transversal_design(k,n,tuple_of_hole_sizes,OA=None).

The function would return an exception whenever there is an element in tuple_of_hole_sizes which is not equal to 1, and if OA is defined then it is the OA that will be used to compute the holes ?

2) From the function you wrote, it is very easy to

  • allow x as None, in which case the function tries to optimize the number of holes

Holes of size 1.

  • have an optional argument OA such that, if it is provided, the function looks for holes inside this orthogonal array.

Yepyep.

I did the change myself but the function looks a bit uglier so I am not sure what to do. I would like to have those two functions to study the number of holes depending on the OA. But on the other hand, I tried with the OA(4,10) that we have but it took lifetime to obtain the answer 9.

Yep. I tried different things an really this small LP appears to be the best choice. If we make the optimization available then we will have to call Graph.independent_set.

A perhaps cleaner way to do things is to have two functions that would looks like

  • incomplete_orthogonal_array(k,n,holes) (this function would be available from the global namespace)

Yepyep, this could be designs.incomplete_orthogonal_array

  • look_for_holes_in_my_OA(OA,k,n,holes)

I would not know where to write that. It does not belong to designs.<tab>. We could write it somewhere in the orthogonal_array file, to let it be exposed later when all this will have become a class.

What do you think?

What do you think ? Answer my questions above and I will write the code. And rebase what needs to be, above.

Nathann

comment:15 in reply to: ↑ 14 Changed 5 years ago by vdelecroix

Hello,

Replying to ncohen:

Yo !

1) What you called OA with holes are "incomplete orthogonal array" in the Handbook

I see I see. Somehow I think that I was mixing together "incomplete TD" and "truncated TD". For me an "incomplete TD" could be an OA truncated in any way, though it seems that it actually is a "nicely truncated TD", i.e. that the missing stuff can potentially be filled with others TD.

Note that I have no clue how I could compute a decomposition of a TD with holes of size > 1. No idea.

For now, we do not care. But there are examples and references in the Handbook.

Okay, then we can implement it like that : incomplete_transversal_design(k,n,tuple_of_hole_sizes,OA=None).

The function would return an exception whenever there is an element in tuple_of_hole_sizes which is not equal to 1, and if OA is defined then it is the OA that will be used to compute the holes ?

Perfect. It is a bit dummy but it is more terminology compliant and lets the door open.

2) From the function you wrote, it is very easy to

  • allow x as None, in which case the function tries to optimize the number of holes

Holes of size 1.

yes. my mistake.

  • have an optional argument OA such that, if it is provided, the function looks for holes inside this orthogonal array.

Yepyep.

I did the change myself but the function looks a bit uglier so I am not sure what to do. I would like to have those two functions to study the number of holes depending on the OA. But on the other hand, I tried with the OA(4,10) that we have but it took lifetime to obtain the answer 9.

Yep. I tried different things and really this small LP appears to be the best choice. If we make the optimization available then we will have to call Graph.independent_set.

With the OA(4,10) that has 100 blocks, what would be the best strategy? It took me more than a minute with the MILP (using either glpk or cbc).

A perhaps cleaner way to do things is to have two functions that would looks like

  • incomplete_orthogonal_array(k,n,holes) (this function would be available from the global namespace)

Yepyep, this could be designs.incomplete_orthogonal_array

Great!

  • look_for_holes_in_my_OA(OA,k,n,holes)

I would not know where to write that. It does not belong to designs.<tab>. We could write it somewhere in the orthogonal_array file, to let it be exposed later when all this will have become a class.

This is what I meant, not a public function. You can call it whatever you want. But I really would like that it accepts an optional OA as argument in the very same way graphs.OrthogonalArrayBlockGraph does. Perhaps a more appropriate name would be, OA_find_disjoint_block?

Vincent

comment:16 Changed 5 years ago by vdelecroix

Sorry, I meant

  • designs.incomplete_transversal_design(k,n,holes) <--- no OA argument here
  • a private OA_find_disjoint_blocks(k,n,x,OA=None)

And of course you can use caching on the first one.

Vincent

comment:17 Changed 5 years ago by ncohen

Hello !

Here is the updated code.

As it is the feature "give me the maximum number of disjoint blocks" is not available, but it can be easily added later. This being said if we do that perhaps the best algorithm to use is not the LP solver but rather graphs.OrthogonalArrayBlockGraph(k,n).independent_set(algorithm=something). And it seems that the best something, even though it is an optional package at the moment, may be MCQD #16083.

Ready for review again !

Nathann

comment:18 Changed 5 years ago by git

  • Commit changed from 90f828fb2904fc5083baa8b45af97d6dc7740f54 to 6e3c6856da596aa0b05c82c2f3cbcf48dbd3812a

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

6e3c685trac #16391: reviewer's comments

comment:19 Changed 5 years ago by vdelecroix

Hi,

Great. But you did not remove the holes! An IOA(k,n; h_1, ..., h_s) must have n^2 - sum(h_i^2) blocks. Would that be hard to adapt?

I wrote a function is_incomplete_orthogonal_array but I do not want interferences with #16295. I will attach the file to the ticket.

Vincent

Changed 5 years ago by vdelecroix

an implementation of is_incomplete_orthogonal_array

comment:20 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_info

comment:21 Changed 5 years ago by git

  • Commit changed from 6e3c6856da596aa0b05c82c2f3cbcf48dbd3812a to 52c2de8586d29cbe302bb9a451589ca5d8eeadd5

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

52c2de8trac #16391: Removing the holes

comment:22 Changed 5 years ago by ncohen

Back to needs_review !

Nathann

comment:23 Changed 5 years ago by ncohen

  • Status changed from needs_info to needs_review

comment:24 follow-up: Changed 5 years ago by vdelecroix

Ouch. I had a commit for that...

  • why are you using tuples instead of lists?
  • there is a problem for holes_sizes=(1,)

You can look at what I did at u/vdelecroix/16391

Vincent

comment:25 in reply to: ↑ 24 ; follow-up: Changed 5 years ago by ncohen

Yo !

  • why are you using tuples instead of lists?

What do you mean ? For the caching ? If so, that's because you get an exception when a @cached_method gets a non-hashable input.

  • there is a problem for holes_sizes=(1,)

O_o

Funny. I fixed it, but I am pretty sure I had fixed it before in the very same way/trick. Weird O_o

Nathann

comment:26 Changed 5 years ago by git

  • Commit changed from 52c2de8586d29cbe302bb9a451589ca5d8eeadd5 to d0885f7944ac0cb5f5ddb6822544f9059596ba67

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

d0885f7trac #16391: bugfix

comment:27 Changed 5 years ago by ncohen

Oh. I had fixed it in "trac #16347: Genelarized Wilson construction" :-P

Nathann

comment:28 in reply to: ↑ 25 Changed 5 years ago by vdelecroix

Replying to ncohen:

Yo !

  • why are you using tuples instead of lists?

What do you mean ? For the caching ? If so, that's because you get an exception when a @cached_method gets a non-hashable input.

I mean for the output!

comment:29 Changed 5 years ago by ncohen

Oh. I see. Then, that's because if you cache the output of a function and that this output is mutable, there is no certainty that users will not change the content of the cache by modifying the result returned by the function.

That's why I was forced to convert to "tuple" the output of orthogonal_array in #16347, which I totally hate. But I will rewrite this to only cache the boolean values, I will implement this manually as soon as all the dependencies are reviewed.

That's also why it is painful to not be able to cache only what you want.

Nathann

comment:30 Changed 5 years ago by ncohen

sage: @cached_function
....: def a():
....:     return []
....: 
sage: a()
[]
sage: x=a()
sage: x.append(8)
sage: a()
[8]

comment:31 follow-up: Changed 5 years ago by vdelecroix

Hi,

Some small changes in u/vdelecroix/16391 (above your last commit). The modification of the NOTE is the most important one (it was wrong before).

I really do not like the fact that designs.orthogonal_array return list of lists while designs.incomplete_orthogonal_array returns tuple of tuples. Can we make all tuple of tuples (at least in a later ticket)?

Beyond that, I am happy with the ticket.

Vincent

PS: the search of disjoint blocks for the OA(4,10) is much faster using increasing values of x instead of a set_objective...

comment:32 in reply to: ↑ 31 Changed 5 years ago by ncohen

Yo !

Some small changes in u/vdelecroix/16391 (above your last commit). The modification of the NOTE is the most important one (it was wrong before).

Was it ? I thought that your version was wrong too, so I added a commit. What do you think ?

I really do not like the fact that designs.orthogonal_array return list of lists while designs.incomplete_orthogonal_array returns tuple of tuples. Can we make all tuple of tuples (at least in a later ticket)?

I do not want any of them to be tuples. I have no other choice but to make them tuples because nobody is willing to review #16353 which would let me cache only boolean answers (meaning that the constructors could all return lists of lists as it would be best).

If #16353 is not reviewed I will have no other choice but to implement a chaching method for all three constructors (with a common cache) for booleans answers, and of course yet another one for this function.

Which is a sheer waste of time.

Beyond that, I am happy with the ticket.

Tell me if you are okay with this additional commit !

PS: the search of disjoint blocks for the OA(4,10) is much faster using increasing values of x instead of a set_objective...

That's because when you give it the number of disjoint blocks it does not have to prove that you cannot find a strictly larger set of blocks by itself. If k is the largest amount of disjoint blocks in a OA(4,10) try with value k+1. Should take the same time.

Nathann

comment:33 Changed 5 years ago by git

  • Commit changed from d0885f7944ac0cb5f5ddb6822544f9059596ba67 to 41a9a247df5925a7067421a03093b0bc01155671

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

c1de597trac #16391: doc clean + remove some list construction
41a9a24trac #16391: Typo

comment:34 follow-up: Changed 5 years ago by vdelecroix

Hi Nathann,

I do not agree with your corrections. By definition, the holes are subsets of the ground set V = {0,...,n-1}. Perhaps it depend on where we read the definition.

Could we just get rid of the caching and return list of lists in the very same way as orthogonal_array? The time needed to find 3 disjoint blocks is not big compared to the time you need to build an orthogonal array. It would make more sense to implement the caching at the level of orthogonal_array. And I think, it would better if done in another ticket.

Vincent

comment:35 in reply to: ↑ 34 ; follow-up: Changed 5 years ago by ncohen

Yo !

I do not agree with your corrections. By definition, the holes are subsets of the ground set V = {0,...,n-1}. Perhaps it depend on where we read the definition.

Well, I did not find definition of incomplete OA in the handbook though they define incomplete transversal designs, and for this they introduce sets H_1,H_2, .... Well, to define a hole in general you need to give a subset for each column... Your phrasing assumes that the OA has been relabelled so that the coordinates of the hole are the same in every column... But honestly everybody would understand it the way it is, adding this ^k just emphasizes that we give the coordinate for every column.

Could we just get rid of the caching and return list of lists in the very same way as orthogonal_array?

Don't you want to review #16353 ? This would make everything MUCH easier.

I am willing to implement this correctly and -- if posible -- uniformly, but if people refuse to review stuff like #16353 for theological reasons then I am stuck, and I have no other way but to find workarounds.

In the constructions I will add when all this will be reviewed this function is called often. You can see that it will be called by the new version of Wilson's theorem, because holes are realy needed there. And it will be good to have it cached.

The time needed to find 3 disjoint blocks is not big compared to the time you need to build an orthogonal array. It would make more sense to implement the caching at the level of orthogonal_array. And I think, it would better if done in another ticket.

Come on man. All the boolean answers should be cached. It costs nothing, and it can only help.

Nathann

comment:36 Changed 5 years ago by git

  • Commit changed from 41a9a247df5925a7067421a03093b0bc01155671 to 42239ccc8b169e1aaf148da90b638004a09e67c6

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

42239cctrac #16391: Undoing stuff

comment:37 Changed 5 years ago by ncohen

Here it is. Note that Wilson's decomposition as it is implemented in #16347 was making orthogonal_array return tuples too.

And I will still need #16353 to update this properly. It is better to output lists than tuples, but if we cannot cache resuls we cannot even build the MOLS table once that #16347 will be implemented --> too slow.

Nathann

comment:38 in reply to: ↑ 35 ; follow-up: Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Replying to ncohen:

Yo !

I do not agree with your corrections. By definition, the holes are subsets of the ground set V = {0,...,n-1}. Perhaps it depend on where we read the definition.

Well, I did not find definition of incomplete OA in the handbook though they define incomplete transversal designs, and for this they introduce sets H_1,H_2, .... Well, to define a hole in general you need to give a subset for each column... Your phrasing assumes that the OA has been relabelled so that the coordinates of the hole are the same in every column... But honestly everybody would understand it the way it is, adding this ^k just emphasizes that we give the coordinate for every column.

I had a look at various papers and they define holes as subset of V. But I agree, it is fine the way you did.

Could we just get rid of the caching and return list of lists in the very same way as orthogonal_array?

Don't you want to review #16353 ? This would make everything MUCH easier.

I can review it, but I do not want to see it used in designs!

I am willing to implement this correctly and -- if posible -- uniformly, but if people refuse to review stuff like #16353 for theological reasons then I am stuck, and I have no other way but to find workarounds.

In the constructions I will add when all this will be reviewed this function is called often. You can see that it will be called by the new version of Wilson's theorem, because holes are really needed there. And it will be good to have it cached.

All right. Then I will changed my mind at this point.

The time needed to find 3 disjoint blocks is not big compared to the time you need to build an orthogonal array. It would make more sense to implement the caching at the level of orthogonal_array. And I think, it would better if done in another ticket.

Come on man. All the boolean answers should be cached. It costs nothing, and it can only help.

No. We should cache a dictionnary n -> (k_exists,k_unknown). This would be more efficient. Sometimes you have a TD(k+5,n) but was looking for a TD(k,n), so you loose information. Similarly, if you start caching (incomplete) orthogonal array you would only cache the one which has the maximum number of holes with respect to a fixed k or the on which has the maximum size with respect to a fixed set of holes.

Vincent

comment:39 in reply to: ↑ 38 ; follow-up: Changed 5 years ago by ncohen

Yo !

I had a look at various papers and they define holes as subset of V. But I agree, it is fine the way you did.

Thanks.

I can review it, but I do not want to see it used in designs!

....

It's cool to say "I do not want to see it used in design" but I am still the one who writes the code. Having this generic cache would make stuff better. And you can't really refuse an improvement because "there would be a better way to implement it" that you expect me to implement instead.

Pfffff...

Spoiled reviewers...

No. We should cache a dictionnary n -> (k_exists,k_unknown). This would be more efficient. Sometimes you have a TD(k+5,n) but was looking for a TD(k,n), so you loose information. Similarly, if you start caching (incomplete) orthogonal array you would only cache the one which has the maximum number of holes with respect to a fixed k or the on which has the maximum size with respect to a fixed set of holes.

I know, I told you about it myself.

...

I will do it.

It just takes time, and I have been stuck for 5 weeks with a straightforward code that does not get reviewed, and I can't add patch over patch over patch forever, knowing that names and specifications will change in the dependencies. It would have been done already otherwise.

Nathann

comment:40 follow-up: Changed 5 years ago by ncohen

Could you add your name as a reviewer ?

Nathann

comment:41 in reply to: ↑ 40 Changed 5 years ago by vdelecroix

Replying to ncohen:

Could you add your name as a reviewer ?

Ha! I always forgot that.

comment:42 Changed 5 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix

comment:43 in reply to: ↑ 39 Changed 5 years ago by ncohen

I will do it.

#16353

Nathann

comment:44 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work
LaTeX Warning: Hyper reference `sage/combinat/designs/orthogonal_arrays:sage.co
mbinat.designs.orthogonal_arrays.wilson_construction' on page 2472 undefined on
 input line 213303.

! Extra }, or forgotten $.
l.213341 ...ound set is always $V = \{0, ..., n-1}
                                                  $ and the
? 
! Emergency stop.
l.213341 ...ound set is always $V = \{0, ..., n-1}
                                                  $ and the
!  ==> Fatal error occurred, no output PDF file produced!
Transcript written on combinat.log.
make[1]: *** [combinat.pdf] Error 1
make[1]: Leaving directory `/home/release/Sage/src/doc/output/latex/en/reference/combinat'
Error building the documentation.

comment:45 Changed 5 years ago by git

  • Commit changed from 42239ccc8b169e1aaf148da90b638004a09e67c6 to 24ac3a8e0424d9b4516517144935b0367a95801e

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

24ac3a8trac #16391: Broken doc

comment:46 Changed 5 years ago by ncohen

Sorry for that.

Now "make doc-clean && make doc-pdf" breaks when compiling some french document, but that's unrelated.

Nathann

comment:47 Changed 5 years ago by ncohen

  • Status changed from needs_work to positive_review

comment:48 Changed 5 years ago by ncohen

  • Dependencies changed from #16370 to #16370,#16460

comment:49 Changed 5 years ago by ncohen

  • Dependencies changed from #16370,#16460 to #16460

comment:50 Changed 5 years ago by git

  • Commit changed from 24ac3a8e0424d9b4516517144935b0367a95801e to 70c98058b2414e3fc873a8825c1db293da0709e3
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:

6fb1f14trac #16295: Bugfix
1653790trac #16295: Merged with 6.3.beta3
b66a187fixed some small language typos and changed MOLS error messages into context that MOLS researchers will expect.
02f1247trac #16295: one more doctest
f969003trac #16356: MOLS for n=18,57,154,276,298,342
917dd5ctrac #16356: Merged with #16295
f23d39ctrac #16460: a cache for OA/TD/MOLS existence
60b717ftrac #16460: small fixes
d7cb52atrac #16460: Merged with updated #16356
70c9805trac #16391: Merged with #16460

comment:51 Changed 5 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:52 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/16391 to 70c98058b2414e3fc873a8825c1db293da0709e3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.