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
]