9
$\begingroup$

I'm looking for ways to speed up calculation of a integral with a many-terms integrant. The obvious way is to go in parallel. I was surprised, but for some tests integration by ParallelMap over each term wasn't faster than one-core Integrate function.

I went further and made a small study. I tested a few methods of integration:

  1. Standart Integrate without any modification
  2. Integrate inside one-core Map
  3. Integrate inside ParallelMap with different methods of parallelization
  4. A "smart" parallelization: first split the sum into subsums, number of them is equal to the number of parallel kernels (4 kernels in my case), and then integrate the subsums in parallel.

The code and the results are:

runTest[n_] := With[{terms = Sum[a[i] z^i, {i, n}]},
  With[{newterms = Plus @@@ Partition[List @@ term, n/$KernelCount]},
   {{"Integrate",
      First[AbsoluteTiming[Integrate[terms, {z, 0, z}];]]},
    {"Map",
      First[AbsoluteTiming[Map[Integrate[#, {z, 0, z}] &, terms];]]},
    {"ParallelMap (Automatic)",
      First[AbsoluteTiming[ParallelMap[Integrate[#, {z, 0, z}] &, terms];]]},
    {"ParallelMap (FinestGrained)",
      First[AbsoluteTiming[ParallelMap[Integrate[#, {z, 0, z}] &, terms, Method -> "FinestGrained"];]]},
    {"ParallelMap (CoersestGrained)",
      First[AbsoluteTiming[ParallelMap[Integrate[#, {z, 0, z}] &, terms, Method -> "CoarsestGrained"];]]},
    {"Partition & ParallelMap",
      First[AbsoluteTiming[Plus @@ ParallelMap[Integrate[#, {z, 0, z}] &, newterms];]]}}
   ]]

numOfSamples = 75;
Monitor[test = Table[runTest[n], {n, $KernelCount, numOfSamples $KernelCount, $KernelCount}];, n]

With[{data = Transpose[test[[All, All, 2]]],
      names = test[[1, All, 1]]},
ListPlot[data,DataRange -> {$KernelCount, numOfSamples $KernelCount},
         PlotRange -> All, PlotLegends -> names, PlotTheme -> "Detailed",
         AxesLabel -> {"Number of terms", "Time, s"}]
]

enter image description here

There are a couple of interesting things on the plot. First, the Integrate function knows its job and works fine on one kernel (better than most parallelized versions). Second, all mapped versions has a linear dependence on number of terms (not surprising due to simple integrants). Third, comparison of Map and ParallelMap (FinestGrained) gives a good expamle of inappropriate parallelization. Fourth, and here I'm surprised, the ParallelMap (CoersestGrained) and Partition & ParallelMap have a significant difference in speed.
The only explanation I have is that ParallelMap (CoersestGrained) still works term-by-term, and Partition & ParallelMap uses power of internal algorithms of Integrate.

My questions are:

  • Is my last guess correct?
  • Is the Partition & ParallelMap method the most simple and fast? Or one can use ParallelMap for this problem in a smarter way (not just changing the method of parallelization)?
$\endgroup$
  • $\begingroup$ This is a very nice comparison of methods (+1). The reason why Integrate is so much better at handling a bunch of terms at a time instead of term by term as determined by some version of Map is probably because of the overhead involved in integrating an expression. You incur some overhead each time you call Integrate and this adds up. This is how it often is; you want to let Mathematica's built-in functions work as much as possibly by themselves, so I'm not really surprised about only Integrate versus Partition & ParallelMap. FinestGrained however is surprising, I think. $\endgroup$ – C. E. Apr 6 '15 at 0:30

Browse other questions tagged or ask your own question.