Skip to main navigation Skip to search Skip to main content

A note on the space complexity of fast D-finite function evaluation

  • Ecole Normale Supérieure de Lyon

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationComputer Algebra in Scientific Computing - 14th InternationalWorkshop, CASC 2012, Proceedings
EditorsVladimir P. Gerdt, Wolfram Koepf, Ernst W. Mayr, Evgenii V. Vorozhtsov
PublisherSpringer Verlag
Pages212-223
Number of pages12
ISBN (Print)9783642329722
DOIs
Publication statusPublished - 1 Jan 2012
Externally publishedYes
Event14th International Workshop on Computer Algebra in Scientific Computing, CASC 2012 - Maribor, Slovenia
Duration: 3 Sept 2012 → 6 Sept 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7442 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Workshop on Computer Algebra in Scientific Computing, CASC 2012
Country/TerritorySlovenia
CityMaribor
Period3/09/12 → 6/09/12

Fingerprint

Dive into the research topics of 'A note on the space complexity of fast D-finite function evaluation'. Together they form a unique fingerprint.

Cite this