On the complexity of skew arithmetic

Joris van der Hoeven

doi:10.1007/s00200-015-0269-0

On the complexity of skew arithmetic

Joris van der Hoeven

Research output: Contribution to journal › Article › peer-review

Abstract

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 almost linearly in terms of the cost of multiplication.

Original language	English
Pages (from-to)	105-122
Number of pages	18
Journal	Applicable Algebra in Engineering, Communication and Computing
Volume	27
Issue number	2
DOIs	https://doi.org/10.1007/s00200-015-0269-0
Publication status	Published - 1 Mar 2016

Keywords

Algorithm
Complexity
Division
Linear differential operators
Local solution
Multiplication
gcrd
lclm

Access to Document

10.1007/s00200-015-0269-0

Cite this

@article{e521dbb6faae42e492b760c440622c43,

title = "On the complexity of skew arithmetic",

abstract = "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 almost linearly in terms of the cost of multiplication.",

keywords = "Algorithm, Complexity, Division, Linear differential operators, Local solution, Multiplication, gcrd, lclm",

author = "\{van der Hoeven\}, Joris",

note = "Publisher Copyright: {\textcopyright} 2015, Springer-Verlag Berlin Heidelberg.",

year = "2016",

month = mar,

day = "1",

doi = "10.1007/s00200-015-0269-0",

language = "English",

volume = "27",

pages = "105--122",

journal = "Applicable Algebra in Engineering, Communication and Computing",

issn = "0938-1279",

number = "2",

}

TY - JOUR

T1 - On the complexity of skew arithmetic

AU - van der Hoeven, Joris

PY - 2016/3/1

Y1 - 2016/3/1

N2 - 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 almost linearly in terms of the cost of multiplication.

AB - 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 almost linearly in terms of the cost of multiplication.

KW - Algorithm

KW - Complexity

KW - Division

KW - Linear differential operators

KW - Local solution

KW - Multiplication

KW - gcrd

KW - lclm

U2 - 10.1007/s00200-015-0269-0

DO - 10.1007/s00200-015-0269-0

M3 - Article

AN - SCOPUS:84959214270

SN - 0938-1279

VL - 27

SP - 105

EP - 122

JO - Applicable Algebra in Engineering, Communication and Computing

JF - Applicable Algebra in Engineering, Communication and Computing

IS - 2

ER -

On the complexity of skew arithmetic

Abstract

Keywords

Access to Document

Fingerprint

Cite this