Parallel computation of number of solutions in dancing links

[seblabbe]

The following computation takes a lot of time:

sage: from sage.games.quantumino import QuantuminoSolver
sage: QuantuminoSolver(0).number_of_solutions()  # long time (several days)

but we can make it faster by doing the computation in parallel... This ticket does this (directly in the dancing links code).

Component: combinatorics

Author: Sébastien Labbé

Branch/Commit: 29ff986

Reviewer: Vincent Delecroix

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

[seblabbe]

comment:1

Preliminary version. Not ready for review.

---

New commits:

ee430a4	Parallel computation of the nb of solutions for tilings
a86b42d	Tilings polyominos modulo 180 degrees rotations

[seblabbe]

Commit: a86b42d

[seblabbe]

Branch: u/slabbe/18987

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a86b42d to 6fd4a87

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

406d876	Parallel computation of the nb of solutions for tilings
6fd4a87	Tilings polyominos modulo 180 degrees rotations

[seblabbe]

Description changed:

--- 
+++ 
@@ -5,8 +5,6 @@
 sage: QuantuminoSolver(0).number_of_solutions()  # long time (about 30 days)

-but we can make it faster by doing the computation in parallel... This ticket does this. It is motivated by a question I received from Nicolaas Neuwahl, the designer of the Quantumino puzzle: +but we can make it faster by doing the computation in parallel... This ticket does this.

• can you tell me HOW MANY different quantumino-solutions exist?

• -The official website says there are over 10.000 potential solutions. +It also simplify the computation by avoiding to compute 4 times the same solution (obtained by rotation of angle pi of the 5x8x2 box).

[seblabbe]

Changed branch from u/slabbe/18987 to none

[seblabbe]

Changed commit from 6fd4a87 to none

[seblabbe]

Commit: 3c11961

[seblabbe]

Branch: u/slabbe/18987

[seblabbe]

New commits:

06915dc	Parallel computation of the nb of solutions for tilings
520cf93	Tilings of polyominos modulo 180 degrees rotations
3c11961	Add a transparent gray box to QuantuminoState.show3d

[seblabbe]

comment:6

Still other stuff to improve...

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3c11961 to b370fd0

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a75f8e3	Parallel computation of the nb of solutions for tilings
21038b0	Tilings of polyominos modulo 180 degrees rotations
b370fd0	Add a transparent gray box to QuantuminoState.show3d

[seblabbe]

comment:8

Ok, now needs reviews. I won't rebase my branch anymore.

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:9

Salut Sebastien,

Do you mind if I rebase over 6.9.beta1? Note that I also have a waiting commit that does some tiny optimization to dancing_links.pyx.

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.

Less importantly:

• I do not understand the name of the function orthogonal_transformation. Are these the orthogonal transformations of R^3 with integer coordinates? If so, please write more precise specifications.

• As far as I see, you do not test all cases of the function orthogonal_transformation.

• What is the modpi arguments. What is a rotation of angle pi 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.

Vincent

[videlec]

Author: Sébastien Labbé

[seblabbe]

comment:10

Replying to @videlec:

Salut Sebastien,

Do you mind if I rebase over 6.9.beta1?

Merge or rebase? I prefer if you merge. Or I can rebase on 6.9.beta1 to keep the authorship (right?).

Note that I also have a waiting commit that does some tiny optimization to dancing_links.pyx.

Where?

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.

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.

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.

[videlec]

comment:11

Replying to @seblabbe:

Replying to @videlec:

Salut Sebastien,

Do you mind if I rebase over 6.9.beta1?

Merge or rebase? I prefer if you merge. Or I can rebase on 6.9.beta1 to keep the authorship (right?).

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).

I do prefer rebase over merge because:

• history is much cleaner afterwards (fewer commits that follow each other)
• you can hide whatever you want in a merge commit

Note that I also have a waiting commit that does some tiny optimization to dancing_links.pyx.

Where?

On my computer ;-) It is waiting for the rebase or merge.

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.

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.

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 i0 and consider the set S0 of subsets that cover it. For each subset in S0, launch a thread where you only run through the subproblem that consists of having fixed this subset.

But I guess that there exists less naive parallelization.

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.

Why? If your parallization ends with a time better than total_time / nb_cpus then you should parallelize more often ;-)

Vincent

[seblabbe]

comment:12

Less importantly:

• I do not understand the name of the function orthogonal_transformation.

I chose that name 3 years ago. I agree it was not the best function name.

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.

When modpi=True, 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.

[seblabbe]

comment:13

Why? If your parallization ends with a time better than total_time / nb_cpus then you should parallelize more often ;-)

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.

[seblabbe]

comment:14

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.

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.

[videlec]

comment:15

Replying to @seblabbe:

Why? If your parallization ends with a time better than total_time / nb_cpus then you should parallelize more often ;-)

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.

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.

There is no super computer in Liege? I can set an invitation to use the very powerful Plafrim 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).

Vincent

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

