4
$\begingroup$

Suppose I have the following Association: 

f=<|"vanilla:veal" -> (353.073 x + 1137.02 x^2 + 2301.78 x^3 + 
     3771.09 x^4 + 5369.78 x^5 + 6302.43 x^6 + 6703.86 x^7 + 
     6518.57 x^8 + 5440.72 x^9 + 4612.02 x^10 + 3457.49 x^11 + 
     2654.9 x^12 + 2100.02 x^13 + 1521.13 x^14 + 1076.02 x^15 + 
     755.953 x^16 + 480.615 x^17 + 261.089 x^18 + 204.306 x^19 + 
     110.874 x^20 + 55.7565 x^21 + 28.2723 x^22 + 28.1937 x^23 + 
     19.6806 x^24 + 5.60733 x^25 + 3.72775 x^26 + 0.929319 x^27 + 
     1.8534 x^28 + 2.77225 x^29 + 0.921466 x^30 + 
     1.8377 x^31)/(354 x + 1143 x^2 + 2320 x^3 + 3811 x^4 + 
     5441 x^5 + 6403 x^6 + 6829 x^7 + 6658 x^8 + 5571 x^9 + 
     4737 x^10 + 3560 x^11 + 2741 x^12 + 2174 x^13 + 1579 x^14 + 
     1120 x^15 + 789 x^16 + 502 x^17 + 275 x^18 + 215 x^19 + 
     117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 21 x^24 + 6 x^25 + 
     4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 2 x^31), 
 "leek:white_wine" -> (353.073 x + 1137.02 x^2 + 2301.78 x^3 + 
     3772.08 x^4 + 5369.78 x^5 + 6306.37 x^6 + 6699.93 x^7 + 
     6523.46 x^8 + 5443.65 x^9 + 4606.18 x^10 + 3463.31 x^11 + 
     2651.02 x^12 + 2101.95 x^13 + 1520.17 x^14 + 1073.14 x^15 + 
     755.953 x^16 + 476.793 x^17 + 264.901 x^18 + 202.406 x^19 + 
     111.822 x^20 + 53.8665 x^21 + 29.2147 x^22 + 27.2539 x^23 + 
     19.6806 x^24 + 5.60733 x^25 + 3.72775 x^26 + 0.929319 x^27 + 
     1.8534 x^28 + 2.77225 x^29 + 0.921466 x^30 + 
     1.8377 x^31)/(354 x + 1143 x^2 + 2320 x^3 + 3811 x^4 + 
     5441 x^5 + 6403 x^6 + 6829 x^7 + 6658 x^8 + 5571 x^9 + 
     4737 x^10 + 3560 x^11 + 2741 x^12 + 2174 x^13 + 1579 x^14 + 
     1120 x^15 + 789 x^16 + 502 x^17 + 275 x^18 + 215 x^19 + 
     117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 21 x^24 + 6 x^25 + 
     4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 2 x^31), 
 "orange:shiitake" -> (353.073 x + 1137.02 x^2 + 2301.78 x^3 + 
     3771.09 x^4 + 5369.78 x^5 + 6302.43 x^6 + 6703.86 x^7 + 
     6518.57 x^8 + 5440.72 x^9 + 4612.02 x^10 + 3457.49 x^11 + 
     2655.86 x^12 + 2099.05 x^13 + 1521.13 x^14 + 1076.02 x^15 + 
     755.953 x^16 + 479.66 x^17 + 262.995 x^18 + 203.356 x^19 + 
     110.874 x^20 + 55.7565 x^21 + 28.2723 x^22 + 28.1937 x^23 + 
     19.6806 x^24 + 5.60733 x^25 + 3.72775 x^26 + 0.929319 x^27 + 
     1.8534 x^28 + 2.77225 x^29 + 0.921466 x^30 + 
     1.8377 x^31)/(354 x + 1143 x^2 + 2320 x^3 + 3811 x^4 + 
     5441 x^5 + 6403 x^6 + 6829 x^7 + 6658 x^8 + 5571 x^9 + 
     4737 x^10 + 3560 x^11 + 2741 x^12 + 2174 x^13 + 1579 x^14 + 
     1120 x^15 + 789 x^16 + 502 x^17 + 275 x^18 + 215 x^19 + 
     117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 21 x^24 + 6 x^25 + 
     4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 2 x^31), 
 "pepper:smoked_sausage" -> (353.073 x + 1137.02 x^2 + 2301.78 x^3 + 
     3773.07 x^4 + 5370.77 x^5 + 6303.41 x^6 + 6708.77 x^7 + 
     6522.48 x^8 + 5432.91 x^9 + 4612.02 x^10 + 3461.37 x^11 + 
     2650.05 x^12 + 2100.02 x^13 + 1520.17 x^14 + 1075.06 x^15 + 
     754.037 x^16 + 481.571 x^17 + 262.042 x^18 + 203.356 x^19 + 
     109.927 x^20 + 55.7565 x^21 + 28.2723 x^22 + 28.1937 x^23 + 
     19.6806 x^24 + 5.60733 x^25 + 3.72775 x^26 + 0.929319 x^27 + 
     1.8534 x^28 + 2.77225 x^29 + 0.921466 x^30 + 
     1.8377 x^31)/(354 x + 1143 x^2 + 2320 x^3 + 3811 x^4 + 
     5441 x^5 + 6403 x^6 + 6829 x^7 + 6658 x^8 + 5571 x^9 + 
     4737 x^10 + 3560 x^11 + 2741 x^12 + 2174 x^13 + 1579 x^14 + 
     1120 x^15 + 789 x^16 + 502 x^17 + 275 x^18 + 215 x^19 + 
     117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 21 x^24 + 6 x^25 + 
     4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 2 x^31), 
 "carrot:celery" -> (353.073 x + 1137.02 x^2 + 2301.78 x^3 + 
     3787.92 x^4 + 5375.7 x^5 + 6322.12 x^6 + 6740.18 x^7 + 
     6545.98 x^8 + 5464.16 x^9 + 4600.34 x^10 + 3451.66 x^11 + 
     2659.74 x^12 + 2084.56 x^13 + 1512.46 x^14 + 1049.12 x^15 + 
     733.916 x^16 + 467.238 x^17 + 254.419 x^18 + 199.555 x^19 + 
     107.084 x^20 + 47.2513 x^21 + 31.0995 x^22 + 23.4948 x^23 + 
     18.7435 x^24 + 5.60733 x^25 + 3.72775 x^26 + 0.929319 x^27 + 
     0.926702 x^28 + 2.77225 x^29 + 1.84293 x^30 + 
     0.918848 x^31)/(354 x + 1143 x^2 + 2320 x^3 + 3811 x^4 + 
     5441 x^5 + 6403 x^6 + 6829 x^7 + 6658 x^8 + 5571 x^9 + 
     4737 x^10 + 3560 x^11 + 2741 x^12 + 2174 x^13 + 1579 x^14 + 
     1120 x^15 + 789 x^16 + 502 x^17 + 275 x^18 + 215 x^19 + 
     117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 21 x^24 + 6 x^25 + 
     4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 2 x^31), 
 "cane_molasses:cumin" -> (353.073 x + 1137.02 x^2 + 2303.76 x^3 + 
     3769.12 x^4 + 5371.76 x^5 + 6304.4 x^6 + 6706.81 x^7 + 
     6518.57 x^8 + 5447.56 x^9 + 4618.84 x^10 + 3458.46 x^11 + 
     2655.86 x^12 + 2105.81 x^13 + 1514.39 x^14 + 1076.98 x^15 + 
     749.246 x^16 + 479.66 x^17 + 255.372 x^18 + 208.107 x^19 + 
     108.031 x^20 + 51.9764 x^21 + 24.5026 x^22 + 28.1937 x^23 + 
     18.7435 x^24 + 5.60733 x^25 + 2.79581 x^26 + 0.929319 x^27 + 
     2.7801 x^28 + 2.77225 x^29 + 1.8377 x^31)/(354 x + 1143 x^2 + 
     2320 x^3 + 3811 x^4 + 5441 x^5 + 6403 x^6 + 6829 x^7 + 
     6658 x^8 + 5571 x^9 + 4737 x^10 + 3560 x^11 + 2741 x^12 + 
     2174 x^13 + 1579 x^14 + 1120 x^15 + 789 x^16 + 502 x^17 + 
     275 x^18 + 215 x^19 + 117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 
     21 x^24 + 6 x^25 + 4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 
     2 x^31), 
 "lettuce:turnip" -> (353.073 x + 1137.02 x^2 + 2301.78 x^3 + 
     3771.09 x^4 + 5369.78 x^5 + 6302.43 x^6 + 6703.86 x^7 + 
     6519.54 x^8 + 5438.77 x^9 + 4612.99 x^10 + 3457.49 x^11 + 
     2654.9 x^12 + 2100.02 x^13 + 1521.13 x^14 + 1076.02 x^15 + 
     755.953 x^16 + 479.66 x^17 + 262.042 x^18 + 204.306 x^19 + 
     110.874 x^20 + 55.7565 x^21 + 28.2723 x^22 + 28.1937 x^23 + 
     19.6806 x^24 + 5.60733 x^25 + 3.72775 x^26 + 0.929319 x^27 + 
     1.8534 x^28 + 2.77225 x^29 + 0.921466 x^30 + 
     1.8377 x^31)/(354 x + 1143 x^2 + 2320 x^3 + 3811 x^4 + 
     5441 x^5 + 6403 x^6 + 6829 x^7 + 6658 x^8 + 5571 x^9 + 
     4737 x^10 + 3560 x^11 + 2741 x^12 + 2174 x^13 + 1579 x^14 + 
     1120 x^15 + 789 x^16 + 502 x^17 + 275 x^18 + 215 x^19 + 
     117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 21 x^24 + 6 x^25 + 
     4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 2 x^31), 
 "corn_grit:pork_sausage" -> (353.073 x + 1137.02 x^2 + 2302.77 x^3 + 
     3771.09 x^4 + 5371.76 x^5 + 6301.45 x^6 + 6701.9 x^7 + 
     6519.54 x^8 + 5439.75 x^9 + 4612.99 x^10 + 3457.49 x^11 + 
     2654.9 x^12 + 2100.98 x^13 + 1519.2 x^14 + 1076.02 x^15 + 
     755.953 x^16 + 479.66 x^17 + 262.042 x^18 + 204.306 x^19 + 
     110.874 x^20 + 55.7565 x^21 + 28.2723 x^22 + 28.1937 x^23 + 
     19.6806 x^24 + 5.60733 x^25 + 3.72775 x^26 + 0.929319 x^27 + 
     2.7801 x^28 + 1.84817 x^29 + 0.921466 x^30 + 
     1.8377 x^31)/(354 x + 1143 x^2 + 2320 x^3 + 3811 x^4 + 
     5441 x^5 + 6403 x^6 + 6829 x^7 + 6658 x^8 + 5571 x^9 + 
     4737 x^10 + 3560 x^11 + 2741 x^12 + 2174 x^13 + 1579 x^14 + 
     1120 x^15 + 789 x^16 + 502 x^17 + 275 x^18 + 215 x^19 + 
     117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 21 x^24 + 6 x^25 + 
     4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 2 x^31), 
 "avocado:pumpkin" -> (353.073 x + 1137.02 x^2 + 2301.78 x^3 + 
     3771.09 x^4 + 5369.78 x^5 + 6303.41 x^6 + 6702.88 x^7 + 
     6518.57 x^8 + 5440.72 x^9 + 4612.02 x^10 + 3457.49 x^11 + 
     2654.9 x^12 + 2100.02 x^13 + 1521.13 x^14 + 1076.02 x^15 + 
     755.953 x^16 + 479.66 x^17 + 262.042 x^18 + 204.306 x^19 + 
     110.874 x^20 + 55.7565 x^21 + 28.2723 x^22 + 28.1937 x^23 + 
     19.6806 x^24 + 5.60733 x^25 + 3.72775 x^26 + 0.929319 x^27 + 
     1.8534 x^28 + 2.77225 x^29 + 0.921466 x^30 + 
     1.8377 x^31)/(354 x + 1143 x^2 + 2320 x^3 + 3811 x^4 + 
     5441 x^5 + 6403 x^6 + 6829 x^7 + 6658 x^8 + 5571 x^9 + 
     4737 x^10 + 3560 x^11 + 2741 x^12 + 2174 x^13 + 1579 x^14 + 
     1120 x^15 + 789 x^16 + 502 x^17 + 275 x^18 + 215 x^19 + 
     117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 21 x^24 + 6 x^25 + 
     4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 2 x^31), 
 "chive:mandarin_peel" -> (353.073 x + 1137.02 x^2 + 2301.78 x^3 + 
     3771.09 x^4 + 5369.78 x^5 + 6302.43 x^6 + 6704.84 x^7 + 
     6517.59 x^8 + 5439.75 x^9 + 4612.99 x^10 + 3457.49 x^11 + 
     2654.9 x^12 + 2100.02 x^13 + 1521.13 x^14 + 1076.02 x^15 + 
     755.953 x^16 + 479.66 x^17 + 262.042 x^18 + 204.306 x^19 + 
     110.874 x^20 + 55.7565 x^21 + 28.2723 x^22 + 28.1937 x^23 + 
     19.6806 x^24 + 5.60733 x^25 + 3.72775 x^26 + 0.929319 x^27 + 
     1.8534 x^28 + 2.77225 x^29 + 0.921466 x^30 + 
     1.8377 x^31)/(354 x + 1143 x^2 + 2320 x^3 + 3811 x^4 + 
     5441 x^5 + 6403 x^6 + 6829 x^7 + 6658 x^8 + 5571 x^9 + 
     4737 x^10 + 3560 x^11 + 2741 x^12 + 2174 x^13 + 1579 x^14 + 
     1120 x^15 + 789 x^16 + 502 x^17 + 275 x^18 + 215 x^19 + 
     117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 21 x^24 + 6 x^25 + 
     4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 2 x^31), 
 "anise_seed:coconut" -> (353.073 x + 1137.02 x^2 + 2301.78 x^3 + 
     3771.09 x^4 + 5369.78 x^5 + 6302.43 x^6 + 6703.86 x^7 + 
     6518.57 x^8 + 5439.75 x^9 + 4612.99 x^10 + 3457.49 x^11 + 
     2654.9 x^12 + 2100.98 x^13 + 1521.13 x^14 + 1075.06 x^15 + 
     755.953 x^16 + 479.66 x^17 + 262.042 x^18 + 204.306 x^19 + 
     110.874 x^20 + 55.7565 x^21 + 28.2723 x^22 + 28.1937 x^23 + 
     19.6806 x^24 + 5.60733 x^25 + 3.72775 x^26 + 0.929319 x^27 + 
     1.8534 x^28 + 2.77225 x^29 + 0.921466 x^30 + 
     1.8377 x^31)/(354 x + 1143 x^2 + 2320 x^3 + 3811 x^4 + 
     5441 x^5 + 6403 x^6 + 6829 x^7 + 6658 x^8 + 5571 x^9 + 
     4737 x^10 + 3560 x^11 + 2741 x^12 + 2174 x^13 + 1579 x^14 + 
     1120 x^15 + 789 x^16 + 502 x^17 + 275 x^18 + 215 x^19 + 
     117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 21 x^24 + 6 x^25 + 
     4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 2 x^31)|>

