@inproceedings{7dcdef6c4f4d4457bc03a01faf65bd89,
title = "A note on the space complexity of fast D-finite function evaluation",
abstract = "We state and analyze a generalization of the {\textquotedblleft}truncation trick{\textquotedblright} 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.",
author = "Marc Mezzarobba",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2012.; 14th International Workshop on Computer Algebra in Scientific Computing, CASC 2012 ; Conference date: 03-09-2012 Through 06-09-2012",
year = "2012",
month = jan,
day = "1",
doi = "10.1007/978-3-642-32973-9\_18",
language = "English",
isbn = "9783642329722",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "212--223",
editor = "Gerdt, \{Vladimir P.\} and Wolfram Koepf and Mayr, \{Ernst W.\} and Vorozhtsov, \{Evgenii V.\}",
booktitle = "Computer Algebra in Scientific Computing - 14th InternationalWorkshop, CASC 2012, Proceedings",
}