Optimising the Selection of MaxValue in Association

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.


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.


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
]