Separating linear forms for bivariate systems

DOI10.1145/2465506.2465518MaRDI QIDQ2963224zbMATH OpenOpenAlexFDO

Authors Yacine Bouzidi, Sylvain Lazard, Marc Pouget, Fabrice Rouillier

Publication date 10 February 2017

Published in Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.5041

zbMATH Keywords

bivariate systemseparating linear form

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Solving polynomial systems; resultants (13P15)

Abstract: We present an algorithm for computing a separating linear form of a system of bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at distinct (complex) solutions of the system. In other words, a separating linear form defines a shear of the coordinate system that sends the algebraic system in generic position, in the sense that no two distinct solutions are vertically aligned. The computation of such linear forms is at the core of most algorithms that solve algebraic systems by computing rational parameterizations of the solutions and, moreover, the computation a separating linear form is the bottleneck of these algorithms, in terms of worst-case bit complexity. Given two bivariate polynomials of total degree at most $d$ with integer coefficients of bitsize at most~$au$, our algorithm computes a separating linear form in $sOB(d^8+d^{7}au)$ bit operations in the worst case, where the previously known best bit complexity for this problem was $sOB(d^{10}+d^{9}au)$ (where $sO$ refers to the complexity where polylogarithmic factors are omitted and $O_B$ refers to the bit complexity).

Recommendations

• Improved algorithm for computing separating linear forms for bivariate systems
• Separating linear forms and rational univariate representations of bivariate systems
• Solving bivariate systems using rational univariate representations
• Rational univariate representations of bivariate systems and applications
• On the complexity of solving a bivariate polynomial system

Cited in

(7)

• scientific article; zbMATH DE number 1400029 (Why is no real title available?)
• A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers
• scientific article; zbMATH DE number 1066345 (Why is no real title available?)
• Separating linear forms and rational univariate representations of bivariate systems
• On the complexity of computing with planar algebraic curves
• Improved algorithm for computing separating linear forms for bivariate systems
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition

This page was built for publication: Separating linear forms for bivariate systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963224)