Accelerated tower arithmetic

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Complexity 2019-12, Vol.55, p.101402, Article 101402
Main Authors: van der Hoeven, Joris, Lecerf, Grégoire
Format: Article
Language:English
Subjects:
Accelerated tower
Algebraic extension
Algebraic tower
Algorithm
Commutative Algebra
Complexity
Computational Complexity
Computer algebra
Computer Science
Mathematical Software
Mathematics
Symbolic Computation
Triangular set
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0885-064X
1090-2708
DOI:10.1016/j.jco.2019.03.002