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

[sagetrac-git]

Changed commit from a86b42d to 6fd4a87

[sagetrac-git]

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]

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

[sagetrac-git]

Changed commit from 3c11961 to b370fd0

[sagetrac-git]

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:58

Replying to @seblabbe:

Moreover, everything would be faster if you would store integer vectors instead of tuples (and an attribute self._free_module). Why aren't you doing that?

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

2. Because it is not the purpose of this ticket.

I opened #19036

[sagetrac-git]

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

df65587

Trac #18987: Moved the paralel computation of nb of sol in dancing links module

[sagetrac-git]

Changed commit from 0d68ece to df65587

[seblabbe]

comment:60

(I will not have access to a machine with Sage for the next 7 days).

[seblabbe]

comment:61

Ok, Vincent. I am now back and available to do the follow up on this ticket.

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?

Sébastien

[seblabbe]

comment:62

I finally decided to split this ticket into two to ease the review. The second part is now available at #19107.

[sagetrac-git]

Changed commit from df65587 to c016126

[sagetrac-git]

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

8db8f72	Trac #18987: Number of solutions method for dancing links
9d25f7c	Trac #18987: doc + optim in dancing_links
c016126	Trac #18987: parallel computations in dancing links

[videlec]

comment:65

• (solving) independant (cases) -> independent
• I do not understand this comment

If possible, a good choice of column gives a partition
of solutions where each part has about the same number
of solutions.

• could you make a complete sentence for the OUTPUT section instead of dict, row number -> list of rows
• this is not quite accurate

After the split each subproblem has the same number of columns and
rows and the same solutions as above::

it is the union of solutions of the subproblems that form the solution of the initial one.

• I do not see the point of having number_of_solutions_iterator and number_of_solutions. You should just get rid of the first one and allow parallelization in the second.
• Why not also make available parallelization for getting the list of solutions?

[sagetrac-git]

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

29ff986

Trac #18987: Fixed reviewer comment 65

[sagetrac-git]

Changed commit from c016126 to 29ff986

[seblabbe]

comment:67

Thanks for your review! I fixed the first comments.

• I do not see the point of having number_of_solutions_iterator and number_of_solutions. You should just get rid of the first one and allow parallelization in the second.

• number_of_solutions_iterator is now _number_of_solutions_iterator
• number_of_solutions now allows parallel computation
• I kept _number_of_solutions_iterator because for the problem I am currently looking at, number_of_solutions takes days while _number_of_solutions_iterator 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 _number_of_solutions_iterator and adding some verbose thing in number_of_solutions.

• Why not also make available parallelization for getting the list of solutions?

Because I don't know how or if it is possible to use the parallel decorator to merge iterators.

[videlec]

comment:68

Salut Sebastien,

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.

Vincent

[vbraun]

Changed branch from public/18987 to 29ff986