A Note on the Space Complexity of Fast D-Finite Function Evaluation

Marc Mezzarobba 1
1 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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 Ο(p*(lg p)^(3+o(1))) and space Ο(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.
Complete list of metadatas

https://hal.inria.fr/hal-00687818
Contributor : Marc Mezzarobba <>
Submitted on : Sunday, September 23, 2012 - 11:28:46 AM
Last modification on : Friday, April 20, 2018 - 3:44:26 PM
Long-term archiving on : Monday, December 24, 2012 - 2:40:11 AM

Licence


Distributed under a Creative Commons CC0 - Public Domain Dedication 4.0 International License

Identifiers

Collections

Citation

Marc Mezzarobba. A Note on the Space Complexity of Fast D-Finite Function Evaluation. CASC - Computer Algebra in Scientific Computing, Sep 2012, Maribor, Slovenia. pp.212-223, ⟨10.1007/978-3-642-32973-9_18⟩. ⟨hal-00687818v2⟩

Share

Metrics

Record views

405

Files downloads

253