Predict which sub-interval is the most complicated - numerical integration

Question

I wrote a small Android-App which integrates a function in a user-selectable interval [a,b]. Because I want to get the result as fast as possible I try to utilize every cpu core of the smartphone, therefore (at the current stage) I divide the interval [a,b] into equally big sub-intervals (depend on how many cpu cores the smartphone has) and then calculate the value with an adaptive-integration approach. I noticed, in case the user wants to integrate the e-Function from [0,6], one cpu-core has a lot more stuff to do because the slope is much higher in [4.5,6] than in [0,1.5], so I asked myself, how can I predict or calculate which sub-intervall is the most time consuming one or, even better, how can I split a given intervall [a,b] into 4 or 8 parts where every part is roughly of the same complexity?

Answer 1

I believe your stated goal is impossible to achieve in general. There is simply too much flexibility included in the set of continuous functions.

However, your real goal is to balance the load.

I suggest you apply a divide and conquer approach. Spawn $p$ threads and cut the interval into $p$ subintervals. While there are subintervals left, assign a subinterval to an idle thread. If the error tolerance is meet for a given subinterval, then add the contribution to the total, otherwise, split the subinterval in two and add those to the queue.

This sketch is not at all trivial to implement. Moreover, if the computational complexity of obtaining $f(x)$ can vary greatly with $x$, then it is possible to construct examples for which this strategy will fail spectacularly.

You may be better off treating one thread as the master, in charge of doing the adaptive quadrature and assign all the function evaluations to the slave threads.

I recommend that you think deeply about what class of functions you want to be able to handle well, run a search for "load balancing parallel numerical integration" as there are quite a few papers on this subject and, if necessary, post a new question to scicomp.stackexchange.com

You may find this paper helpful as it elaborates on the divide an conquer strategy mentioned above.