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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-00698610
Contributor : Bruno Salvy <>
Submitted on : Thursday, May 17, 2012 - 7:41:36 AM
Last modification on : Wednesday, November 20, 2019 - 3:27:40 AM

Links full text

Identifiers

  • 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. ISSAC 2012 - 37th International Symposium on Symbolic and Algebraic Computation, Jul 2012, Grenoble, France. pp.99-106. ⟨hal-00698610⟩

Share

Metrics

Record views

389