4
$\begingroup$

This question was previously posted to Math.SE here and had received no answers at the time of this posting.

When performing computational work, I often come across a univariate function, defined in terms of an integral or differential equation, which I would like to rapidly evaluate (say, millions of times per second) over a specified interval to a given precision (say, one part in $10^{10}$). For example, the function $$ f(\alpha) = \int_{k=0}^\infty \frac{e^{-\alpha^2 k^2}}{k+1}\ \mathrm{d}k $$ over the interval $\alpha \in (0,10)$ came up in a recent project. Now it happens that this integral can be evaluated in terms of standard special functions (in particular, $\operatorname{Ei}(z)$ and $\operatorname{erfi}(z)$), but suppose we had a much more complicated function for which no such evaluation was known. Is there a systematic technique I can apply to develop my own numerical routines for the evaluation of such functions?

I am sure plenty of techniques must be out there, as fast algorithms seem to exist for basically all of the common special functions. However, I emphasize that the sort of technique I am looking for should not rely on the function having some particular structure (e.g. recurrence relations like $\Gamma(n+1) = n\Gamma(n)$ or reflection formulas like $\Gamma(z) \Gamma(1-z) = \pi \csc(\pi z)$). Ideally, such a technique would work for just about any (sufficiently well-behaved) function I come across.

You can take for granted that I do have some slow method of evaluating the desired function (e.g. direct numerical integration) to any precision, and that I'm willing to do a lot of pre-processing work with the slow method in order to develop a fast method.

$\endgroup$
  • 1
    $\begingroup$ I would have to say that I think the responses you got on MSE from Hagen von Eitzen and from njuffa are probably right — I think it's rare for there to be a "special" technique. If you look at the multitude of "Methods of Computation" sections of the DLMF, it often recommends reducing a problem to evaluating an ODE/integral/series/etc. I also agree with njuffa that polynomial/rational approximation and argument transformations is the best first thing to try. For your example function the first step is to transform it to get rid of the singularity at $\alpha=0$. $\endgroup$ – Kirill Nov 24 '15 at 23:13
  • $\begingroup$ The question seems somewhat broad. Would you say that argument transformation together with polynomial/rational approximation is the kind of a systematic technique that is a suitable answer to this question? $\endgroup$ – Kirill Nov 24 '15 at 23:15
  • $\begingroup$ @Kirill I was hoping there would be more powerful general-purpose techniques for constructing fast function approximations, but if that's the best one can do at this level of generality, then I'd gladly accept that answer. $\endgroup$ – David Zhang Nov 24 '15 at 23:18
  • $\begingroup$ @Kirill In particular, what systematic techniques are there for constructing high-accuracy polynomial or rational approximations to a function for a given error tolerance over an interval? I know these approximations are often easier to do piecewise; are there systematic means for deciding how to subdivide the interval of interest? $\endgroup$ – David Zhang Nov 24 '15 at 23:24
  • $\begingroup$ If this question was answered over on MSE, would you mind adding a note to this question here? $\endgroup$ – Kirill Nov 26 '15 at 1:08
1
$\begingroup$

In general you can expect that a customized algorithm would be faster for each particular special function that you need to evaluate over various ranges- that's why there are so many different approaches used for particular special functions. A general purpose approach probably won't be the fastest for all possible functions.

For limited ranges of arguments where the function is quite smooth, you might consider computing tables of values to high accuracy and then interpolating these values using a higher order interpolation method.

$\endgroup$

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.