FEE method

In mathematics, the FEE method is the method of fast summation of series of a special form. It was constructed in 1990 by E. A. Karatsuba^[1]^[2] and was called FEE—Fast E-function Evaluation—because it makes it possible fast computations of the Siegel $E$ -functions, and in particular, $e^x.$

A class of functions, which are 'similar to the exponential function' was given the name 'E-functions' by Siegel.^[3] Among these functions are such special functions as the hypergeometric function, cylinder, spherical functions and so on.

Using the FEE, it is possible to prove the following theorem

Theorem: Let $y=f(x)$ be an elementary Transcendental function, that is the exponential function, or a trigonometric function, or an elementary algebraic function, or their superposition, or their inverse, or a superposition of the inverses. Then

s_f(n) = O(M(n)\log^2n). \,

Here $s_f(n)$ is the complexity of computation (bit) of the function $f(x)$ with accuracy up to $n$ digits, $M(n)$ is the complexity of multiplication of two $n$ -digit integers.

The algorithms based on the method FEE include the algorithms for fast calculation of any elementary Transcendental function for any value of the argument, the classical constants e, $\pi,$ the Euler constant $\gamma,$ the Catalan and the Apéry constants,^[4] such higher transcendental functions as the Euler gamma function and its derivatives, the hypergeometric,^[5] spherical, cylinder (including the Bessel)^[6] functions and some other functions for algebraic values of the argument and parameters, the Riemann zeta function for integer values of the argument^[7]^[8] and the Hurwitz zeta function for integer argument and algebraic values of the parameter,^[9] and also such special integrals as the integral of probability, the Fresnel integrals, the integral exponential function, the trigonometric integrals, and some other integrals^[10] for algebraic values of the argument with the complexity bound which is close to the optimal one, namely

s_{f}(n)= O(M(n)\log^2 n). \,

At present, only the FEE makes it possible to calculate fast the values of the functions from the class of higher transcendental functions,^[11] certain special integrals of mathematical physics and such classical constants as Euler's, Catalan's^[12] and Apéry's constants. An additional advantage of the method FEE is the possibility of parallelizing the algorithms based on the FEE.

FEE-computation of classical constants

For fast evaluation of the constant $\pi,$ one can use the Euler formula $\frac{\pi}{4} = \arctan \frac12 + \arctan \frac13,$ and apply the FEE to sum the Taylor series for

\arctan \frac12 = \frac{1}{1\cdot 2} - \frac{1}{3\cdot 2^3}+ \cdots + \frac{(-1)^{r-1}}{(2r-1)2^{2r-1}} + R_1 ,

\arctan \frac13 = \frac{1}{1\cdot 3} - \frac{1}{3\cdot 3^3}+ \cdots + \frac{(-1)^{r-1}}{(2r-1)3^{2r-1}} + R_2 ,

with the remainder terms $R_1,$ $R_2,$ which satisfy the bounds

|R_1| \leq \frac45\frac{1}{2r+1}\frac{1}{2^{2r+1}};

|R_2| \leq \frac{9}{10}\frac{1}{2r+1}\frac{1}{3^{2r+1}};

and for

r = n,\,

4(|R_1|+|R_2|) \ < \ 2^{-n}.

To calculate $\pi$ by the FEE it is possible to use also other approximations^[13] In all cases the complexity is

s_\pi = O(M(n)\log^2 n). \,

To compute the Euler constant gamma with accuracy up to $n$ digits, it is necessary to sum by the FEE two series. Namely, for

m=6n, \quad k = n, \quad k \geq 1, \,

\gamma = - \log n \sum_{r=0}^{12n} \frac{(-1)^rn^{r+1}}{(r+1)!} + \sum_{r=0}^{12n} \frac{(-1)^rn^{r+1}}{(r+1)!(r+1)} + O(2^{-n}) .

The complexity is

s_\gamma = O(M(n)\log^2 n). \,

To evaluate fast the constant $\gamma$ it is possible to apply the FEE to other approximations.^[14]

FEE-computation of certain power series

By the FEE the two following series are calculated fast:

f_1 = f_1(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}z^j ,

f_2 = f_2(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}\frac{z^j}{j!} ,

under the assumption that $a(j) , \quad b(j)$ are integers,

|a(j)|+|b(j)| \leq (Cj)^K; \quad |z| \ < \ 1; \quad K

and $C$ are constants, and $z$ is an algebraic number. The complexity of the evaluation of the series is

s_{f_1}(n) = O\left(M(n)\log^2n \right), \,

s_{f_2}(n)= O\left(M(n)\log n \right).

The FEE details on the example of fast calculation of the classical constant e

For the evaluation of the constant $e$ take $m = 2^k, \quad k \geq 1$ , terms of the Taylor series for $e,$

e = 1 + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{(m-1)!} + R_m.

Here we choose $m$ , requiring that for the remainder $R_m$ the inequality $R_m \leq 2^{-n-1}$ is fulfilled. This is the case, for example, when $m\geq \frac{4n}{\log n}.$ Thus, we take $m=2^k$ such that the natural number $k$ is determined by the inequalities:

2^k \geq \frac{4n}{\log n} > 2^{k-1}.

We calculate the sum

S = 1 + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{(m-1)!} = \sum_{j=0}^{m-1}\frac{1}{(m-1-j)!} ,

