zbMATH — the first resource for mathematics

Fast evaluation of holonomic functions. (English) Zbl 0912.68081
Summary: A holonomic function is an analytic function, which satisfies a linear differential equation with polynomial coefficients. In particular, the elementary functions exp, log, sin, etc. and many special functions like erf, Si, Bessel functions, etc. are holonomic functions. Given a holonomic function \(f\) (determined by the linear differential equation it satisfies and initial conditions in a non singular point \(z\)), we show how to perform arbitrary precision evaluations of \(f\) at a non singular point \(z'\) on the Riemann surface of \(f\), while estimating the error. Moreover, if the coefficients of the polynomials in the equation for \(f\) are algebraic numbers, then our algorithm is asymptotically very fast: if \(M(n)\) is the time needed to multiply two n digit numbers, then we need a time \(O(M(n \log^{2}n \log\log n))\) to compute \(n\) digits of \(f(z')\).

68W30 Symbolic computation and algebraic computation
68W10 Parallel algorithms in computer science
Full Text: DOI
[1] Borwein, J.M.; Borwein, P.B., Pi and the AGM, (1987), Wiley New York · Zbl 0699.10044
[2] Brent, R.P., The complexity of multiprecision arithmetic, ()
[3] Brent, R.P., Fast multiple-precision evaluation of elementary functions, J. ACM, 23, 2, 242-251, (1976) · Zbl 0324.65018
[4] Brent, R.P.; MacMillan, E., Some new algorithms for high-precision computation of Euler’s constant, J. ACM, 23, 242-251, (1980)
[5] Haible, B.; Papanikolaou, T., Fast multiple-precision evaluation of elementary functions, (), Available on the web at
[6] van der Hoeven, J., Fast evaluation of holonomic functions, (), Available on the web at · Zbl 0912.68081
[7] van der Hoeven, J., Automatic asymptotics, () · Zbl 0874.65047
[8] Knuth, D.E., The art of computer programming, () · Zbl 0191.17903
[9] Lipshitz, L., D-finite power series, J. algebra, 122, 353-373, (1989) · Zbl 0695.12018
[10] Naegele, F., Autour de quelques équations fonctionnelles analytiques, ()
[11] Richardson, D., How to recognize zero, J. symbolic computat., 24, 627-645, (1997) · Zbl 0917.11062
[12] Salamin, E., Computation of π using the arithmetic-geometric Mean, Math. comput., 30, 565-570, (1976) · Zbl 0345.10003
[13] Schönhage, A.; Strassen, V., Schnelle multiplikation grosser zahlen, Computing, 7, 281-292, (1971) · Zbl 0223.68007
[14] Stanley, R.P., Differentially finite power series, Eur. J. combin., 1, 175-188, (1980), MR # 81m:05012. · Zbl 0445.05012
[15] Thomann, J., Procédés formels et numériques de sommation de séries d’équations différentielles, Expositiones math., 13, 223-246, (1995) · Zbl 0831.34003
[16] Zeilberger, D., A holonomic systems approach to special functions identities, J. comput. appl. math., 32, 321-368, (1990) · Zbl 0738.33001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.