3
$\begingroup$

I have to repeatedly calculate a function which contains a sum of a large number (~100) of exponential terms:

$f(x) = \sum_{r=1}^{100} C_r e^{b_r \cdot x}$

There is no relation between the $C_r$ and $b_r$ (i.e. something like $C_{r+1}$ = 2 $C_r$).

Does anyone know a fast way to determine a numerical approximation for such a sum of exponentials?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Try to use the following transformation $x = \ln{y}$ and compute the following sum: $$f(\ln{y}) = \sum_r C_r{y^{b_r}}$$ $\endgroup$ – HBR Sep 25 '17 at 15:15
  • $\begingroup$ Thanks for the suggestion! Do you know how much faster calculating $y^{b_r}$ should be compared to calculating $e^{b_r x}$ ? $\endgroup$ – KMee Sep 25 '17 at 15:25
  • 3
    $\begingroup$ Check this out.. And look up some info on logsumexp $\endgroup$ – GoHokies Sep 27 '17 at 21:17
  • 3
    $\begingroup$ Do you need to compute this for large values of x? What is the desired precision? What programming language do you use? In my opinion for just 100 exponentials it is not worth searching for an approximation. Computing things directly should work well enough... $\endgroup$ – Beni Bogosel Nov 27 '17 at 13:23
  • 1
    $\begingroup$ Is there a good reason for leaving the terms in the form $C_r e^{b_r\cdot x}$ instead of $e^{b_r\cdot x+ c_r}$ where $c_r\equiv \ln C_r$? Because if your system has a fast fused multiply-add (fma), then that would be a win. Combine that with a good logsumexp, and you'd be set. $\endgroup$ – Sean Lake Dec 27 '17 at 4:34
2
$\begingroup$

Sometimes, the best way to do this kind of things is rather simple. If the problem is computing this function a lot of times, then... don't compute it!

Basically, all you have to do is to write a table for a finite set of values $x_j$. If you are going to compute $f(x)$ with $x\in[a,b]$, then you compute $f(x_j)$, where $x_j=a+j\Delta x$, $\Delta x=(b-a)/N$. The larger $N$, the better representation of the function you get.

You compute this table once, at the beginning of the program. You could additionally write it to a file and simply recover it at the beginning.

Finally, if you need $f(x)$, with $x_j<x<x_{j+1}$, you return $f(x)\simeq(f(x_j)+f(x_{j+1}))/2$. Since your function is continuous, if $\Delta x$ is small enough, you are going to have a very good approximation for $f(x)$. And you avoid computing the function, since all the $f(x_j)$ are stored in memory.

This "trick" really saves a lot of computations (at expense of having the results stored in memory) and in my opinion it is not used as much as it should.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ You mean tabulating the function? Sure, but you'd still be left with the problem of evaluating the function N times (where N may be large), so you haven't really answered the question. $\endgroup$ – GoHokies Sep 27 '17 at 21:10
  • $\begingroup$ Well, a decent program may compute this function, for example, $10^6$ times. If I tabulate it using $N=10^3$, then I am saving a large number of iterations. In addition to that, I may have to run the program dozens of times. If I tabulate using $N=10^6$ and write it to file, I still have a benefit. I know this is not a direct answer to OP's question, but I think this helps in a large number of cases. $\endgroup$ – VictorSeven Sep 28 '17 at 7:52
  • $\begingroup$ This is a good suggestion, unfortunately I've simplified the original problem for clarity in my question. It looks like this: $f(x,y,z) = \sum_r C_r e^{b_rx +d_ry+ f_r z}$. In this case a lookup-table would probably be too large since it would have something like ${10^3}^3 = 10^9$ entries? $\endgroup$ – KMee Oct 4 '17 at 12:37
  • $\begingroup$ In that case you are right, probably the lookup table is not the best option. $\endgroup$ – VictorSeven Oct 5 '17 at 14:21

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.