3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are all functions sums of squares, and the coefficient of u the same? If not, are there any other commonalities among the functions? $\endgroup$ – bbgodfrey Aug 3 '17 at 23:37
  • $\begingroup$ 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]. $\endgroup$ – bbgodfrey Aug 4 '17 at 0:43
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ typo in D[fun[[1, 1]], u, u] ah nvm you already fixed it $\endgroup$ – Alucard Aug 4 '17 at 4:06
  • $\begingroup$ @Alucard Yeah, had to re-run the timings, too. Just to be sure. $\endgroup$ – aardvark2012 Aug 4 '17 at 4:08
  • $\begingroup$ 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 $\endgroup$ – Alucard Aug 4 '17 at 4:15
  • $\begingroup$ 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. $\endgroup$ – aardvark2012 Aug 4 '17 at 4:21
  • $\begingroup$ 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. $\endgroup$ – Alucard Aug 4 '17 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.