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
$\endgroup$
2
  • 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
    Commented Sep 4, 2018 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
    Commented Sep 8, 2018 at 17:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.