2 A NOTE ON THE SPACE COMPLEXITY OF FAST D-FINITE FUNCTION EVALUATION
Marc Mezzarobba, Lip (umr Cnrs-ens Lyon-inria-ucbl · 2012
Abstract. We state and analyze a generalization of the “truncation trick” suggested by Gourdon and Sebah to improve the performance of power series evaluation by binary splitting. It follows from our analysis that the values of D-finite functions (i.e., functions described as solutions of linear differential equations with polynomial coefficients) may be computed with error bounded by 2 −p in time O(p(lg p) 3+o(1) ) and space O(p). The standard fast algorithm for this task, due to Chudnovsky and Chudnovsky, achieves the same time complexity bound but requires Θ(p lg p) bits of memory. 1.