Accelerated tower arithmetic

Joris van der Hoeven; Grégoire Lecerf

doi:10.1016/j.jco.2019.03.002

Accelerated tower arithmetic

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

Abstract

Nowadays, asymptotically fast algorithms are widely used in computer algebra for computations in towers of algebraic field extensions of small height. Yet it is still unknown how to reach softly linear time for products and inversions in towers of arbitrary height. In this paper we design the first algorithm for general ground fields with a complexity exponent that can be made arbitrarily close to one from the asymptotic point of view. We deduce new faster algorithms for changes of tower representations, including the computation of primitive element representations in subquadratic time.

Original language	English
Article number	101402
Journal	Journal of Complexity
Volume	55
DOIs	https://doi.org/10.1016/j.jco.2019.03.002
Publication status	Published - 1 Dec 2019

Keywords

Accelerated tower
Algebraic extension
Algebraic tower
Algorithm
Complexity
Computer algebra
Triangular set

Access to Document

10.1016/j.jco.2019.03.002

Cite this

@article{8377a162db6b45aebe9cc73ab341419d,

title = "Accelerated tower arithmetic",

abstract = "Nowadays, asymptotically fast algorithms are widely used in computer algebra for computations in towers of algebraic field extensions of small height. Yet it is still unknown how to reach softly linear time for products and inversions in towers of arbitrary height. In this paper we design the first algorithm for general ground fields with a complexity exponent that can be made arbitrarily close to one from the asymptotic point of view. We deduce new faster algorithms for changes of tower representations, including the computation of primitive element representations in subquadratic time.",

keywords = "Accelerated tower, Algebraic extension, Algebraic tower, Algorithm, Complexity, Computer algebra, Triangular set",

author = "\{van der Hoeven\}, Joris and Gr{\'e}goire Lecerf",

note = "Publisher Copyright: {\textcopyright} 2019",

year = "2019",

month = dec,

day = "1",

doi = "10.1016/j.jco.2019.03.002",

language = "English",

volume = "55",

journal = "Journal of Complexity",

issn = "0885-064X",

}

TY - JOUR

T1 - Accelerated tower arithmetic

AU - van der Hoeven, Joris

AU - Lecerf, Grégoire

PY - 2019/12/1

Y1 - 2019/12/1

N2 - Nowadays, asymptotically fast algorithms are widely used in computer algebra for computations in towers of algebraic field extensions of small height. Yet it is still unknown how to reach softly linear time for products and inversions in towers of arbitrary height. In this paper we design the first algorithm for general ground fields with a complexity exponent that can be made arbitrarily close to one from the asymptotic point of view. We deduce new faster algorithms for changes of tower representations, including the computation of primitive element representations in subquadratic time.

AB - Nowadays, asymptotically fast algorithms are widely used in computer algebra for computations in towers of algebraic field extensions of small height. Yet it is still unknown how to reach softly linear time for products and inversions in towers of arbitrary height. In this paper we design the first algorithm for general ground fields with a complexity exponent that can be made arbitrarily close to one from the asymptotic point of view. We deduce new faster algorithms for changes of tower representations, including the computation of primitive element representations in subquadratic time.

KW - Accelerated tower

KW - Algebraic extension

KW - Algebraic tower

KW - Algorithm

KW - Complexity

KW - Computer algebra

KW - Triangular set

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

U2 - 10.1016/j.jco.2019.03.002

DO - 10.1016/j.jco.2019.03.002

M3 - Article

AN - SCOPUS:85069707616

SN - 0885-064X

VL - 55

JO - Journal of Complexity

JF - Journal of Complexity

M1 - 101402

ER -

Accelerated tower arithmetic

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this