Directed evaluation

Let K be a fixed effective field. The most straightforward approach to compute with an element in the algebraic closure of K is to compute modulo its minimal polynomial. The determination of a minimal polynomial from an arbitrary annihilator requires an algorithm for polynomial factorization over K....

Full description

Saved in:
Bibliographic Details
Published in:Journal of Complexity 2020-10, Vol.60, p.101498, Article 101498
Main Authors: van der Hoeven, Joris, Lecerf, Grégoire
Format: Article
Language:English
Subjects:
Accelerated tower
Algebraic tower
Complexity
Computer Science
Directed evaluation
Dynamic evaluation
Mathematical Software
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:Let K be a fixed effective field. The most straightforward approach to compute with an element in the algebraic closure of K is to compute modulo its minimal polynomial. The determination of a minimal polynomial from an arbitrary annihilator requires an algorithm for polynomial factorization over K. Unfortunately, such algorithms do not exist over generic effective fields. They do exist over fields that are explicitly generated over their prime sub-field, but they are often expensive. The dynamic evaluation paradigm, introduced by Duval and collaborators in the eighties, offers an alternative algorithmic solution for computations in the algebraic closure of K. This approach does not require an algorithm for polynomial factorization, but it still suffers from a non-trivial overhead due to suboptimal recomputations. For the first time, we design another paradigm, called directed evaluation, which combines the conceptual advantages of dynamic evaluation with a good worst case complexity bound.
ISSN:0885-064X
1090-2708
DOI:10.1016/j.jco.2020.101498