55fb3b7	Parallel computation of the nb of solutions for tilings
ef31007	Tilings of polyominos modulo 180 degrees rotations
cbbc262	Add a transparent gray box to QuantuminoState.show3d

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b370fd0 to cbbc262

[videlec]

comment:17

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.

[1] S. M. Ashraful Kadir, "A Parallel Programming Approach to Solve the Exact Cover Problem"

[seblabbe]

comment:18

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).

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.

There is no super computer in Liege?

Well maybe there is something. It is the first time in Liège that I need computation power, but it is the vacation now.

I can set an invitation to use the very powerful Plafrim 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).

That would be nice!

[seblabbe]

comment:19

Do you mind if I rebase over 6.9.beta1?

I just did that (in case you did not notice).

[videlec]

New commits:

9d8d0a1

doc + optim in dancing_links

[videlec]

Changed commit from cbbc262 to 9d8d0a1

[videlec]

Changed branch from u/slabbe/18987 to public/18987

[videlec]

comment:21

I found the organization of the dancing links code very confusing. Do you know why there are both a file dancing_links.pyx (that wraps the C++ class as a Cython class) and a file dlxcpp.py (that uses the Cython class in a functional style)? And there is also a combinat/dlx.py!! I guess this is mostly historical but it needs a serious cleanup.

[seblabbe]

comment:22

Even just inside dancing_links.pyx, the class is called a Wrapper for the C++ code and dlx_solver is a function that calls the constructor of the wrapper...

Also I would not put this in combnat/matrices just because the exact cover problem can be represented as a 0-1 matrix...

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9d8d0a1 to 91de863

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

91de863

rename orthogonal_transformation function

[seblabbe]

comment:24

Is there a way to quotient two groups in Sage, maybe using gap or something ?

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:

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0c752d4

Improve explanation of the modpi argument

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 91de863 to 0c752d4

[seblabbe]

comment:26

• What is the modpi arguments. What is a rotation of angle pi 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.

Ok, so tell me if it is better now.

[videlec]

comment:27

Replying to @seblabbe:

• What is the modpi arguments. What is a rotation of angle pi 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.

Ok, so tell me if it is better now.

A bit. What do you mean by the rectangular parallelepiped? There is only one? As far as I understand it is the isometry group that preserves any rectangular parallelepiped. You can also say differently: the group of orientable isometry that preserve (globally) each axis. Is that right?

And as before, this is the group generated by these rotation and not only thes rotations themselves (except in dim 2 and 3).

Isn't this group exactly the subgroup of matrices with an even number of -1 on the diagonal? So the quotient is just the signed permutation matrices with either 0 or 1 coefficient -1 (all others being 1). Isn't it?

When orientation_preserving is False I guess this group is the subgroup of matrices with any number of -1 on the diagonal. In that case, the quotient would just be the permutation matrices. No?

[videlec]

comment:28

And when you say that is by rotations of angle pi this is confusing since there are infinitely many of them. You can say by rotations of angle pi on the plane generated by two axes.

[seblabbe]

comment:29

A bit. What do you mean by the rectangular parallelepiped? There is only one?

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.

As far as I understand it is the isometry group that preserves any rectangular parallelepiped.

You understand well.

You can also say differently: the group of orientable isometry that preserve (globally) each axis. Is that right?

Yes.

And as before, this is the group generated by these rotation and not only thes rotations themselves (except in dim 2 and 3).

Of course. "modpi" is in the sense of modulo a group.

Isn't this group exactly the subgroup of matrices with an even number of -1 on the diagonal?

Yes.

So the quotient is just the signed permutation matrices with either 0 or 1 coefficient -1 (all others being 1). Isn't it?

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.

When orientation_preserving is False I guess this group is the subgroup of matrices with any number of -1 on the diagonal. In that case, the quotient would just be the permutation matrices. No?

Yes! You are right.

[seblabbe]

comment:30

So the quotient is just the signed permutation matrices with either 0 or 1 coefficient -1 (all others being 1). Isn't it?

When orientation_preserving=True, 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.

[seblabbe]

comment:31

So the quotient is just the signed permutation matrices with either 0 or 1 coefficient -1 (all others being 1). Isn't it?

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.

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.

For example, these representatives do not form a group:

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

But these representatives forms a group:

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

And I still don't know how to construct the quotient when n is even.

[seblabbe]

comment:32

Okay, so it is a chance that it works for when n is odd because in general:

http://groupprops.subwiki.org/wiki/Quotient_group_need_not_be_isomorphic_to_any_subgroup

[seblabbe]

comment:33

Ok, now I understand why I needed it that way.

Wait. I really need the quotient itself finally. I was just lucky that the transformation keeping some the pentamino invariant was in the group.

    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]
    ])]

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.

Give me more time. I'll update my branch.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a51e4d8	Using cosets for when modpi=True
dc3797b	Change pentaminos to there canonical form

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0c752d4 to dc3797b

[seblabbe]

comment:35

Re-needs review.