On Isolating Roots in a Multiple Field Extension

2023/06/07 by Christina Katsamaki, Katsamaki, Christina, Fabrice Rouillier +1
Computer Science · #Coding theory and cryptography #Polynomial and algebraic computation #Digital Filter Design and Implementation

paper · pdf · doi:10.48550/arxiv.2306.04271

Abstract

We address univariate root isolation when the polynomial's coefficients are in a multiple field extension. We consider a polynomial F ∈ L[Y], where L is a multiple algebraic extension of ℚ. We provide aggregate bounds for F and algorithmic and bit-complexity results for the problem of isolating its roots. For the latter problem we follow a common approach based on univariate root isolation algorithms. For the particular case where F does not have multiple roots, we achieve a bit-complexity in O_B(n d²ⁿ⁺²(d+nτ)), where d is the total degree and τ is the bitsize of the involved polynomials.In the general case we need to enhance our algorithm with a preprocessing step that determines the number of distinct roots of F. We follow a numerical, yet certified, approach that has bit-complexity O_B(n²d³ⁿ⁺³τ+ n³ d²ⁿ⁺⁴τ).

Related

• Univariate real root isolation in an extension field
• Univariate polynomial real root isolation: Continued Fractions revisited
• From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition
• Improved complexity bounds for real root isolation using Continued Fractions
• Improved complexity bounds for real root isolation using Continued Fractions