Separating linear forms for bivariate systems

DOI10.1145/2465506.2465518zbMATH Open1360.68923arXiv1303.5041OpenAlexW2164300104MaRDI QIDQ2963224FDOQ2963224

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)

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).

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

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

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)

Cited In (7)

• A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)