which contains rational functions. I want to select the ones that have y value above 1 for a specific range of x, so I do: 

Select[f, MaxValue[{#, 2/382 <= x <= 1}, x] > 1 &] // AbsoluteTiming

in this case none of them are, so I get: 

{1.80393, <||>}

The point is that my original list contains 30000 of these polynomials and the command I have for selection is taking a lot of time. For 10 of them as above it took 1.8 seconds. I wonder how can I break this time down without losing the dictionary, namely what key is related to what polynomial?

I know if I only look at values the time would be reduced, but then I will not know the output would belong to which key from the association.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ If you have 8 cores, and use ParallelTable, that would take less than 12 minutes. Is that too long? $\endgroup$
    – rhermans
    Commented Jul 17, 2019 at 16:14
  • $\begingroup$ I have 4 so presume it will take 24', is there any way to chunk the code down into easier-to-handle part? $\endgroup$
    – Wiliam
    Commented Jul 17, 2019 at 16:23
  • $\begingroup$ For all of the polynomials you give, the maximum lies at the lower edge of your search interval. Maybe there's something generalizable here: maybe it's possible to exclude a large number of polynomials by just looking at the values (and derivatives) at the end points. $\endgroup$
    – Roman
    Commented Jul 17, 2019 at 18:15

3 Answers 3

Reset to default
4
$\begingroup$

This would take less than 25 minutes with 4 cores.

LaunchKernels[];
maxlist = ParallelTable[
   MaxValue[{eq, 2/382 <= x <= 1}, x]
   , {eq, List @@ f}
  ];

Pick[
 Keys[f],
 Thread[Greater[maxlist, 1]]
]

My take on the answer by Carl Woll, which should bring you below 6 minutes.

trueFalseList = ParallelTable[
  UnsameQ[
   False,
   Quiet[
    Reduce[eq > 1 && 2/382 <= x <= 1, x]
    , Reduce::ratnz]
   ], {eq, List @@ f}]

Pick[
 Keys[f],
 trueFalseList
]
Improve this answer
$\endgroup$
1
  • $\begingroup$ The second method is fabulously fast, thank you and Carl Woll. $\endgroup$
    – Wiliam
    Commented Jul 18, 2019 at 11:14
6
$\begingroup$

Maybe you can use Reduce instead of MaxValue. For instance, the "vanilla:veal" rational function is:

p = (353.073 x + 1137.02 x^2 + 2301.78 x^3 + 
 3771.09 x^4 + 5369.78 x^5 + 6302.43 x^6 + 6703.86 x^7 + 
 6518.57 x^8 + 5440.72 x^9 + 4612.02 x^10 + 3457.49 x^11 + 
 2654.9 x^12 + 2100.02 x^13 + 1521.13 x^14 + 1076.02 x^15 + 
 755.953 x^16 + 480.615 x^17 + 261.089 x^18 + 204.306 x^19 + 
 110.874 x^20 + 55.7565 x^21 + 28.2723 x^22 + 28.1937 x^23 + 
 19.6806 x^24 + 5.60733 x^25 + 3.72775 x^26 + 0.929319 x^27 + 
 1.8534 x^28 + 2.77225 x^29 + 0.921466 x^30 + 
 1.8377 x^31)/(354 x + 1143 x^2 + 2320 x^3 + 3811 x^4 + 
 5441 x^5 + 6403 x^6 + 6829 x^7 + 6658 x^8 + 5571 x^9 + 
 4737 x^10 + 3560 x^11 + 2741 x^12 + 2174 x^13 + 1579 x^14 + 
 1120 x^15 + 789 x^16 + 502 x^17 + 275 x^18 + 215 x^19 + 
 117 x^20 + 59 x^21 + 30 x^22 + 30 x^23 + 21 x^24 + 6 x^25 + 
 4 x^26 + x^27 + 2 x^28 + 3 x^29 + x^30 + 2 x^31)

Compare:

MaxValue[{p, 2/382 <= x <= 1}, x] //AbsoluteTiming
Quiet[Reduce[p > 1 && 2/382 <= x <= 1, x], Reduce::ratnz] //AbsoluteTiming

{0.133098, 0.976077}

{0.041712, False}

Another example where the result isn't false:

MaxValue[{p+.5, 2/382 <= x <= 1}, x] //AbsoluteTiming
Quiet[Reduce[p+.5 > 1 && 2/382 <= x <= 1, x], Reduce::ratnz] //AbsoluteTiming

{0.128614, 1.47608}

{0.041923, 0.0390256 < x <= 1.}

So, using Reduce is about 3 times faster. Combine it with a ParallelTable approach as in @rherman's answer.

Improve this answer
$\endgroup$
5
$\begingroup$

The following is not the exact filter that you want, but a simple prefilter that apparently is quite good at filtering the given example ;) The point is that this check is much cheaper than computing the maxima, so it can be used to filter out (hopefully) many rational functions from your list f, so that filtering the resulting list becomes less expensive.

Here is the code:

a = 2./382;
b = 1.;
picker =
    ParallelMap[
     With[{x = a + (b - a) z/(1 + z)},
       With[{p = Together[#]},
        Min[CoefficientList[Denominator[r] - Numerator[r], z]] < 0.
        ]
       ] &,
     Values[f]
     ]; // AbsoluteTiming // First

fpresieved = Pick[f, picker]

0.04817

<||>

Here is the idea behind the method.

Let $r(x)$ be a rational function from your list f. First, we apply the substitution x = a + (b - a) z/(1 + z); The mapping $z \mapsto x$ maps the $[0,\infty]$ to the interval $[a,b]$. Thus, $r = \frac{p}{q}$ is a rational function on the positive real axis for which we want to check whether

$$r(x) = \frac{p(z)}{q(z)} \leq 1 \quad \text{for all $z \geq 0$.}$$

This is equivalent to

$$q(z) - p(z) \geq 0 \quad \text{for all $z \geq 0$.}$$

A sufficient condition for this is that all coefficients of the polynomial $q(z) - p(z)$ are nonnegative. So a necessary condition for r(x) to be selected is that at least one coefficient of $q(z) - p(z)$ is negative. And precisely that is checked for in the code above.

Improve this answer
$\endgroup$

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.