\input zb-basic
\input zb-ioport
\iteman{io-port 06084877}
\itemau{Mezzarobba, Marc}
\itemti{A note on the space complexity of fast d-finite function evaluation.}
\itemso{Gerdt, Vladimir P. (ed.) et al., Computer algebra in scientific computing. 14th international workshop, CASC 2012, Maribor, Slovenia, September 3--6, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32972-2/pbk). Lecture Notes in Computer Science 7442, 212-223 (2012).}
\itemab
Summary: 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 $\mathrm{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 $\Theta (p \lg p)$ bits of memory.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-32973-9\_18}
\end