Sage: Ticket #18987: Parallel computation of number of solutions in dancing links
https://trac.sagemath.org/ticket/18987
<p>
The following computation takes a lot of time:
</p>
<pre class="wiki">sage: from sage.games.quantumino import QuantuminoSolver
sage: QuantuminoSolver(0).number_of_solutions() # long time (several days)
</pre><p>
but we can make it faster by doing the computation in parallel... This ticket does this (directly in the dancing links code).
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/18987
Trac 1.1.6slabbeTue, 04 Aug 2015 13:23:22 GMTcommit, branch set
https://trac.sagemath.org/ticket/18987#comment:1
https://trac.sagemath.org/ticket/18987#comment:1
<ul>
<li><strong>commit</strong>
set to <em>a86b42d048567484cf30c7a6f7838704615083e3</em>
</li>
<li><strong>branch</strong>
set to <em>u/slabbe/18987</em>
</li>
</ul>
<p>
Preliminary version. Not ready for review.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ee430a47cc3f7eb71bf6358ee50f360ac3cf6c57"><span class="icon"></span>ee430a4</a></td><td><code>Parallel computation of the nb of solutions for tilings</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a86b42d048567484cf30c7a6f7838704615083e3"><span class="icon"></span>a86b42d</a></td><td><code>Tilings polyominos modulo 180 degrees rotations</code>
</td></tr></table>
TicketgitTue, 04 Aug 2015 13:31:57 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:2
https://trac.sagemath.org/ticket/18987#comment:2
<ul>
<li><strong>commit</strong>
changed from <em>a86b42d048567484cf30c7a6f7838704615083e3</em> to <em>6fd4a8759641415b121b4a12aa6ecb711490b533</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=406d8766e149baf3e381a0fbefc1e4ec44e6e203"><span class="icon"></span>406d876</a></td><td><code>Parallel computation of the nb of solutions for tilings</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6fd4a8759641415b121b4a12aa6ecb711490b533"><span class="icon"></span>6fd4a87</a></td><td><code>Tilings polyominos modulo 180 degrees rotations</code>
</td></tr></table>
TicketslabbeTue, 04 Aug 2015 19:39:22 GMTdescription changed
https://trac.sagemath.org/ticket/18987#comment:3
https://trac.sagemath.org/ticket/18987#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/18987?action=diff&version=3">diff</a>)
</li>
</ul>
TicketslabbeTue, 04 Aug 2015 19:40:12 GMTcommit, branch deleted
https://trac.sagemath.org/ticket/18987#comment:4
https://trac.sagemath.org/ticket/18987#comment:4
<ul>
<li><strong>commit</strong>
<em>6fd4a8759641415b121b4a12aa6ecb711490b533</em> deleted
</li>
<li><strong>branch</strong>
<em>u/slabbe/18987</em> deleted
</li>
</ul>
TicketslabbeTue, 04 Aug 2015 19:41:57 GMTstatus changed; commit, branch set
https://trac.sagemath.org/ticket/18987#comment:5
https://trac.sagemath.org/ticket/18987#comment:5
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>3c11961ebae4953711c490f7ac57679b99c59b52</em>
</li>
<li><strong>branch</strong>
set to <em>u/slabbe/18987</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=06915dc3b89c1e8b4f1214a0985e27a3bf6434c7"><span class="icon"></span>06915dc</a></td><td><code>Parallel computation of the nb of solutions for tilings</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=520cf9361dbcc4f870ee8d0526c85cf6a049b253"><span class="icon"></span>520cf93</a></td><td><code>Tilings of polyominos modulo 180 degrees rotations</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3c11961ebae4953711c490f7ac57679b99c59b52"><span class="icon"></span>3c11961</a></td><td><code>Add a transparent gray box to QuantuminoState.show3d</code>
</td></tr></table>
TicketslabbeTue, 04 Aug 2015 19:48:42 GMTstatus changed
https://trac.sagemath.org/ticket/18987#comment:6
https://trac.sagemath.org/ticket/18987#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Still other stuff to improve...
</p>
TicketgitTue, 04 Aug 2015 21:07:04 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:7
https://trac.sagemath.org/ticket/18987#comment:7
<ul>
<li><strong>commit</strong>
changed from <em>3c11961ebae4953711c490f7ac57679b99c59b52</em> to <em>b370fd04a3efb7393d5516936958c552934faa7f</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a75f8e3201330a652af9f2b69cc0af86ed2f7b3b"><span class="icon"></span>a75f8e3</a></td><td><code>Parallel computation of the nb of solutions for tilings</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=21038b033a90520ee142dbabac283929c5fa017b"><span class="icon"></span>21038b0</a></td><td><code>Tilings of polyominos modulo 180 degrees rotations</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b370fd04a3efb7393d5516936958c552934faa7f"><span class="icon"></span>b370fd0</a></td><td><code>Add a transparent gray box to QuantuminoState.show3d</code>
</td></tr></table>
TicketslabbeTue, 04 Aug 2015 21:10:06 GMTstatus changed
https://trac.sagemath.org/ticket/18987#comment:8
https://trac.sagemath.org/ticket/18987#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Ok, now needs reviews. I won't rebase my branch anymore.
</p>
TicketvdelecroixSun, 09 Aug 2015 18:09:16 GMTstatus changed; reviewer, author set
https://trac.sagemath.org/ticket/18987#comment:9
https://trac.sagemath.org/ticket/18987#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>Vincent Delecroix</em>
</li>
<li><strong>author</strong>
set to <em>Sébastien Labbé</em>
</li>
</ul>
<p>
Salut Sebastien,
</p>
<p>
Do you mind if I rebase over 6.9.beta1? Note that I also have a waiting commit that does some tiny optimization to <code>dancing_links.pyx</code>.
</p>
<p>
I am not sure the overall strategy is the good one. If parallelization is needed I guess that it should better be implemented at the level of dancing links. Googling "parallelization dancing links" already gives a lot of things.
</p>
<p>
Less importantly:
</p>
<ul><li>I do not understand the name of the function <code>orthogonal_transformation</code>. Are these the orthogonal transformations of <code>R^3</code> with integer coordinates? If so, please write more precise specifications.
</li></ul><ul><li>As far as I see, you do not test all cases of the function <code>orthogonal_transformation</code>.
</li></ul><ul><li>What is the <code>modpi</code> arguments. What is a rotation of angle <code>pi</code> for you? Is it a linear transformation that is a pi-rotation restricted on a plane and leaves invariant the orthogonal complement? (I guess it should also have integer coordinates) If this is, then it is of course not a group... but of course you might consider the group generated by these.
</li></ul><p>
Vincent
</p>
TicketslabbeSun, 09 Aug 2015 20:07:18 GMT
https://trac.sagemath.org/ticket/18987#comment:10
https://trac.sagemath.org/ticket/18987#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:9" title="Comment 9">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Salut Sebastien,
</p>
<p>
Do you mind if I rebase over 6.9.beta1?
</p>
</blockquote>
<p>
Merge or rebase? I prefer if you merge. Or I can rebase on 6.9.beta1 to keep the authorship (right?).
</p>
<blockquote class="citation">
<p>
Note that I also have a waiting commit that does some tiny optimization to <code>dancing_links.pyx</code>.
</p>
</blockquote>
<p>
Where?
</p>
<blockquote class="citation">
<p>
I am not sure the overall strategy is the good one. If parallelization is needed I guess that it should better be implemented at the level of dancing links. Googling "parallelization dancing links" already gives a lot of things.
</p>
</blockquote>
<p>
Indeed, I am using a parallelization strategy that applies to a tiling problem where each piece is used only once. This strategy obviously does not apply to the general problem that is the Exact cover problem.
</p>
<p>
Also, I prefered to cut the (tiling) problem into subproblems that takes at most 2-3 hours each so that I can more easily follow the process of the computation and stop and restart the computation more easily. Even with a parallel implementation of dancing links, the computation would take days to finish.
</p>
TicketvdelecroixSun, 09 Aug 2015 20:18:12 GMT
https://trac.sagemath.org/ticket/18987#comment:11
https://trac.sagemath.org/ticket/18987#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:10" title="Comment 10">slabbe</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:9" title="Comment 9">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Salut Sebastien,
</p>
<p>
Do you mind if I rebase over 6.9.beta1?
</p>
</blockquote>
<p>
Merge or rebase? I prefer if you merge. Or I can rebase on 6.9.beta1 to keep the authorship (right?).
</p>
</blockquote>
<p>
The autorship of what? If I do a rebase, you keep the autorship of commits. But of course it will be my branch (or a public one).
</p>
<p>
I do prefer rebase over merge because:
</p>
<ul><li>history is much cleaner afterwards (fewer commits that follow each other)
</li><li>you can hide whatever you want in a merge commit
</li></ul><blockquote class="citation">
<blockquote class="citation">
<p>
Note that I also have a waiting commit that does some tiny optimization to <code>dancing_links.pyx</code>.
</p>
</blockquote>
<p>
Where?
</p>
</blockquote>
<p>
On my computer ;-) It is waiting for the rebase or merge.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
I am not sure the overall strategy is the good one. If parallelization is needed I guess that it should better be implemented at the level of dancing links. Googling "parallelization dancing links" already gives a lot of things.
</p>
</blockquote>
<p>
Indeed, I am using a parallelization strategy that applies to a tiling problem where each piece is used only once. This strategy obviously does not apply to the general problem that is the Exact cover problem.
</p>
</blockquote>
<p>
In the exact cover problem, each subset is used at most once. In your tiling formulation a piece count for several subsets. You can naively apply the same thing for dancing links: look at one position <code>i0</code> and consider the set <code>S0</code> of subsets that cover it. For each subset in <code>S0</code>, launch a thread where you only run through the subproblem that consists of having fixed this subset.
</p>
<p>
But I guess that there exists less naive parallelization.
</p>
<blockquote class="citation">
<p>
Also, I prefered to cut the (tiling) problem into subproblems that takes at most 2-3 hours each so that I can more easily follow the process of the computation and stop and restart the computation more easily. Even with a parallel implementation of dancing links, the computation would take days to finish.
</p>
</blockquote>
<p>
Why? If your parallization ends with a time better than <code>total_time / nb_cpus</code> then you should parallelize more often ;-)
</p>
<p>
Vincent
</p>
TicketslabbeSun, 09 Aug 2015 20:20:03 GMT
https://trac.sagemath.org/ticket/18987#comment:12
https://trac.sagemath.org/ticket/18987#comment:12
<blockquote class="citation">
<p>
Less importantly:
</p>
<ul><li>I do not understand the name of the function <code>orthogonal_transformation</code>.
</li></ul></blockquote>
<p>
I chose that name 3 years ago. I agree it was not the best function name.
</p>
<p>
Your comments are very good. The reason that things are not clearly written is that it is not clear enough in my head. Let me sleep this night and I will come back on this tomorrow or later this week.
</p>
<p>
When <code>modpi=True</code>, I (think! I) want to quotient the result by the group generated by the diagonal matrices of 1's and -1's with exactly two -1 on the diagonal. Only, when the dimension is 3, I was able to generate representative of the classes easily.
</p>
TicketslabbeSun, 09 Aug 2015 20:27:54 GMT
https://trac.sagemath.org/ticket/18987#comment:13
https://trac.sagemath.org/ticket/18987#comment:13
<blockquote class="citation">
<p>
Why? If your parallization ends with a time better than <code>total_time / nb_cpus</code> then you should parallelize more often ;-)
</p>
</blockquote>
<p>
I have 240 subproblems each of them taking between 20 minutes and 10 hours of computation. But my machine at work only have 4 cores. So one way or the other, the computation takes days to finish since I do not have access to a super machine.
</p>
TicketslabbeSun, 09 Aug 2015 20:31:24 GMT
https://trac.sagemath.org/ticket/18987#comment:14
https://trac.sagemath.org/ticket/18987#comment:14
<blockquote class="citation">
<p>
I am not sure the overall strategy is the good one. If parallelization is needed I guess that it should better be implemented at the level of dancing links. Googling "parallelization dancing links" already gives a lot of things.
</p>
</blockquote>
<p>
If you agree, I suggest to move the discussion of "parallelization dancing links" in another ticket for which I am willing to be a reviewer.
</p>
TicketvdelecroixSun, 09 Aug 2015 20:36:38 GMT
https://trac.sagemath.org/ticket/18987#comment:15
https://trac.sagemath.org/ticket/18987#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:13" title="Comment 13">slabbe</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Why? If your parallization ends with a time better than <code>total_time / nb_cpus</code> then you should parallelize more often ;-)
</p>
</blockquote>
<p>
I have 240 subproblems each of them taking between 20 minutes and 10 hours of computation. But my machine at work only have 4 cores. So one way or the other, the computation takes days to finish since I do not have access to a super machine.
</p>
</blockquote>
<p>
This looks very bad. At the end, you might end up with only one core working on the biggest subinstance. And it can lasts several days even with 200 cores. Ideally, you should slice the problem in such way that each subinstance will not take longer than 1 hour (let say). This is why adopting a less naive strategy at the level of dancing links seems to me the best option since people already worked on it.
</p>
<p>
There is no super computer in Liege? I can set an invitation to use the very powerful <a class="ext-link" href="https://plafrim.bordeaux.inria.fr/doku.php"><span class="icon"></span>Plafrim</a> in Bordeaux. But it is some work to learn how to use it (e.g. you need to tell in advance for how long you request the processors).
</p>
<p>
Vincent
</p>
TicketgitSun, 09 Aug 2015 20:45:31 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:16
https://trac.sagemath.org/ticket/18987#comment:16
<ul>
<li><strong>commit</strong>
changed from <em>b370fd04a3efb7393d5516936958c552934faa7f</em> to <em>cbbc26242b1883f8a51065ccd7e8e97e6154025b</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=55fb3b7c845f7c7a49b966f84314804f589454ef"><span class="icon"></span>55fb3b7</a></td><td><code>Parallel computation of the nb of solutions for tilings</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ef310074326f707952a73a5a99ce3b43e3b98c3d"><span class="icon"></span>ef31007</a></td><td><code>Tilings of polyominos modulo 180 degrees rotations</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=cbbc26242b1883f8a51065ccd7e8e97e6154025b"><span class="icon"></span>cbbc262</a></td><td><code>Add a transparent gray box to QuantuminoState.show3d</code>
</td></tr></table>
TicketvdelecroixSun, 09 Aug 2015 20:50:36 GMT
https://trac.sagemath.org/ticket/18987#comment:17
https://trac.sagemath.org/ticket/18987#comment:17
<p>
Quickly reading [1] (which looks serious but not very deep) it seems that it is hard to find subinstance of the problems that are well scaled for a given cluster.
</p>
<blockquote>
<p>
[1] S. M. Ashraful Kadir, "A Parallel Programming Approach to Solve the Exact Cover Problem"
</p>
</blockquote>
TicketslabbeSun, 09 Aug 2015 20:55:06 GMT
https://trac.sagemath.org/ticket/18987#comment:18
https://trac.sagemath.org/ticket/18987#comment:18
<blockquote class="citation">
<p>
This looks very bad. At the end, you might end up with only one core working on the biggest subinstance. And it can lasts several days even with 200 cores. Ideally, you should slice the problem in such way that each subinstance will not take longer than 1 hour (let say).
</p>
</blockquote>
<p>
It is not very bad as most of the 240 computations takes the same amount of time (about 2 to 3 hours). Maybe 5 of time takes more (10 hours). So I am using the four cores at least 95% of the time. In my case, I have very good subinstances to reuse your term.
</p>
<blockquote class="citation">
<p>
There is no super computer in Liege?
</p>
</blockquote>
<p>
Well maybe there is something. It is the first time in Liège that I need computation power, but it is the vacation now.
</p>
<blockquote class="citation">
<p>
I can set an invitation to use the very powerful <a class="ext-link" href="https://plafrim.bordeaux.inria.fr/doku.php"><span class="icon"></span>Plafrim</a> in Bordeaux. But it is some work to learn how to use it (e.g. you need to tell in advance for how long you request the processors).
</p>
</blockquote>
<p>
That would be nice!
</p>
TicketslabbeSun, 09 Aug 2015 21:02:10 GMT
https://trac.sagemath.org/ticket/18987#comment:19
https://trac.sagemath.org/ticket/18987#comment:19
<blockquote class="citation">
<p>
Do you mind if I rebase over 6.9.beta1?
</p>
</blockquote>
<p>
I just did that (in case you did not notice).
</p>
TicketvdelecroixSun, 09 Aug 2015 21:14:39 GMTcommit, branch changed
https://trac.sagemath.org/ticket/18987#comment:20
https://trac.sagemath.org/ticket/18987#comment:20
<ul>
<li><strong>commit</strong>
changed from <em>cbbc26242b1883f8a51065ccd7e8e97e6154025b</em> to <em>9d8d0a142b58c2ab0c3ab2e18eef093295c0c54e</em>
</li>
<li><strong>branch</strong>
changed from <em>u/slabbe/18987</em> to <em>public/18987</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=9d8d0a142b58c2ab0c3ab2e18eef093295c0c54e"><span class="icon"></span>9d8d0a1</a></td><td><code>doc + optim in dancing_links</code>
</td></tr></table>
TicketvdelecroixSun, 09 Aug 2015 21:19:35 GMT
https://trac.sagemath.org/ticket/18987#comment:21
https://trac.sagemath.org/ticket/18987#comment:21
<p>
I found the organization of the dancing links code very confusing. Do you know why there are both a file <code>dancing_links.pyx</code> (that wraps the C++ class as a Cython class) and a file <code>dlxcpp.py</code> (that uses the Cython class in a functional style)? And there is also a <code>combinat/dlx.py</code>!! I guess this is mostly historical but it needs a serious cleanup.
</p>
TicketslabbeSun, 09 Aug 2015 21:25:18 GMT
https://trac.sagemath.org/ticket/18987#comment:22
https://trac.sagemath.org/ticket/18987#comment:22
<p>
Even just inside <code>dancing_links.pyx</code>, the class is called a Wrapper for the C++ code and <code>dlx_solver</code> is a function that calls the constructor of the wrapper...
</p>
<p>
Also I would not put this in <code>combnat/matrices</code> just because the exact cover problem can be represented as a 0-1 matrix...
</p>
TicketgitMon, 10 Aug 2015 07:31:17 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:23
https://trac.sagemath.org/ticket/18987#comment:23
<ul>
<li><strong>commit</strong>
changed from <em>9d8d0a142b58c2ab0c3ab2e18eef093295c0c54e</em> to <em>91de8636683e1c8cec7d9d33e645721572de3b1c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=91de8636683e1c8cec7d9d33e645721572de3b1c"><span class="icon"></span>91de863</a></td><td><code>rename orthogonal_transformation function</code>
</td></tr></table>
TicketslabbeMon, 10 Aug 2015 08:11:01 GMT
https://trac.sagemath.org/ticket/18987#comment:24
https://trac.sagemath.org/ticket/18987#comment:24
<p>
Is there a way to quotient two groups in Sage, maybe using gap or something ?
</p>
<pre class="wiki">sage: L = [w.matrix() for w in WeylGroup(['B',3]) if w.matrix().det()==1]
sage: G = MatrixGroup(L)
sage: H = MatrixGroup(L[:4])
sage: len(G)
24
sage: len(H)
4
sage: H
Matrix group over Rational Field with 4 generators (
[1 0 0] [ 1 0 0] [-1 0 0] [-1 0 0]
[0 1 0] [ 0 -1 0] [ 0 1 0] [ 0 -1 0]
[0 0 1], [ 0 0 -1], [ 0 0 -1], [ 0 0 1]
)
sage: G.quotient(H)
Traceback (most recent call last):
...
NotImplementedError:
</pre>
TicketgitMon, 10 Aug 2015 09:07:23 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:25
https://trac.sagemath.org/ticket/18987#comment:25
<ul>
<li><strong>commit</strong>
changed from <em>91de8636683e1c8cec7d9d33e645721572de3b1c</em> to <em>0c752d4038a7419285a1c1fa9b0c21842b593a2e</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0c752d4038a7419285a1c1fa9b0c21842b593a2e"><span class="icon"></span>0c752d4</a></td><td><code>Improve explanation of the modpi argument</code>
</td></tr></table>
TicketslabbeMon, 10 Aug 2015 09:08:44 GMTstatus changed
https://trac.sagemath.org/ticket/18987#comment:26
https://trac.sagemath.org/ticket/18987#comment:26
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<blockquote class="citation">
<ul><li>What is the <code>modpi</code> arguments. What is a rotation of angle <code>pi</code> for you? Is it a linear transformation that is a pi-rotation restricted on a plane and leaves invariant the orthogonal complement? (I guess it should also have integer coordinates) If this is, then it is of course not a group... but of course you might consider the group generated by these.
</li></ul></blockquote>
<p>
Ok, so tell me if it is better now.
</p>
TicketvdelecroixMon, 10 Aug 2015 09:24:12 GMT
https://trac.sagemath.org/ticket/18987#comment:27
https://trac.sagemath.org/ticket/18987#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:26" title="Comment 26">slabbe</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<ul><li>What is the <code>modpi</code> arguments. What is a rotation of angle <code>pi</code> for you? Is it a linear transformation that is a pi-rotation restricted on a plane and leaves invariant the orthogonal complement? (I guess it should also have integer coordinates) If this is, then it is of course not a group... but of course you might consider the group generated by these.
</li></ul></blockquote>
<p>
Ok, so tell me if it is better now.
</p>
</blockquote>
<p>
A bit. What do you mean by <code>the rectangular parallelepiped</code>? There is only one? As far as I understand it is the isometry group that preserves <strong>any</strong> rectangular parallelepiped. You can also say differently: the group of orientable isometry that preserve (globally) each axis. Is that right?
</p>
<p>
And as before, this is the group *generated* by these rotation and not only thes rotations themselves (except in dim 2 and 3).
</p>
<p>
Isn't this group exactly the subgroup of matrices with an even number of <code>-1</code> on the diagonal? So the quotient is just the signed permutation matrices with either <code>0</code> or <code>1</code> coefficient <code>-1</code> (all others being <code>1</code>). Isn't it?
</p>
<p>
When <code>orientation_preserving</code> is <code>False</code> I guess this group is the subgroup of matrices with any number of <code>-1</code> on the diagonal. In that case, the quotient would just be the permutation matrices. No?
</p>
TicketvdelecroixMon, 10 Aug 2015 09:25:44 GMT
https://trac.sagemath.org/ticket/18987#comment:28
https://trac.sagemath.org/ticket/18987#comment:28
<p>
And when you say <code>that is by rotations of angle pi</code> this is confusing since there are infinitely many of them. You can say <code>by rotations of angle pi on the plane generated by two axes</code>.
</p>
TicketslabbeMon, 10 Aug 2015 09:38:37 GMT
https://trac.sagemath.org/ticket/18987#comment:29
https://trac.sagemath.org/ticket/18987#comment:29
<blockquote class="citation">
<p>
A bit. What do you mean by <code>the rectangular parallelepiped</code>? There is only one?
</p>
</blockquote>
<p>
Of course the length of the side can change, so there is more than one. But, of course, I consider the case where the length of the sides are all distinct.
</p>
<blockquote class="citation">
<p>
As far as I understand it is the isometry group that preserves <strong>any</strong> rectangular parallelepiped.
</p>
</blockquote>
<p>
You understand well.
</p>
<blockquote class="citation">
<p>
You can also say differently: the group of orientable isometry that preserve (globally) each axis. Is that right?
</p>
</blockquote>
<p>
Yes.
</p>
<blockquote class="citation">
<p>
And as before, this is the group *generated* by these rotation and not only thes rotations themselves (except in dim 2 and 3).
</p>
</blockquote>
<p>
Of course. "modpi" is in the sense of modulo a group.
</p>
<blockquote class="citation">
<p>
Isn't this group exactly the subgroup of matrices with an even number of <code>-1</code> on the diagonal?
</p>
</blockquote>
<p>
Yes.
</p>
<blockquote class="citation">
<p>
So the quotient is just the signed permutation matrices with either <code>0</code> or <code>1</code> coefficient <code>-1</code> (all others being <code>1</code>). Isn't it?
</p>
</blockquote>
<p>
Maybe. When the dimension is odd, the quotient is the signed permutation matrices where the signs is either all positive or all negative with determinant 1. That is the formula that I was using.
</p>
<blockquote class="citation">
<p>
When <code>orientation_preserving</code> is <code>False</code> I guess this group is the subgroup of matrices with any number of <code>-1</code> on the diagonal. In that case, the quotient would just be the permutation matrices. No?
</p>
</blockquote>
<p>
Yes! You are right.
</p>
TicketslabbeMon, 10 Aug 2015 09:59:47 GMT
https://trac.sagemath.org/ticket/18987#comment:30
https://trac.sagemath.org/ticket/18987#comment:30
<blockquote class="citation">
<p>
So the quotient is just the signed permutation matrices with either <code>0</code> or <code>1</code> coefficient <code>-1</code> (all others being <code>1</code>). Isn't it?
</p>
</blockquote>
<p>
When <code>orientation_preserving=True</code>, the determinant of every returned matrix must be one. Therefore, I believe the quotient is the positive permutation matrices of determinant one + the other permutation matrices where one 1 is replaced by -1.
</p>
TicketslabbeMon, 10 Aug 2015 12:29:47 GMT
https://trac.sagemath.org/ticket/18987#comment:31
https://trac.sagemath.org/ticket/18987#comment:31
<blockquote class="citation">
<blockquote class="citation">
<p>
So the quotient is just the signed permutation matrices with either <code>0</code> or <code>1</code> coefficient <code>-1</code> (all others being <code>1</code>). Isn't it?
</p>
</blockquote>
<p>
Maybe. When the dimension is odd, the quotient is the signed permutation matrices where the signs is either all positive or all negative with determinant 1. That is the formula that I was using.
</p>
</blockquote>
<p>
Ok, now I understand why I needed it that way. I need well-chosen representatives for the quotient. By this, I mean that the chosen representatives of the cosets form a group itself.
</p>
<p>
For example, these representatives do not form a group:
</p>
<pre class="wiki">sage: n = 3
sage: c = identity_matrix(n)
sage: c[0,0] = -1
sage: L = [w.matrix() for w in WeylGroup(['A', n-1])]
sage: L = [(w if w.det() == 1 else c*w) for w in L]
[
[1 0 0] [ 0 0 -1] [0 0 1] [ 0 -1 0] [0 1 0] [-1 0 0]
[0 1 0] [ 0 1 0] [1 0 0] [ 1 0 0] [0 0 1] [ 0 0 1]
[0 0 1], [ 1 0 0], [0 1 0], [ 0 0 1], [1 0 0], [ 0 1 0]
]
sage: MatrixGroup(L).cardinality()
24
</pre><p>
But these representatives forms a group:
</p>
<pre class="wiki">sage: L = [w.matrix() for w in WeylGroup(['A', n-1])]
sage: L = [m.det() * m for m in L]
sage: L
[
[1 0 0] [ 0 0 -1] [0 0 1] [ 0 -1 0] [0 1 0] [-1 0 0]
[0 1 0] [ 0 -1 0] [1 0 0] [-1 0 0] [0 0 1] [ 0 0 -1]
[0 0 1], [-1 0 0], [0 1 0], [ 0 0 -1], [1 0 0], [ 0 -1 0]
]
sage: MatrixGroup(L).cardinality()
6
</pre><p>
And I still don't know how to construct the quotient when n is even.
</p>
TicketslabbeMon, 10 Aug 2015 12:46:46 GMT
https://trac.sagemath.org/ticket/18987#comment:32
https://trac.sagemath.org/ticket/18987#comment:32
<p>
Okay, so it is a chance that it works for when n is odd because in general:
</p>
<p>
<a class="ext-link" href="http://groupprops.subwiki.org/wiki/Quotient_group_need_not_be_isomorphic_to_any_subgroup"><span class="icon"></span>http://groupprops.subwiki.org/wiki/Quotient_group_need_not_be_isomorphic_to_any_subgroup</a>
</p>
TicketslabbeMon, 10 Aug 2015 13:45:20 GMT
https://trac.sagemath.org/ticket/18987#comment:33
https://trac.sagemath.org/ticket/18987#comment:33
<blockquote class="citation">
<p>
Ok, now I understand why I needed it that way.
</p>
</blockquote>
<p>
Wait. I really need the quotient itself finally. I was just lucky that the transformation keeping some the pentamino invariant was in the group.
</p>
<pre class="wiki">
sage: from sage.combinat.tiling import ncube_isometry_group
sage: from sage.games.quantumino import pentaminos
sage: L = ncube_isometry_group(3)
sage: f = lambda p : [m for m in L[1:] if (m*p).canonical() == p.canonical()]
sage: [(i, f(p)) for i,p in enumerate(pentaminos) if f(p)]
[(6, [
[ 0 0 -1]
[ 0 -1 0]
[-1 0 0]
]),
(7, [
[ 0 0 1]
[ 0 -1 0]
[ 1 0 0]
]),
(12, [
[-1 0 0]
[ 0 0 -1]
[ 0 -1 0]
]),
(13, [
[ 0 0 -1]
[ 0 -1 0]
[-1 0 0]
]),
(16, [
[ 0 0 -1]
[ 0 -1 0]
[-1 0 0]
])]
</pre><p>
Above, I get a problem with pentamino number 7 because it is invariant under a transformation that is not in the subgroup isomorphic to the quotient. So I really need to consider the quotient with all of the elements in each coset. Chosing a representative won't work even if it is well chosen.
</p>
<p>
Give me more time. I'll update my branch.
</p>
TicketgitMon, 10 Aug 2015 19:45:31 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:34
https://trac.sagemath.org/ticket/18987#comment:34
<ul>
<li><strong>commit</strong>
changed from <em>0c752d4038a7419285a1c1fa9b0c21842b593a2e</em> to <em>dc3797bd98509562635b7ef940c7cbd48fc71e31</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a51e4d83be6ed02daacecd3dd932db7099c4fbab"><span class="icon"></span>a51e4d8</a></td><td><code>Using cosets for when modpi=True</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=dc3797bd98509562635b7ef940c7cbd48fc71e31"><span class="icon"></span>dc3797b</a></td><td><code>Change pentaminos to there canonical form</code>
</td></tr></table>
TicketslabbeMon, 10 Aug 2015 19:46:24 GMT
https://trac.sagemath.org/ticket/18987#comment:35
https://trac.sagemath.org/ticket/18987#comment:35
<p>
Re-needs review.
</p>
TicketvdelecroixMon, 10 Aug 2015 21:58:52 GMT
https://trac.sagemath.org/ticket/18987#comment:36
https://trac.sagemath.org/ticket/18987#comment:36
<p>
Note that the patchbot was not able to build the doc.
</p>
TicketgitTue, 11 Aug 2015 06:02:29 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:37
https://trac.sagemath.org/ticket/18987#comment:37
<ul>
<li><strong>commit</strong>
changed from <em>dc3797bd98509562635b7ef940c7cbd48fc71e31</em> to <em>1e01ba27547f9a7f8ec2e35418f95b00e2ffb405</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ca84fcf36ec653753ad53297320c85a6867e0bff"><span class="icon"></span>ca84fcf</a></td><td><code>Trac #18987: Parallel computation of the nb of solutions for tilings</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3d4402bd52e80d94b2d199283ccb9900102565ee"><span class="icon"></span>3d4402b</a></td><td><code>Trac #18987: Tilings of polyominos modulo 180 degrees rotations</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=65f6512ae9b59de0634fd63ddd0bd23b443ab31d"><span class="icon"></span>65f6512</a></td><td><code>Trac #18987: Add a transparent gray box to QuantuminoState.show3d</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=555f0a9ecfa788fb7e82f8cf387037624504732b"><span class="icon"></span>555f0a9</a></td><td><code>Trac #18987: doc + optim in dancing_links</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=481d96eb3cf4e583775d5baa23305341fdd4de4f"><span class="icon"></span>481d96e</a></td><td><code>Trac #18987: rename orthogonal_transformation function</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5f66e1de423ce677cad0b7b4fd1e26029c77dde2"><span class="icon"></span>5f66e1d</a></td><td><code>Trac #18987: Improve explanation of the modpi argument</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d3591151d9498972eb705eeade3de87d633f888b"><span class="icon"></span>d359115</a></td><td><code>Trac #18987: Using cosets for when modpi=True</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1e01ba27547f9a7f8ec2e35418f95b00e2ffb405"><span class="icon"></span>1e01ba2</a></td><td><code>Trac #18987: Change pentaminos to there canonical form</code>
</td></tr></table>
TicketslabbeTue, 11 Aug 2015 06:05:55 GMT
https://trac.sagemath.org/ticket/18987#comment:38
https://trac.sagemath.org/ticket/18987#comment:38
<p>
There was a <code>TESTS::</code> with text following. Fixed that (and squashed it the the last commit). Also added the prefix <code>Trac #18987: </code> to all commit messages.
</p>
TicketslabbeTue, 11 Aug 2015 08:54:17 GMTstatus changed
https://trac.sagemath.org/ticket/18987#comment:39
https://trac.sagemath.org/ticket/18987#comment:39
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
There is one failing doctest on the patchbot that is not failing on my machine...
</p>
TicketgitTue, 11 Aug 2015 08:55:36 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:40
https://trac.sagemath.org/ticket/18987#comment:40
<ul>
<li><strong>commit</strong>
changed from <em>1e01ba27547f9a7f8ec2e35418f95b00e2ffb405</em> to <em>2133ecdcffb1b993049874c8be6cad2b1224a73a</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2133ecdcffb1b993049874c8be6cad2b1224a73a"><span class="icon"></span>2133ecd</a></td><td><code>Trac #18987: fixing intermittent doctest failure</code>
</td></tr></table>
TicketslabbeTue, 11 Aug 2015 08:55:55 GMTstatus changed
https://trac.sagemath.org/ticket/18987#comment:41
https://trac.sagemath.org/ticket/18987#comment:41
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketvdelecroixTue, 11 Aug 2015 10:13:45 GMT
https://trac.sagemath.org/ticket/18987#comment:42
https://trac.sagemath.org/ticket/18987#comment:42
<p>
Are you sure <code>ncube_isometry_group</code> is worth a <code>@cached_function</code>?
</p>
<p>
In <code>ncube_isometry_group_modpi</code> why are you building <code>MatrixGroup</code>?
</p>
<p>
In
</p>
<pre class="wiki">P_coset = set(frozenset((m.matrix() * self).canonical() for m in coset) for coset in L)
return set(next(iter(s)) for s in P_coset)
</pre><p>
You are building a lot of images to consider <code>matrix x polyomino</code> to use just one at the end. Why not
</p>
<pre class="wiki">return set((L[0].matrix() * self).canonical() for coset in L)
</pre><p>
And if you were not using matrix groups you can even do
</p>
<pre class="wiki">return set((L[0] * self).canonical() for coset in L)
</pre>
TicketslabbeTue, 11 Aug 2015 11:43:42 GMT
https://trac.sagemath.org/ticket/18987#comment:43
https://trac.sagemath.org/ticket/18987#comment:43
<p>
You are using <code>L</code> instead of <code>coset</code> I think. Can you edit your previous comment to make sure I understand what you mean?
</p>
TicketslabbeTue, 11 Aug 2015 11:48:05 GMT
https://trac.sagemath.org/ticket/18987#comment:44
https://trac.sagemath.org/ticket/18987#comment:44
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:42" title="Comment 42">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Are you sure <code>ncube_isometry_group</code> is worth a <code>@cached_function</code>?
</p>
</blockquote>
<p>
Calling this function takes 2.8s on my machine. And it is called once for each polyomino. That is 16 times for the Quantumino puzzle. With the cache, I gain about 40s to construct the rows to give to the dlx solver.
</p>
<blockquote class="citation">
<p>
In <code>ncube_isometry_group_modpi</code> why are you building <code>MatrixGroup</code>?
</p>
</blockquote>
<p>
Because otherwise, this
</p>
<pre class="wiki">G = ncube_isometry_group(n, orientation_preserving)
H = [h for h in G if all(i==j for (i,j) in h.nonzero_positions())]
left_cosets = set(tuple(sorted(h*g for h in H)) for g in G)
</pre><p>
throws a <code>TypeError: mutable matrices are unhashable</code> and I find it more fun to read like this instead of the <code>.set_immutable()</code> on every matrices.
</p>
TicketslabbeTue, 11 Aug 2015 12:16:54 GMT
https://trac.sagemath.org/ticket/18987#comment:45
https://trac.sagemath.org/ticket/18987#comment:45
<blockquote class="citation">
<p>
You are building a lot of images to consider <code>matrix x polyomino</code> to use just one at the end. Why not
</p>
</blockquote>
<p>
I know but I need all of them. That is what I understood yesterday. Let me try to explain. In general it is okay to take only one matrix in the coset. The problem comes when the polyomino is invariant under some of the 24 orientation preserving isometries of the cube. For example, consider:
</p>
<pre class="wiki">sage: from sage.games.quantumino import pentaminos
sage: from sage.combinat.tiling import ncube_isometry_group
sage: p = pentaminos[7]
sage: m = ncube_isometry_group(3)[-3]
sage: p
Polyomino: [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 2, 1), (1, 0, 0)], Color: orange
sage: m
[ 0 0 1]
[ 0 -1 0]
[ 1 0 0]
sage: (m*p).canonical() == p
True
</pre><p>
The polyomino <code>p</code> has 12 distinct rotation images instead of 24. And among the 12 ways of placing that polyomino into a box, there are 3 distinct ways up to rotation of the box keeping the box invariant. To compute this, we need to consider the whole coset:
</p>
<pre class="wiki">sage: cosets = ncube_isometry_group_modpi(3)
sage: P_coset = set(frozenset((m.matrix() * p).canonical() for m in coset) for coset in cosets)
sage: len(P_coset)
3
sage: len(set(next(iter(s)) for s in P_coset))
3
</pre><p>
Otherwise, you obtain too many polyominos (see below).
</p>
<pre class="wiki">sage: set((coset[0].matrix() * p).canonical() for coset in cosets)
{Polyomino: [(0, 0, 1), (1, 0, 1), (1, 1, 1), (1, 2, 0), (1, 2, 1)], Color: orange,
Polyomino: [(0, 1, 2), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 1, 2)], Color: orange,
Polyomino: [(0, 0, 0), (0, 1, 0), (1, 1, 0), (2, 1, 0), (2, 1, 1)], Color: orange,
Polyomino: [(0, 1, 0), (0, 1, 1), (1, 1, 1), (2, 0, 1), (2, 1, 1)], Color: orange,
Polyomino: [(0, 2, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 2, 0)], Color: orange}
</pre>
TicketvdelecroixTue, 11 Aug 2015 16:20:33 GMT
https://trac.sagemath.org/ticket/18987#comment:46
https://trac.sagemath.org/ticket/18987#comment:46
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:44" title="Comment 44">slabbe</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:42" title="Comment 42">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Are you sure <code>ncube_isometry_group</code> is worth a <code>@cached_function</code>?
</p>
</blockquote>
<p>
Calling this function takes 2.8s on my machine. And it is called once for each polyomino. That is 16 times for the Quantumino puzzle. With the cache, I gain about 40s to construct the rows to give to the dlx solver.
</p>
</blockquote>
<p>
Perhaps the way it is implemented is wrong. For example
</p>
<pre class="wiki">sage: %timeit P = [s.matrix() for s in SymmetricGroup(4)]
1 loops, best of 3: 1.27 ms per loop
</pre><p>
and with the signs
</p>
<pre class="wiki">sage: from itertools import product
sage: %timeit M = [diagonal_matrix(p) for p in product([1,-1], repeat=4)]
1 loops, best of 3: 2.9 ms per loop
sage: M = [diagonal_matrix(p) for p in product([1,-1], repeat=4)]
sage: %timeit S = [m*s.matrix() for m in M for s in SymmetricGroup(4)]
100 loops, best of 3: 18.3 ms per loop
</pre><p>
So it is likely to be <code>~20ms</code>.
</p>
TicketgitWed, 12 Aug 2015 08:53:40 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:47
https://trac.sagemath.org/ticket/18987#comment:47
<ul>
<li><strong>commit</strong>
changed from <em>2133ecdcffb1b993049874c8be6cad2b1224a73a</em> to <em>0d68ecec28cb92d9e78a92d6e733d42b3e8941c1</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0d68ecec28cb92d9e78a92d6e733d42b3e8941c1"><span class="icon"></span>0d68ece</a></td><td><code>Trac #18987: removed a cached_function</code>
</td></tr></table>
TicketslabbeWed, 12 Aug 2015 09:08:32 GMT
https://trac.sagemath.org/ticket/18987#comment:48
https://trac.sagemath.org/ticket/18987#comment:48
<blockquote class="citation">
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:42" title="Comment 42">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Are you sure <code>ncube_isometry_group</code> is worth a <code>@cached_function</code>?
</p>
</blockquote>
</blockquote>
</blockquote>
<p>
In fact, you make me realize that there is already caching involved in WeylGroup. Therefore caching that function is not so necessary. Without caching, I get:
</p>
<pre class="wiki">sage: from sage.combinat.tiling import ncube_isometry_group
sage: time L = ncube_isometry_group(4)
CPU times: user 1.14 s, sys: 19.7 ms, total: 1.16 s
Wall time: 1.3 s
sage: time L = ncube_isometry_group(4)
CPU times: user 358 ms, sys: 4.01 ms, total: 362 ms
Wall time: 448 ms
</pre><blockquote class="citation">
<pre class="wiki">sage: from itertools import product
sage: %timeit M = [diagonal_matrix(p) for p in product([1,-1], repeat=4)]
1 loops, best of 3: 2.9 ms per loop
sage: M = [diagonal_matrix(p) for p in product([1,-1], repeat=4)]
sage: %timeit S = [m*s.matrix() for m in M for s in SymmetricGroup(4)]
100 loops, best of 3: 18.3 ms per loop
</pre><p>
So it is likely to be <code>~20ms</code>.
</p>
</blockquote>
<p>
Note that you can't use timeit above since there is caching involved in SymmetricGroup.
</p>
<p>
For comparison, your solution on my machine gives the following timings:
</p>
<div class="wiki-code"><div class="code"><pre>sage<span class="p">:</span> <span class="kn">from</span> <span class="nn">itertools</span> <span class="kn">import</span> product
sage<span class="p">:</span> <span class="c"># first call </span>
sage<span class="p">:</span> time M <span class="o">=</span> <span class="p">[</span>diagonal_matrix<span class="p">(</span>p<span class="p">)</span> <span class="k">for</span> p <span class="ow">in</span> product<span class="p">([</span><span class="mi">1</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> repeat<span class="o">=</span><span class="mi">4</span><span class="p">)]</span>
CPU times<span class="p">:</span> user <span class="mf">11.4</span> ms<span class="p">,</span> sys<span class="p">:</span> <span class="mi">92</span> <span class="err">µ</span>s<span class="p">,</span> total<span class="p">:</span> <span class="mf">11.5</span> ms
Wall time<span class="p">:</span> <span class="mf">11.9</span> ms
sage<span class="p">:</span> time S <span class="o">=</span> <span class="p">[</span>m<span class="o">*</span>s<span class="o">.</span>matrix<span class="p">()</span> <span class="k">for</span> m <span class="ow">in</span> M <span class="k">for</span> s <span class="ow">in</span> SymmetricGroup<span class="p">(</span><span class="mi">4</span><span class="p">)]</span>
CPU times<span class="p">:</span> user <span class="mi">191</span> ms<span class="p">,</span> sys<span class="p">:</span> <span class="mf">25.2</span> ms<span class="p">,</span> total<span class="p">:</span> <span class="mi">216</span> ms
Wall time<span class="p">:</span> <span class="mi">667</span> ms
sage<span class="p">:</span> <span class="c"># second call</span>
sage<span class="p">:</span> time M <span class="o">=</span> <span class="p">[</span>diagonal_matrix<span class="p">(</span>p<span class="p">)</span> <span class="k">for</span> p <span class="ow">in</span> product<span class="p">([</span><span class="mi">1</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> repeat<span class="o">=</span><span class="mi">4</span><span class="p">)]</span>
CPU times<span class="p">:</span> user <span class="mf">11.7</span> ms<span class="p">,</span> sys<span class="p">:</span> <span class="mf">1.34</span> ms<span class="p">,</span> total<span class="p">:</span> <span class="mi">13</span> ms
Wall time<span class="p">:</span> <span class="mf">16.6</span> ms
sage<span class="p">:</span> time S <span class="o">=</span> <span class="p">[</span>m<span class="o">*</span>s<span class="o">.</span>matrix<span class="p">()</span> <span class="k">for</span> m <span class="ow">in</span> M <span class="k">for</span> s <span class="ow">in</span> SymmetricGroup<span class="p">(</span><span class="mi">4</span><span class="p">)]</span>
CPU times<span class="p">:</span> user <span class="mi">108</span> ms<span class="p">,</span> sys<span class="p">:</span> <span class="mf">1.92</span> ms<span class="p">,</span> total<span class="p">:</span> <span class="mi">110</span> ms
Wall time<span class="p">:</span> <span class="mi">114</span> ms
</pre></div></div><p>
So it seems using <code>WeylGroup(['B',4])</code> is about 4 times slower than your solution. But I don't know if I will change it. I mean that improvement could be done directly in <code>WeylGroup</code> code...
</p>
TicketvdelecroixWed, 12 Aug 2015 13:19:48 GMT
https://trac.sagemath.org/ticket/18987#comment:49
https://trac.sagemath.org/ticket/18987#comment:49
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:48" title="Comment 48">slabbe</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<pre class="wiki">sage: from itertools import product
sage: %timeit M = [diagonal_matrix(p) for p in product([1,-1], repeat=4)]
1 loops, best of 3: 2.9 ms per loop
sage: M = [diagonal_matrix(p) for p in product([1,-1], repeat=4)]
sage: %timeit S = [m*s.matrix() for m in M for s in SymmetricGroup(4)]
100 loops, best of 3: 18.3 ms per loop
</pre><p>
So it is likely to be <code>~20ms</code>.
</p>
</blockquote>
<p>
Note that you can't use timeit above since there is caching involved in SymmetricGroup.
</p>
</blockquote>
<p>
Where?! Beyond the construction of the group (<code>SymmetricGroup(4) is SymmetricGroup(4)</code> gives <code>True</code>) nothing is cached.
</p>
TicketslabbeWed, 12 Aug 2015 13:58:36 GMT
https://trac.sagemath.org/ticket/18987#comment:50
https://trac.sagemath.org/ticket/18987#comment:50
<blockquote class="citation">
<p>
Where?! Beyond the construction of the group (<code>SymmetricGroup(4) is SymmetricGroup(4)</code> gives <code>True</code>) nothing is cached.
</p>
</blockquote>
<p>
Don't you get that the first execution of
</p>
<pre class="wiki">sage: time S = [m*s.matrix() for m in M for s in SymmetricGroup(4)]
</pre><p>
is slower than the second? And that the second takes about the same time than the third, the fourth, etc. ? Like me:
</p>
<pre class="wiki">sage: from itertools import product
sage: M = [diagonal_matrix(p) for p in product([1,-1], repeat=4)]
sage: time S = [m*s.matrix() for m in M for s in SymmetricGroup(4)]
CPU times: user 184 ms, sys: 18 ms, total: 202 ms
Wall time: 710 ms
sage: time S = [m*s.matrix() for m in M for s in SymmetricGroup(4)]
CPU times: user 109 ms, sys: 2.05 ms, total: 111 ms
Wall time: 166 ms
sage: time S = [m*s.matrix() for m in M for s in SymmetricGroup(4)]
CPU times: user 109 ms, sys: 2.6 ms, total: 111 ms
Wall time: 113 ms
sage: time S = [m*s.matrix() for m in M for s in SymmetricGroup(4)]
CPU times: user 110 ms, sys: 2.12 ms, total: 112 ms
Wall time: 169 ms
sage: time S = [m*s.matrix() for m in M for s in SymmetricGroup(4)]
CPU times: user 108 ms, sys: 2.44 ms, total: 111 ms
Wall time: 114 ms
</pre>
TicketvdelecroixWed, 12 Aug 2015 14:06:06 GMT
https://trac.sagemath.org/ticket/18987#comment:51
https://trac.sagemath.org/ticket/18987#comment:51
<p>
Yes for the timing. But this does <strong>not</strong> implies that something is cached. Actually, the reason is because gap is launched (I do not know why)
</p>
<pre class="wiki">sage: S = SymmetricGroup(4)
sage: time gap(3)
CPU times: user 16 ms, sys: 12 ms, total: 28 ms
Wall time: 295 ms
3
sage: from itertools import product
sage: M = [diagonal_matrix(p) for p in product([1,-1], repeat=4)]
sage: time S = [m*s.matrix() for m in M for s in SymmetricGroup(4)]
CPU times: user 56 ms, sys: 0 ns, total: 56 ms
Wall time: 56.9 ms
sage: time S = [m*s.matrix() for m in M for s in SymmetricGroup(4)]
CPU times: user 56 ms, sys: 0 ns, total: 56 ms
Wall time: 53 ms
</pre>
TicketslabbeWed, 12 Aug 2015 14:20:57 GMT
https://trac.sagemath.org/ticket/18987#comment:52
https://trac.sagemath.org/ticket/18987#comment:52
<p>
caching <code>ncube_isometry_group</code> gives:
</p>
<pre class="wiki">sage: from sage.games.quantumino import QuantuminoSolver
sage: q = QuantuminoSolver(0)
sage: t = q.tiling_solver()
sage: time rows = t.rows()
CPU times: user 18.8 s, sys: 168 ms, total: 19 s
Wall time: 19 s
</pre><p>
not caching <code>ncube_isometry_group</code> gives:
</p>
<pre class="wiki">sage: from sage.games.quantumino import QuantuminoSolver
sage: q = QuantuminoSolver(0)
sage: t = q.tiling_solver()
sage: time rows = t.rows()
CPU times: user 19.4 s, sys: 288 ms, total: 19.7 s
Wall time: 20 s
</pre><p>
So I confirm that I don't lose relatively much time by not caching.
</p>
TicketslabbeThu, 13 Aug 2015 12:03:18 GMT
https://trac.sagemath.org/ticket/18987#comment:53
https://trac.sagemath.org/ticket/18987#comment:53
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:46" title="Comment 46">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Perhaps the way it is implemented is wrong. For example
</p>
<pre class="wiki">sage: %timeit P = [s.matrix() for s in SymmetricGroup(4)]
1 loops, best of 3: 1.27 ms per loop
</pre></blockquote>
<p>
I removed the <code>cached_method</code>. Do you want me to replace the code based on <code>WeylGroup(['B',n])</code> by the <code>SymmetricGroup</code> + <code>diagonal_matrix of signs</code> code you propose? I think that this improvement should be done in <code>WeylGroup</code> in another ticket.
</p>
<p>
Also, for timing improvements in that file <code>tiling.py</code>, there is a another more important thing to spend time on because a lot of time is spent creating vectors from tuple (because coordinates are stored as tuple). This should be done in another ticket.
</p>
<p>
Needs review!
</p>
TicketvdelecroixThu, 13 Aug 2015 12:56:38 GMT
https://trac.sagemath.org/ticket/18987#comment:54
https://trac.sagemath.org/ticket/18987#comment:54
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:53" title="Comment 53">slabbe</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:46" title="Comment 46">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Perhaps the way it is implemented is wrong. For example
</p>
<pre class="wiki">sage: %timeit P = [s.matrix() for s in SymmetricGroup(4)]
1 loops, best of 3: 1.27 ms per loop
</pre></blockquote>
<p>
I removed the <code>cached_method</code>. Do you want me to replace the code based on <code>WeylGroup(['B',n])</code> by the <code>SymmetricGroup</code> + <code>diagonal_matrix of signs</code> code you propose? I think that this improvement should be done in <code>WeylGroup</code> in another ticket.
</p>
</blockquote>
<p>
Nope. I also the think that the <code>WeylGroup</code> code has to be improved.
</p>
<blockquote class="citation">
<p>
Also, for timing improvements in that file <code>tiling.py</code>, there is a another more important thing to spend time on because a lot of time is spent creating vectors from tuple (because coordinates are stored as tuple). This should be done in another ticket.
</p>
</blockquote>
<p>
Did you notice that
</p>
<pre class="wiki">sage: t = map(vector, t)
</pre><p>
is much slower than
</p>
<pre class="wiki">sage: V = FreeModule(ZZ,12)
sage: t = map(V,t)
</pre><p>
(I measure a factor x8 in <code>__sub__</code> and <code>__add__</code> for example)
</p>
<p>
Moreover, everything would be faster if you would store integer vectors instead of tuples (and an attribute <code>self._free_module</code>). Why aren't you doing that?
</p>
TicketvdelecroixThu, 13 Aug 2015 13:02:17 GMT
https://trac.sagemath.org/ticket/18987#comment:55
https://trac.sagemath.org/ticket/18987#comment:55
<p>
I still do not understand why you are parallelizing the polyomino solver code and not the DLX one. Isn't your strategy exactly equivalent to this one: pick a column, for each row that does have a 1 in this column remove all the columns occuppied by the piece and launch an independent process?
</p>
TicketslabbeSat, 15 Aug 2015 12:27:48 GMT
https://trac.sagemath.org/ticket/18987#comment:56
https://trac.sagemath.org/ticket/18987#comment:56
<blockquote class="citation">
<p>
Moreover, everything would be faster if you would store integer vectors instead of tuples (and an attribute <code>self._free_module</code>). Why aren't you doing that?
</p>
</blockquote>
<ol><li>Because I think I wanted to use the most basic hashable container (tuple) for the need. I realized only recently that it was slow because there are many matrix operations and additions involved. So indeed, storing vectors would be better.
</li></ol><ol start="2"><li>Because it is not the purpose of this ticket.
</li></ol>
TicketslabbeSat, 15 Aug 2015 12:28:53 GMTstatus changed
https://trac.sagemath.org/ticket/18987#comment:57
https://trac.sagemath.org/ticket/18987#comment:57
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:55" title="Comment 55">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
I still do not understand why you are parallelizing the polyomino solver code and not the DLX one. Isn't your strategy exactly equivalent to this one: pick a column, for each row that does have a 1 in this column remove all the columns occuppied by the piece and launch an independent process?
</p>
</blockquote>
<p>
Okay, I will work on a new commit for that.
</p>
TicketvdelecroixSat, 15 Aug 2015 12:37:08 GMT
https://trac.sagemath.org/ticket/18987#comment:58
https://trac.sagemath.org/ticket/18987#comment:58
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18987#comment:56" title="Comment 56">slabbe</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Moreover, everything would be faster if you would store integer vectors instead of tuples (and an attribute <code>self._free_module</code>). Why aren't you doing that?
</p>
</blockquote>
<ol><li>Because I think I wanted to use the most basic hashable container (tuple) for the need. I realized only recently that it was slow because there are many matrix operations and additions involved. So indeed, storing vectors would be better.
</li></ol><ol start="2"><li>Because it is not the purpose of this ticket.
</li></ol></blockquote>
<p>
I opened <a class="closed ticket" href="https://trac.sagemath.org/ticket/19036" title="enhancement: Use vectors instead of tuples in Polyomino (closed: fixed)">#19036</a>
</p>
TicketgitMon, 17 Aug 2015 21:50:09 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:59
https://trac.sagemath.org/ticket/18987#comment:59
<ul>
<li><strong>commit</strong>
changed from <em>0d68ecec28cb92d9e78a92d6e733d42b3e8941c1</em> to <em>df655874d79c75f3d5b18adda01cedb620a1856b</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=df655874d79c75f3d5b18adda01cedb620a1856b"><span class="icon"></span>df65587</a></td><td><code>Trac #18987: Moved the paralel computation of nb of sol in dancing links module</code>
</td></tr></table>
TicketslabbeMon, 17 Aug 2015 21:52:28 GMTstatus changed
https://trac.sagemath.org/ticket/18987#comment:60
https://trac.sagemath.org/ticket/18987#comment:60
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
(I will not have access to a machine with Sage for the next 7 days).
</p>
TicketslabbeMon, 24 Aug 2015 09:05:45 GMT
https://trac.sagemath.org/ticket/18987#comment:61
https://trac.sagemath.org/ticket/18987#comment:61
<p>
Ok, Vincent. I am now back and available to do the follow up on this ticket.
</p>
<p>
With the new proposal you made, this ticket now consist of two independant things. Do you prefer me to split the code into two tickets (easier to review) or is it ok like this?
</p>
<p>
Sébastien
</p>
TicketslabbeThu, 27 Aug 2015 19:25:05 GMTdescription, summary changed
https://trac.sagemath.org/ticket/18987#comment:62
https://trac.sagemath.org/ticket/18987#comment:62
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/18987?action=diff&version=62">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Parallel computation for TilingSolver.number_of_solutions</em> to <em>Parallel computation of number of solutions in dancing links</em>
</li>
</ul>
<p>
I finally decided to split this ticket into two to ease the review. The second part is now available at <a class="closed ticket" href="https://trac.sagemath.org/ticket/19107" title="enhancement: Do not count 4 times the same solution (up to rotations) in ... (closed: fixed)">#19107</a>.
</p>
TicketslabbeThu, 27 Aug 2015 19:26:46 GMTdescription changed
https://trac.sagemath.org/ticket/18987#comment:63
https://trac.sagemath.org/ticket/18987#comment:63
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/18987?action=diff&version=63">diff</a>)
</li>
</ul>
TicketgitThu, 27 Aug 2015 19:27:58 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:64
https://trac.sagemath.org/ticket/18987#comment:64
<ul>
<li><strong>commit</strong>
changed from <em>df655874d79c75f3d5b18adda01cedb620a1856b</em> to <em>c01612691e55baf745fc710fc8c8dfc97b885375</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8db8f72d4369f70aeff8cb26cde971961216fd7f"><span class="icon"></span>8db8f72</a></td><td><code>Trac #18987: Number of solutions method for dancing links</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=9d25f7c8ea01988f6e79903885cc41946ad2e4a0"><span class="icon"></span>9d25f7c</a></td><td><code>Trac #18987: doc + optim in dancing_links</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c01612691e55baf745fc710fc8c8dfc97b885375"><span class="icon"></span>c016126</a></td><td><code>Trac #18987: parallel computations in dancing links</code>
</td></tr></table>
TicketvdelecroixFri, 04 Sep 2015 00:04:07 GMTstatus changed
https://trac.sagemath.org/ticket/18987#comment:65
https://trac.sagemath.org/ticket/18987#comment:65
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<ul><li><code>(solving) independant (cases)</code> -> <code>independent</code>
</li><li>I do not understand this comment
<pre class="wiki">If possible, a good choice of column gives a partition
of solutions where each part has about the same number
of solutions.
</pre></li><li>could you make a complete sentence for the <code>OUTPUT</code> section instead of <code>dict, row number -> list of rows</code>
</li><li>this is not quite accurate
<pre class="wiki">After the split each subproblem has the same number of columns and
rows and the same solutions as above::
</pre>it is the union of solutions of the subproblems that form the solution of the initial one.
</li><li>I do not see the point of having <code>number_of_solutions_iterator</code> and <code>number_of_solutions</code>. You should just get rid of the first one and allow parallelization in the second.
</li><li>Why not also make available parallelization for getting the list of solutions?
</li></ul>
TicketgitSat, 05 Sep 2015 15:36:18 GMTcommit changed
https://trac.sagemath.org/ticket/18987#comment:66
https://trac.sagemath.org/ticket/18987#comment:66
<ul>
<li><strong>commit</strong>
changed from <em>c01612691e55baf745fc710fc8c8dfc97b885375</em> to <em>29ff98625316f95c48fd704115a209dce38deda8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=29ff98625316f95c48fd704115a209dce38deda8"><span class="icon"></span>29ff986</a></td><td><code>Trac #18987: Fixed reviewer comment 65</code>
</td></tr></table>
TicketslabbeSat, 05 Sep 2015 15:45:41 GMTstatus changed
https://trac.sagemath.org/ticket/18987#comment:67
https://trac.sagemath.org/ticket/18987#comment:67
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Thanks for your review! I fixed the first comments.
</p>
<blockquote class="citation">
<ul><li>I do not see the point of having <code>number_of_solutions_iterator</code> and <code>number_of_solutions</code>. You should just get rid of the first one and allow parallelization in the second.
</li></ul></blockquote>
<ul><li><code>number_of_solutions_iterator</code> is now <code>_number_of_solutions_iterator</code>
</li><li><code>number_of_solutions</code> now allows parallel computation
</li><li>I kept <code>_number_of_solutions_iterator</code> because for the problem I am currently looking at, <code>number_of_solutions</code> takes days while <code>_number_of_solutions_iterator</code> yield something once every hours. So it allows me to follow the computation, making sure it is not stuck and evaluate the duration left to do. I prefer this way rather than removing method <code>_number_of_solutions_iterator</code> and adding some verbose thing in <code>number_of_solutions</code>.
</li></ul><blockquote class="citation">
<ul><li>Why not also make available parallelization for getting the list of solutions?
</li></ul></blockquote>
<p>
Because I don't know how or if it is possible to use the parallel decorator to merge iterators.
</p>
TicketvdelecroixMon, 07 Sep 2015 17:33:41 GMTstatus changed
https://trac.sagemath.org/ticket/18987#comment:68
https://trac.sagemath.org/ticket/18987#comment:68
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Salut Sebastien,
</p>
<p>
Thanks for your patience. I am sure that the choice of splitting is suboptimal but at least the design is much cleaner than in the first version.
</p>
<p>
Vincent
</p>
TicketvbraunTue, 08 Sep 2015 14:41:15 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/18987#comment:69
https://trac.sagemath.org/ticket/18987#comment:69
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/18987</em> to <em>29ff98625316f95c48fd704115a209dce38deda8</em>
</li>
</ul>
Ticket