We propose a new algorithm to compute the topology of a real algebraic space curve. The novelties of this algorithm are a new technique to achieve the lifting step which recovers points of the space curve in each plane fiber from several projections and a weaker notion of generic position. As distinct to previous work, our sweep generic position does not require that x-critical points have different x-coordinates. The complexity of achieving this sweep generic position property is thus no longer a bottleneck in term of complexity. The bit complexity of our algorithm is \widetilde{\mathcal{O}}(d^18+d^17\tau) where d and \tau bound the degree and the bitsize of the integer coefficients, respectively, of the defining polynomials of the curve and polylogarithmic factors are ignored. To the best of our knowledge, this improves upon the best currently known results at least by a factor of d^2.

Publication:

Journal of Symbolic Computation (Volume: 125, November 2024)

https://doi.org/10.1016/j.jsc.2024.102309

Author:

Jin-San Cheng

KLMM, Institute of Systems Science, Academy of Mathematics and Systems Science, CAS, China; School of Mathematical Sciences, University of Chinese Academy of Sciences, China

Email: jcheng@amss.ac.cn

Kai Jin

School of Mathematics and Statistics, Hubei University of Science and Technology, Xianning, China

Marc Pouget

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

Junyi Wen

KLMM, Institute of Systems Science, Academy of Mathematics and Systems Science, CAS, China; School of Mathematical Sciences, University of Chinese Academy of Sciences, China

Bingwei Zhang

KLMM, Institute of Systems Science, Academy of Mathematics and Systems Science, CAS, China; School of Mathematical Sciences, University of Chinese Academy of Sciences, China