On the complexity of skew arithmetic


In this paper, we study the complexity of several basic operations on linear differential operators with polynomial coefficients. As in the case of ordinary polynomials, we show that these complexities can be expressed in terms of the cost of multiplication.

Authors: Joris van der Hoeven

Keywords: Linear differential operations, algorithm, complexity, multiplication, local solution, division, lcd, gcm

A.M.S. subject classification: 68W30, 68Q15, 34M03, 12E15

View: Html, TeXmacs, Pdf, BibTeX