Products of Ordinary Differential Operators by Evaluation and Interpolation

Alin Bostan 1 Frédéric Chyzak 1, * Nicolas Le Roux 1
* Auteur correspondant
1 ALGORITHMS - Algorithms
Inria Paris-Rocquencourt
Abstract : It is known that multiplication of linear differential operators over ground fields of characteristic zero can be reduced to a constant number of matrix products. We give a new algorithm by evaluation and interpolation which is faster than the previously-known one by a constant factor, and prove that in characteristic zero, multiplication of differential operators and of matrices are computationally equivalent problems. In positive characteristic, we show that differential operators can be multiplied in nearly optimal time. Theoretical results are validated by intensive experiments.
Keywords : differential operators Fast algorithms differential operators.
Type de document :
Communication dans un congrès
Jeffrey, David. ISSAC'08 : International Symposium on Symbolic and Algebraic Computation, Jul 2008, Hagenberg, Austria. ACM Press, 2008
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00273148
Contributeur : Frédéric Chyzak <>
Soumis le : lundi 14 avril 2008 - 15:31:04
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : vendredi 21 mai 2010 - 01:42:59

Fichiers

issac.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00273148, version 1
  • ARXIV : 0804.2181

Collections

INRIA | INRIA-ROCQ

Citation

Alin Bostan, Frédéric Chyzak, Nicolas Le Roux. Products of Ordinary Differential Operators by Evaluation and Interpolation. Jeffrey, David. ISSAC'08 : International Symposium on Symbolic and Algebraic Computation, Jul 2008, Hagenberg, Austria. ACM Press, 2008. 〈inria-00273148〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

215

Téléchargements de fichiers

173

Contact


archive-ouverte@inria.fr