in $k$ steps of the following process.

Step 1. Combining in $S$ the summands sequentially in pairs we carry out of the brackets the "obvious" common factor and obtain

\begin{align} S & = \left(\frac{1}{(m-1)!} + \frac{1}{(m-2)!}\right) + \left(\frac{1}{(m-3)!} + \frac{1}{(m-4)!}\right) + \cdots \\ & = \frac{1}{(m-1)!}(1+m-1) + \frac{1}{(m-3)!}(1+m-3) + \cdots . \end{align}

We shall compute only integer values of the expressions in the parentheses, that is the values

m , m-2 , m-4 , \dots . \,

Thus, at the first step the sum $S$ is into

S = S(1) = \sum_{j=0}^{m_1-1}\frac{1}{(m-1-2j)!}\alpha_{m_1-j}(1) ,

m_1 = \frac m2 , m = 2^k , k \geq 1 .

At the first step $\frac m2$ integers of the form

\alpha_{m_1-j}(1) = m-2j , \quad j = 0 , 1 , \dots , m_1 - 1 ,

are calculated. After that we act in a similar way: combining on each step the summands of the sum $S$ sequentially in pairs, we take out of the brackets the 'obvious' common factor and compute only the integer values of the expressions in the brackets. Assume that the first $i$ steps of this process are completed.

Step $i+1$ ( $i+1 \leq k$ ).

S = S(i+1) = \sum_{j=0}^{m_{i+1}-1}\frac{1}{(m-1-2^{i+1}j)!} \alpha_{m_{i+1}-j}(i+1) ,

m_{i+1} = \frac{m_i}{2} = \frac{m}{2^{i+1}} ,

we compute only $\frac{m}{2^{i+1}}$ integers of the form

\alpha_{m_{i+1}-j}(i+1) = \alpha_{m_i-2j}(i) + \alpha_{m_i-(2j+1)}(i)\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!} ,

j = 0 , 1 , \dots , \quad m_{i+1} - 1 , \quad m = 2^k , \quad k \geq i+1 .

Here

\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!}

is the product of $2^i$ integers.

Etc.

Step $k$ , the last one. We compute one integer value $\alpha_1(k),$ we compute, using the fast algorithm described above the value $(m-1)!,$ and make one division of the integer $\alpha_1(k)$ by the integer $(m-1)!,$ with accuracy up to $n$ digits. The obtained result is the sum $S,$ or the constant $e$ up to $n$ digits. The complexity of all computations is

O\left(M(m)\log^2 m\right) = O\left(M(n)\log n\right). \,

References

↑ E.A. Karatsuba, Fast evaluations of transcendental functions. Probl. Peredachi Informat., Vol. 27, N 4, (1991)
↑ D.W. Lozier and F.W.J. Olver, Numerical Evaluation of Special Functions. Mathematics of Computation 1943-1993: A Half-Century of Computational Mathematics, W. Gautschi, eds., Proc. Sympos. Applied Mathematics, AMS, Vol.48 (1994).
↑ C.L. Siegel, Transcendental numbers. Princeton University Press, Princeton (1949).
↑ Karatsuba E. A., Fast evaluation of $\zeta(3)$ , Probl. Peredachi Informat., Vol. 29, N 1 (1993)
↑ Ekatharine A. Karatsuba, Fast evaluation of hypergeometric function by FEE. Computational Methods and Function Theory (CMFT'97), N. Papamichael, St. Ruscheweyh and E.B. Saff, eds., World Sc.Pub. (1999)
↑ Catherine A. Karatsuba, Fast evaluation of Bessel functions. Integral Transforms and Special Functions, Vol. 1, N4 (1993)
↑ E. A. Karatsuba, Fast Evaluation of Riemann zeta-function $\zeta(s)$ for integer values of argument $s$ . Probl. Peredachi Informat., Vol. 31, N 4 (1995).
↑ J.M. Borwein, D.M. Bradley and R.E. Crandall, Computational strategies for the Riemann zeta function. J. of Comput. Appl. Math., Vol. 121 ,N 1-2 (2000).
↑ E.A. Karatsuba, Fast evaluation of Hurwitz zeta function and Dirichlet $L$ -series, Problem. Peredachi Informat., Vol. 34, N 4, pp. 342–353, (1998).
↑ E.A. Karatsuba, Fast computation of some special integrals of mathematical physics. Scientific Computing, Validated Numerics, Interval Methods, W.Kramer, J.W.von Gudenberg, eds.(2001).
↑ E. Bach, The complexity of number-theoretic constants. Info. Proc. Letters, N 62 (1997).
↑ E.A. Karatsuba, Fast computation of $\zeta(3)$ and of some special integrals ,using the polylogarithms, the Ramanujan formula and its generalization. J. of Numerical Mathematics BIT, Vol. 41, N 4 (2001).
↑ D.H. Bailey, P.B. Borwein and S. Plouffe, On the rapid computation of various polylogarithmic constants. Math. Comp.,Vol. 66 (1997).
↑ R.P. Brent and E.M. McMillan, Some new algorithms for high-precision computation of Euler's constant. Math. Comp., Vol.34 (1980).

External links

This article is issued from Wikipedia - version of the 5/18/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.