The testing of the 4 methods' effectiveness, on the 200th knot in Dunfield' s list of knots .

<<KnotTheory`

Ks = ReadList["http://drorbn.net/AcademicPensieve/People/Dunfield/nmd_random_knots"]

testingKnotBig = Ks[[198]];

Length @ testingKnotBig

Timing[bestGreedy[testingKnotBig, {factor -> JonesResult, tries -> 1000}]][[1]]

This is the unparallelized version, comparing the run time with the 100 crossing knot, the estimate is that it will take about 20 seconds.

unselTableBig = Flatten[Table[bestGreedySamples[PD @@ testingKnotBig, {factor -> JonesResult, neededSamples ->1, tries -> 1000}], {i, 50}],1];

unselTableJonesBig = JonesResult[#] &/@ unselTableBig

Mean[unselTableJonesBig] * RunTimeConstant

Estimation of Run Time, similar to ModelRunTime

LM

Timing[localOptimization[PD @@ #, {startPt -> convertToList, invariantCriteria -> JonesOptimize, optSize ->6}] &/@ unselTableBig][[1]]

LOunselTableBig = localOptimization[PD @@ #, {startPt -> convertToList, invariantCriteria -> JonesOptimize, optSize ->6}] &/@ unselTableBig;

LOJonesBig = JonesResult[#] &/@ LOunselTableBig;

Mean[LOJonesBig] * RunTimeConstant

105.71 + 366.59 / 50

Timing[localOptimization[PD @@ #, {startPt -> convertToList, invariantCriteria -> JonesOptimize, optSize ->5}] &/@ unselTableBig][[1]]

LOunselTableSmallBig = localOptimization[PD @@ #, {startPt -> convertToList, invariantCriteria -> JonesOptimize, optSize ->5}] &/@ unselTableBig;

LOJonesSmallBig = JonesResult[#] &/@ LOunselTableSmallBig;

Mean[LOJonesSmallBig] * RunTimeConstant

118.1457394 + 49.890625`/50

PLM

Timing[partialLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->6, partialPortion -> 0.1, rounds -> 10}] &/@ unselTableBig][[1]]

PLOunselTableBig = partialLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->6, partialPortion -> 0.1, rounds -> 10}] &/@ unselTableBig;

PLOJonesBig = JonesResult[#] &/@ PLOunselTableBig;

Mean[PLOJonesBig] * RunTimeConstant

86.472 + 398.109375/50

Timing[partialLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->5, partialPortion -> 0.1, rounds -> 10}] &/@ unselTableBig][[1]]

PLOunselTableSmallBig = partialLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->5, partialPortion -> 0.1, rounds -> 10}] &/@ unselTableBig;

PLOJonesSmallBig = JonesResult[#] &/@ PLOunselTableSmallBig;

Mean[PLOJonesSmallBig] * RunTimeConstant

103.30386716` + 72.1875`/50

Timing[partialLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->5, partialPortion -> 0.2, rounds -> 5}] &/@ unselTableBig][[1]]

PLOunselTableSmallModBig = partialLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->5, partialPortion -> 0.2, rounds -> 5}] &/@ unselTableBig;

