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.

Authors: Joris van der Hoeven, Grégoire Lecerf

Keywords: complexity, algorithm, computer algebra, algebraic extension, algebraic tower, triangular set, accelerated tower

View: Html, TeXmacs, Pdf, BibTeX