1
$\begingroup$

I have the following calculation

k = 1; While[! (PolynomialMod[x^k - 1, poly , Modulus -> 2] === 0), k++]; k

where poly is a given polynomial. If the polynomial is simple, the calculation is done in under a second, so no problem at all.

However, if we use poly = 1 + x + x^2 + x^15 + x^16 + x^17 + x^18, then the calculation takes roughly 7 seconds in my machine. This is just an example of the problem. In reality, I want to calculate the k's for much harder polynomials, where the calculation takes hours (k being of order $10^6-10^8$).

The question: is there a way to parallelize this expression? For example, running this on a cluster with 40-50 kernels would speed up the calculations significantly (assuming that an efficient parallelization exists in the first place...). Furthermore, each kernel wouldn't need much allocated memory since each calculation is simple.


(Maybe some helpful information...)

We know a hard limit for k; it can't be bigger than order = 2^Exponent[poly, x] - 1. However, the issue here is that most of the times k is orders of magnitude smaller than order and it is not efficient at all to check all numbers till order and then find the first one being zero, for example, with a Table construction...

$\endgroup$
6
  • $\begingroup$ Consider evenly distributing starting $k$ values across the range of interest and accept the first successful response? $\endgroup$
    – eyorble
    Nov 23, 2022 at 2:07
  • $\begingroup$ Exactly, I was thinking about something similar, but I am not sure how to write this code efficiently... $\endgroup$
    – Kostas
    Nov 23, 2022 at 2:09
  • $\begingroup$ ParallelTry is the built-in infrastructure for it, so encapsulate the problem in a function which can be distributed to parallel kernels and use that. I haven't done it myself though, so I'm not planning to write up an answer for it. $\endgroup$
    – eyorble
    Nov 23, 2022 at 2:10
  • $\begingroup$ Thanks a lot for the help! I didn't know of ParallelTry!! $\endgroup$
    – Kostas
    Nov 23, 2022 at 2:20
  • $\begingroup$ so, I managed to get it work. However the results are pretty disappointing...First of all, I think the solution that you were refering to, @eyorble, is something like this ParallelTry[ If[PolynomialMod[x^# - 1, poly, Modulus -> 2] === 0, #, $Failed] &, Range[1, order]]. However, if order is bigger than $2^{11}-2^{12}$ my laptop crashes. The problem persists even to small sizes (the serial method is faster...). At the same time, I get a solution (inefficient, but still, it works...) with the serial method. Is there a way to optimize the parallelized version more? $\endgroup$
    – Kostas
    Nov 23, 2022 at 2:58

2 Answers 2

1
$\begingroup$

Code:

kernelFunction[poly_][{kstart_,kstop_}] := Catch[Do[
   If[PolynomialMod[x^k-1,poly,Modulus->2]===0,Throw[k]],
   {k,kstart,kstop}];Infinity];
DistributeDefinitions[kernelFunction];

try[poly_,imax_:Infinity,batchsize_:100] := With[{kstep=$KernelCount},
  Catch[Do[Min[ParallelMap[kernelFunction[poly],
    batchsize*((i-1)*kstep+Range[0,kstep])+1//Transpose[{Most[#],Rest[#]-1}]&,
    DistributedContexts->None]]//If[#<Infinity,Throw[#]]&,{i,1,imax}];
  Infinity]];

Timing:

poly = 1+x+x^2+x^15+x^16+x^17+x^18;

(* serial *)
kernelFunction[poly][{1,Infinity}] // AbsoluteTiming
(* {4.88467, 9709} *)

(* parallel *)
LaunchKernels[];
try[poly] // AbsoluteTiming
(* {1.0087, 9709} *)

where my $KernelCount was $8$.

$\endgroup$
9
  • $\begingroup$ Thank you very much for the solution!! After I did some extensive testing, I think that your code works really really well...My only concern is your last remark. So, there is a chance that I have maximum values up to $10^10$ for example and the code chooses randomly to run the value I want last. This would crash the universe...Is this a real possibility? From my testing I didn't encounter any problem like that though... $\endgroup$
    – Kostas
    Nov 23, 2022 at 19:00
  • $\begingroup$ values up to $10^{10}$, I meant... $\endgroup$
    – Kostas
    Nov 23, 2022 at 23:09
  • $\begingroup$ Updated. This new version should not have the issue mentioned in the first version. But it is also more complicated now, hence more likely to contain errors, please check yourself. $\endgroup$
    – user293787
    Nov 24, 2022 at 4:44
  • 1
    $\begingroup$ I tried both, and both are faster using the parallel code: from 9 seconds down to 2 seconds in the first case, from 14 down to 3 in the second case. You probably made some mistake, such as not clearing old definitions... Btw, also the people who mainly ask questions on this site should think of themselves as contributors, not merely consumers. You could do more than just say that it does not work. $\endgroup$
    – user293787
    Nov 24, 2022 at 9:19
  • 1
    $\begingroup$ Update: somehow, after a restart now I got from 20sec to 0.4sec for the same polynomial...(I don't know how can this be-I also made sure I don't have anything changed...). It seems that I now agree with your timings (or I even get better ones :)...) Thanks again! $\endgroup$
    – Kostas
    Nov 25, 2022 at 0:42
0
$\begingroup$

How about something like this:

LaunchKernels[];
With[{
  poly = 1 + x + x^2 + x^15 + x^16 + x^17 + x^18
  },
 ParallelTry[
  SelectFirst[
    Range @@ #,
    Function[k, 
      k =!= 0 && PolynomialMod[x^k - 1, poly, Modulus -> 2] === 0
    ],
    $Failed
  ]&,
  Partition[FindDivisions[{1, 10^6, 1}, Length @ Kernels[]], 2, 1]
 ]
]

One potential issue though: you're not guaranteed to get the lowest value of k this way. But I guess that's a somewhat inherent problem to parallelizing this kind of problem.

$\endgroup$
3
  • $\begingroup$ The issue you mention at the end was the reason why I updated my answer from this version to this one. $\endgroup$
    – user293787
    Nov 24, 2022 at 11:27
  • $\begingroup$ I tried running it for this polynomial 1 + x^7 + x^{10} - x^{11} + x^{13} - x^{14} + x^{15} + x^{16} - x^{17} + x^{18} - x^{20} + x^{21} + x^{24}. I run your code like this With[...]//Timing . The first time I have FindDivisions[{1, 10^6, 1}...]. The output is {1.5`, 758835}. The second time I run it with the max limit to FindDivisions[{1, 10^7, 1}...]. The output is {1.03125`, 7505568}. I am not really sure what is going on here...Am I missing anything? Do you get the same outputs? $\endgroup$
    – Kostas
    Nov 25, 2022 at 0:44
  • 1
    $\begingroup$ Like I said: it will find the first result across different kernels; not necessarily the lowest result. You'd need to use ParallelMap to find the lowest value. $\endgroup$ Nov 25, 2022 at 9:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.