PLOJonesSmallModBig = JonesResult[#] &/@ PLOunselTableSmallModBig;

Mean[PLOJonesSmallModBig] * RunTimeConstant

97.47+62.73/50

RLM

Timing[reverseLocalOptimization[PD @@ #, {startPt -> convertToList, invariantCriteria -> JonesOptimize, optSize ->6}] &/@ unselTableBig][[1]]

RLOunselTableBig = reverseLocalOptimization[PD @@ #, {startPt -> convertToList, invariantCriteria -> JonesOptimize, optSize ->6}] &/@ unselTableBig;

RLOJonesBig = JonesResult[#] &/@ RLOunselTableBig;

Mean[RLOJonesBig] * RunTimeConstant

120.66 + 430.141/50

Timing[reverseLocalOptimization[PD @@ #, {startPt -> convertToList, invariantCriteria -> JonesOptimize, optSize ->5}] &/@ unselTableBig][[1]]

RLOunselTableSmallBig = reverseLocalOptimization[PD @@ #, {startPt -> convertToList, invariantCriteria -> JonesOptimize, optSize ->5}] &/@ unselTableBig;

RLOJonesSmallBig = JonesResult[#] &/@ RLOunselTableSmallBig;

Mean[RLOJonesSmallBig] * RunTimeConstant

133.61722867999998` + 125.6875`/50

RPLM

Protect[startPt, invariantCriteria, optSize, partialPortion, rounds];

Options[backwardsPLO] := {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize -> 3, partialPortion -> 0.1, rounds -> 3};

backwardsPLO[pd_PD, opts: OptionsPattern[backwardsPLO]] := 
Module[{s, k, sBest, optimizeList, optimizeResult, widths, width, round},
s = OptionValue[startPt][pd];
k = Length[s] - OptionValue[optSize] + 1;
round = 1;
sBest = s;
While[round ≤ OptionValue[rounds],
widths = FoldList[Complement [#1 ⋃ #2, #1 ⋂ #2] &, {}, List @@@ sBest];
While[k ≥ 1,
optimizeList = sBest[[k;;k+OptionValue[optSize] - 1]];
width =  widths[[k]];
optimizeResult = OptionValue[invariantCriteria][width, optimizeList,k, OptionValue[partialPortion]];
sBest = Join[If[k == 1, {}, sBest[[1;;k-1]]], optimizeResult, If[k == Length[s] - OptionValue[optSize] + 1, {}, sBest[[k + OptionValue[optSize];;-1]]]];
k = k - 1;
];
round = round + 1;
k  = Length[s] - OptionValue[optSize] + 1;
];
sBest]

Timing[backwardsPLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->6, partialPortion -> 0.1, rounds -> 10}] &/@ unselTableBig][[1]]

BPLOunselTableBig =  backwardsPLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->6, partialPortion -> 0.1, rounds -> 10}] &/@ unselTableBig;

BPLOJonesBig = JonesResult[#] &/@ BPLOunselTableBig;

Mean[BPLOJonesBig] * RunTimeConstant

80.77528264` + 379/50

Timing[backwardsPLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->5, partialPortion -> 0.1, rounds -> 10}] &/@ unselTableBig][[1]]

BPLOunselTableSmallBig =  backwardsPLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->5, partialPortion -> 0.1, rounds -> 10}] &/@ unselTableBig;

BPLOJonesSmallBig = JonesResult[#] &/@ BPLOunselTableSmallBig;

Mean[BPLOJonesSmallBig] * RunTimeConstant

92.38820032` + 65.375`/50

Timing[backwardsPLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->5, partialPortion -> 0.2, rounds -> 5}] &/@ unselTableBig][[1]]

BPLOunselTableSmallModBig =  backwardsPLO[PD @@ #, {startPt -> convertToList, invariantCriteria -> PartialJonesOptimize, optSize ->5, partialPortion -> 0.2, rounds -> 5}] &/@ unselTableBig;

BPLOJonesSmallModBig = JonesResult[#] &/@ BPLOunselTableSmallModBig;

Mean[BPLOJonesSmallModBig] * RunTimeConstant

95.94167544` + 59.5`/50

And similarly, what is the actual run time estimates looking like?

unselTableBigFKB = (# /. Global`X -> X) &/@ unselTableBig;

Timing[FKB[#]][[1]] &/@ unselTableBigFKB

Mean[{191.421875`,155.734375`,195.84375`,124.15625`,160.5`,258.703125`,158.796875`,123.40625`,183.078125`,222.671875`,246.171875`,210.1875`,181.140625`,157.9375`,124.53125`,162.8125`,199.`,139.53125`,170.734375`,86.9375`,250.578125`,136.578125`,231.171875`,178.53125`,224.796875`,253.421875`,243.34375`,200.515625`,220.1875`,131.1875`,124.578125`,149.09375`,64.1875`,241.90625`,183.015625`,164.75`,200.484375`,190.546875`,155.421875`,155.453125`,151.734375`,224.5`,176.59375`,135.5`,123.59375`,162.515625`,172.984375`,149.015625`,295.359375`,153.65625`}]

FKBTimeLOBig = Timing[FKB[#]][[1]] &/@ ((# /. Global`X -> X) &/@ LOunselTableBig);

Mean[FKBTimeLOBig]

366.59375`/50 + 108.121875`

FKBTimeLOSmallBig = Timing[FKB[#]][[1]] &/@ ((# /. Global`X -> X) &/@ LOunselTableSmallBig);

Mean[FKBTimeLOSmallBig]

117.2378125`+ 49.890625`/50

FKBTimePLOBig = Timing[FKB[#]][[1]] &/@ ((# /. Global`X -> X) &/@ PLOunselTableBig);

Mean[FKBTimePLOBig]

86.630625` + 398.109375`/50

FKBTimePLOSmallBig = Timing[FKB[#]][[1]] &/@ ((# /. Global`X -> X) &/@ PLOunselTableSmallBig);

Mean[FKBTimePLOSmallBig]

103.9821875` + 72.1875`/50

FKBTimePLOSmallModBig = Timing[FKB[#]][[1]] &/@ ((# /. Global`X -> X) &/@ PLOunselTableSmallModBig);

Mean[FKBTimePLOSmallModBig]

100.735` + 62.734375`/50

FKBTimeRLOBig = Timing[FKB[#]][[1]] &/@ ((# /. Global`X -> X) &/@ RLOunselTableBig);

Mean[FKBTimeRLOBig]

123.03+ 430.140625`/50

FKBTimeRLOSmallBig = Timing[FKB[#]][[1]] &/@ ((# /. Global`X -> X) &/@ RLOunselTableSmallBig);

Mean[FKBTimeRLOSmallBig]

132.26+ 125.6875/50

FKBTimeBPLOBig = Timing[FKB[#]][[1]] &/@ ((# /. Global`X -> X) &/@ BPLOunselTableBig);

Mean[FKBTimeBPLOBig]

82.74625`

82.74625` + 379.`/50

FKBTimeBPLOSmallBig = Timing[FKB[#]][[1]] &/@ ((# /. Global`X -> X) &/@ BPLOunselTableSmallBig);

Mean[FKBTimeBPLOSmallBig]

94.260625` + 65.375`/50

FKBTimeBPLOSmallModBig = Timing[FKB[#]][[1]] &/@ ((# /. Global`X -> X) &/@ BPLOunselTableSmallModBig);

Mean[FKBTimeBPLOSmallModBig]

97.56875` + 59.5`/50