Geodesic
FP//LINSPACE evaluation of real Lambert W-function~$W_0$
Prikladnaâ diskretnaâ matematika, no. 3 (2014), pp. 111-116.

Voir la notice de l'article provenant de la source Math-Net.Ru

In the paper, we construct FP//LINSPACE algorithmic analog of real Lambert W-function $W_0(x)$ on segment $[-(re)^{-1},(re)^{-1}]$ of FP//LINSPACE algorithmic real numbers, where $r$ is a rational number, $r>4/3$ (any such rational number is suitable). To construct algorithmic analog of real Lambert W-function $W_0(x)$, we consider algorithm WLE for the evaluation of dyadic rational approximations of the function on segment $[-(re)^{-1},(re)^{-1}]$ on Turing machine using polynomial time and linear space. Algorithm WLE is based on the Taylor series expansion of the function; it is shown that the Taylor series of real Lambert W-function $W_0(x)$ on segment $[-(re)^{-1},(re)^{-1}]$ converges linearly. This fact is used in the algorithm.
Keywords: real Lambert W-function $W_0$, algorithmic real functions, Turing machine, polynomial time complexity, linear space complexity. 
@article{PDM_2014_3_a10,
     author = {M. A. Staritzyn and S. V. Yakhontov},
     title = {FP//LINSPACE evaluation of real {Lambert} {W-function~}$W_0$},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {111--116},
     publisher = {mathdoc},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2014_3_a10/}
}
TY  - JOUR
AU  - M. A. Staritzyn
AU  - S. V. Yakhontov
TI  - FP//LINSPACE evaluation of real Lambert W-function~$W_0$
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2014
SP  - 111
EP  - 116
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2014_3_a10/
LA  - ru
ID  - PDM_2014_3_a10
ER  - 
%0 Journal Article
%A M. A. Staritzyn
%A S. V. Yakhontov
%T FP//LINSPACE evaluation of real Lambert W-function~$W_0$
%J Prikladnaâ diskretnaâ matematika
%D 2014
%P 111-116
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2014_3_a10/
%G ru
%F PDM_2014_3_a10
M. A. Staritzyn; S. V. Yakhontov. FP//LINSPACE evaluation of real Lambert W-function~$W_0$. Prikladnaâ diskretnaâ matematika, no. 3 (2014), pp. 111-116. http://geodesic.mathdoc.fr/item/PDM_2014_3_a10/

[1] Dubinov A. E., Dubinova I. D., Saikov S. K., W-funktsiya Lamberta i ee primenenie v matematicheskikh zadachakh fiziki, Izd-vo FGUP “RFYaTs-VNIIEF”, Sarov, 2006, 160 pp.

[2] Yakhontov S. V., Kosovskii N. K., Kosovskaya T. M., Effektivnye po vremeni i pamyati algoritmicheskie priblizheniya chisel i funktsii, Ucheb. posobie, Izd-vo SPbGU, SPb., 2012, 256 pp.

[3] Ko K., Complexity Theory of Real Functions, Birkhauser, Boston, 1991, 310 pp. | MR

[4] Du D., Ko K., Theory of Computational Complexity, John Wiley Sons, N.Y., 2000, 491 pp. | MR

[5] Brent R. P., “Fast multiple-precision evaluation of elementary functions”, J. ACM, 23:2 (1976), 242–251 | DOI | MR | Zbl

[6] Karatsuba E. A., “Bystrye vychisleniya transtsendentnykh funktsii”, Problemy peredachi informatsii, 27:4 (1991), 76–99 | MR | Zbl

[7] Haible B., Papanikolaou T., “Fast multiprecision evaluation of series of rational numbers”, Proc. Third Intern. Symposium on Algorithmic Number Theory (Portland, Orgeon, USA, June 21–25, 1998), 338–350 | MR | Zbl

[8] Mezzarobba M., “A note on the space complexity of fast D-finite function evaluation”, Computer Algebra in Scientific Comput., 7442 (2012), 212–223 | DOI | Zbl

[9] Staritsyn M. A., Yakhontov S. V., “Effektivnoe po vremeni i pamyati vychislenie W-funktsii Lamberta”, Chetvertaya Vseros. nauch. konf. po problemam informatiki SPISOK-14, SPb., 2014 (to appear)

[10] Fikhtengolts G. M., Kurs differentsialnogo i integralnogo ischisleniya, v. 2, Fizmatlit, M., 2003, 680 pp.