Quasi-optimal multiplication of linear differential operators

Alexandre Benoit; Alin Bostan; Joris Van Der Hoeven

doi:10.1109/FOCS.2012.57

Quasi-optimal multiplication of linear differential operators

Alexandre Benoit
, Alin Bostan
, Joris Van Der Hoeven

Research output: Contribution to journal › Conference article › peer-review

Abstract

We show that linear differential operators with polynomial coefficients over a field of characteristic zero can be multiplied in quasi-optimal time. This answers an open question raised by van der Hoeven.

Original language	English
Article number	6375331
Pages (from-to)	524-530
Number of pages	7
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs	https://doi.org/10.1109/FOCS.2012.57
Publication status	Published - 1 Dec 2012
Event	53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States Duration: 20 Oct 2012 → 23 Oct 2012

Keywords

Linear differential operators
algebraic algorithms
computational complexity
multiplication

Access to Document

10.1109/FOCS.2012.57

Cite this

@article{600b6e81c9a445928bb7d4b0d83c66eb,

title = "Quasi-optimal multiplication of linear differential operators",

abstract = "We show that linear differential operators with polynomial coefficients over a field of characteristic zero can be multiplied in quasi-optimal time. This answers an open question raised by van der Hoeven.",

keywords = "Linear differential operators, algebraic algorithms, computational complexity, multiplication",

author = "Alexandre Benoit and Alin Bostan and \{Van Der Hoeven\}, Joris",

year = "2012",

month = dec,

day = "1",

doi = "10.1109/FOCS.2012.57",

language = "English",

pages = "524--530",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

note = "53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 ; Conference date: 20-10-2012 Through 23-10-2012",

}

TY - JOUR

T1 - Quasi-optimal multiplication of linear differential operators

AU - Benoit, Alexandre

AU - Bostan, Alin

AU - Van Der Hoeven, Joris

PY - 2012/12/1

Y1 - 2012/12/1

N2 - We show that linear differential operators with polynomial coefficients over a field of characteristic zero can be multiplied in quasi-optimal time. This answers an open question raised by van der Hoeven.

AB - We show that linear differential operators with polynomial coefficients over a field of characteristic zero can be multiplied in quasi-optimal time. This answers an open question raised by van der Hoeven.

KW - Linear differential operators

KW - algebraic algorithms

KW - computational complexity

KW - multiplication

UR - https://www.scopus.com/pages/publications/84871971065

U2 - 10.1109/FOCS.2012.57

DO - 10.1109/FOCS.2012.57

M3 - Conference article

AN - SCOPUS:84871971065

SN - 0272-5428

SP - 524

EP - 530

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

M1 - 6375331

T2 - 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012

Y2 - 20 October 2012 through 23 October 2012

ER -

Quasi-optimal multiplication of linear differential operators

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this