Local Generic Position for Root Isolation of Zero-dimensional Triangular Polynomial Systems

Jia Li (1) , Jinsan Cheng (2) , Elias Tsigaridas (3)

1 Beijing Electronic Science and Technology Institute
2 KLMM - Key Laboratory of Mathematics Mechanization
3 PolSys - Polynomial Systems

We present an algorithm based on local generic position (LGP) to isolate the complex or real roots and their multiplicities of a zero-dimensional triangular polynomial system. The Boolean complexity of the algorithm for computing the real roots is single exponential: $\tilde{\mathcal {O}}_B(N^{n^2})$, where $N=\max\{d,\tau\}$, $d$ and $\tau$, is the degree and the maximum coefficient bitsize of the polynomials, respectively, and $n$ is the number of variables.

Domaines: Calcul formel [cs.SC]

Jia Li, Jinsan Cheng, Elias Tsigaridas. Local Generic Position for Root Isolation of Zero-dimensional Triangular Polynomial Systems. CASC 2012 - 14th International Workshop on Computer Algebra in Scientific Computing, Sep 2012, Maribor, Slovenia. pp.186-197, ⟨10.1007/978-3-642-32973-9_16⟩. ⟨hal-00776212⟩