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

International audienceWe 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.Nous énonçons et analysons une généralisation de " l'astuce des troncatures " proposée par Gourdon et Sebah afin d'améliorer les performances de l'évaluation de séries rationnelles par scindage binaire. Il ressort de notre analyse que les valeurs de fonctions D-finies (c'est-à-dire de fonctions décrites comme solutions d'équations différentielles linéaires à coefficients polynomiaux) se calculent avec une erreur bornée par 2^(-p) en temps Ο(p*(lg p)^(3+o(1))) et en espace O(p). L'algorithme standard dû à Chudnovsky et Chudnovsky fournit la même borne de complexité en temps mais nécessite Θ(p*lg p) bits de mémoire