5
$\begingroup$

I am generating the orbit of a partition of a set of size $n$ under the action of the symmetric group $S_n$. PermutationReplace won't allow itself to be parallelized. Why is this ? Is it because the Operating System is already multi-threading it ? Is there a way to parallelize it efficiently ? I tried the below, but my ugly attempt at parallelization led to slower code, not faster. My timing results were 0.26 seconds serially, and 3.83 seconds in parallel. I have 4 cores available.

n = 8;
partition = {{1, 3, 5}, {2}, {4, 7}, {6, 8}};
Parallelize[PermutationReplace[partition, SymmetricGroup[n]]];
starttime = TimeUsed[];
serial = PermutationReplace[partition, SymmetricGroup[n]];
endtime = TimeUsed[];
Print["Serial computation took ", endtime - starttime, " seconds."];
starttime = TimeUsed[];
parallel =
  ParallelTable[
   PermutationReplace[partition, permutation], {permutation,
    SymmetricGroup[n]}, Method -> "CoarsestGrained"];
endtime = TimeUsed[];
Print["Parallel computation took ", endtime - starttime,
  " seconds."];
serial == parallel
|improve this question
$\endgroup$
  • 1
    $\begingroup$ On my four-core PC running Windows 10, 64-bit, CPU usage never exceeds 22% for PermutationReplace, so I do not think that multi-treading occurs automatically in this case. If I launch the kernels before running Parallelize, the runtime with and without it about the same. ParallelTable fails as written in the code but appears to work for, ParallelTable[PermutationReplace[partition, permutation], {permutation, SymmetricGroup[n] // GroupElements}, Method -> "CoarsestGrained"]; but is very slow. $\endgroup$ – bbgodfrey Sep 4 '18 at 1:40
  • $\begingroup$ Many thanks @bbgodfrey for your input. Very interesting about the multi-threading. At present I follow my use of PermutationReplace with a use of DeleteDuplicates. I see that there is a command GroupOrbits that would seem to do the whole job in one command. I will experiment with GroupOrbits, and in particular, with whether it can be parallelized. $\endgroup$ – Simon Sep 8 '18 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.