SCIENCE@home

Fast computation of common left multiples of linear ordinary differential operators

Alin Bostan,F. Chyzak,Ziming Li,B. Salvy

Published 2011 in ACCA

ABSTRACT

We study tight bounds and fast algorithms for LCLMs of several linear differential operators with polynomial coefficients. We analyse 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-60 of 60 references · Page 1 of 1

CITED BY

Showing 1-26 of 26 citing papers · Page 1 of 1