Fast Computation of Common Left Multiples of Linear Ordinary Differential Operators

Abstract : We study tight bounds and fast algorithms for LCLMs of several linear differential operators with polynomial coefficients. We analyze the arithmetic complexity of existing algorithms for LCLMs, as well as the size of their outputs. We propose a new algorithm that recasts the LCLM computation in a linear algebra problem on a polynomial matrix. This algorithm yields sharp bounds on the coefficient degrees of the LCLM, improving by one order of magnitude the best bounds obtained using previous algorithms. The complexity of the new algorithm is almost optimal, in the sense that it nearly matches the arithmetic size of the output.
Type de document :
Communication dans un congrès
van Hoeij, Mark and van der Hoeven, Joris. ISSAC 2012 - 37th International Symposium on Symbolic and Algebraic Computation, Jul 2012, Grenoble, France. pp.99-106, 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00698610
Contributeur : Bruno Salvy <>
Soumis le : jeudi 17 mai 2012 - 07:41:36
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

Identifiants

  • HAL Id : hal-00698610, version 1
  • ARXIV : 1205.0879

Collections

Citation

Alin Bostan, Frédéric Chyzak, Ziming Li, Bruno Salvy. Fast Computation of Common Left Multiples of Linear Ordinary Differential Operators. van Hoeij, Mark and van der Hoeven, Joris. ISSAC 2012 - 37th International Symposium on Symbolic and Algebraic Computation, Jul 2012, Grenoble, France. pp.99-106, 2012. 〈hal-00698610〉

Partager

Métriques

Consultations de la notice

347