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
KLMM - Key Laboratory of Mathematics Mechanization
3 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-00776212
Contributor : Elias Tsigaridas <>
Submitted on : Tuesday, January 15, 2013 - 11:28:58 AM
Last modification on : Thursday, March 21, 2019 - 2:17:18 PM
Long-term archiving on : Saturday, April 1, 2017 - 5:14:15 AM

File

lct-lgp.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

375

Files downloads

194