# Improving the efficiency of applying FindMinimum to a very large table

I am working with a large table that has around 200,000 elements. Each element is a function of a single variable u. For example, one element looks like

(0.003 - 416.35 u)^2 + (0.0019 - 416.35 u)^2 + (0.005 + 416.35 u)^2 +
(0.0012 + 416.35 u)^2


I need to find the minimum of each element in fun. I have been using FindMinimum in the following way (where fun is a table of dimensions ~ 2000*100):

Minfun =
ParallelTable[FindMinimum[fun[[i, j]], {u, 0}], {i, 1, m}, {j, 1, n}];


This takes a few hours to do and I need to do this for multiple tables of functions.

Is there a significantly more efficient way to minimize many functions in the way I have described?

• Are all functions sums of squares, and the coefficient of u the same? If not, are there any other commonalities among the functions? Aug 3, 2017 at 23:37
• With the first expression in the question designated f, Solve[D[f, u] == 0, u] is an order of magnitude faster than FindMinimum[f, u]. Aug 4, 2017 at 0:43

First, let's set up a (smaller) table with the functions in. I'm assuming they're all similar to the one you posted, but the results don't rely on that.

m = 50; n = 50;
fun = Table[
Total[(#[[1]] - #[[2]] u)^2 & /@
Transpose[{RandomReal[0.01, 4],
ConstantArray[RandomReal[500], 4]}]], {m}, {n}];


There are three obvious possibilities: FindMinimum, FindArgMin and Solve (where, in the latter, you find zeros of the derivative at which the second derivative is positive).

AbsoluteTiming[
fminres =
Table[u /. Last@FindMinimum[fun[[i, j]], {u, 0}], {i, m}, {j, n}];]
AbsoluteTiming[
fargminres =
Table[First@FindArgMin[fun[[i, j]], {u, 0}], {i, m}, {j, n}];]
AbsoluteTiming[
solres = Table[
u /. First@
Solve[{D[fun[[i, j]], u] == 0, D[fun[[i, j]], u, u] > 0},
u], {i, m}, {j, n}];]

(* {13.2571, Null} *)
(* {13.2213, Null} *)
(* {0.316872, Null} *)


Also check

fminres == fargminres == solres
(* True *)


So there's a pretty clear winner there. You may be able improve slightly on your parallelization by setting the Method -> "CoarsestGrained"

ParallelTable[
u /. First@
Solve[{D[fun[[i, j]], u] == 0, D[fun[[i, j]], u, u] > 0}, u], {i,
m}, {j, n}]; // RepeatedTiming
ParallelTable[
u /. First@
Solve[{D[fun[[i, j]], u] == 0, D[fun[[i, j]], u, u] > 0}, u], {i,
m}, {j, n}, Method -> "CoarsestGrained"]; // RepeatedTiming

(* {0.13, Null} *)
(* {0.12, Null} *)


Not a huge difference by any stretch. It may be more pronounced for larger matrices, or it may get washed out. Still, something you can try.

If there is a clear structure to all the functions in your matrix you may well be able to improve on this substantially. In the extreme, if you can find a general solution then all you have to do is plug in values and you'll be done much faster.

• typo in D[fun[[1, 1]], u, u] ah nvm you already fixed it Aug 4, 2017 at 4:06
• @Alucard Yeah, had to re-run the timings, too. Just to be sure. Aug 4, 2017 at 4:08
• AbsoluteTiming[ ParallelTable[ Solve[D[fun[[i, j]] == 0, u ]], {i, 1, m}, {j, 1, n} ];]  is slower than the third one but faster than the other 2 Aug 4, 2017 at 4:15
• Finding zeros of the derivative would also find maxima. The functions in the array might only have a single minimum, but I didn't want to assume that. It would be a good example of using the form of the functions to get a speed up. Also, I wasn't using ParallelTable in the first round of tests. Aug 4, 2017 at 4:21
• i added the condition on the second derivative like you did and now, aside the parallelTable, the function is almost identical to the one you wrote. it remains slower though and i don't get why since the workload is now distributed on 4 cores. Aug 4, 2017 at 4:32