Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

On the Bit Complexity of Solving Bilinear Polynomial Systems

Ioannis Emiris 1 Angelos Mantzaflaris 2, 1, 3 Elias Tsigaridas 4
1 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , NKUA - National and Kapodistrian University of Athens
4 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : We bound the Boolean complexity of computing isolating hyperboxes for all complex roots of systems of bilinear polynomials. The resultant of such systems admits a family of determinantal Sylvester-type formulas, which we make explicit by means of homological complexes. The computation of the determinant of the resultant matrix is a bottleneck for the overall complexity. We exploit the quasi-Toeplitz structure to reduce the problem to efficient matrix-vector products, corresponding to multivariate polynomial multiplication. For zero-dimensional systems, we arrive at a primitive element and a rational univariate representation of the roots. The overall bit complexity of our probabilistic algorithm is O_B(n^4 D^4 + n^2 D^4 τ), where n is the number of variables, D equals the bilinear Bezout bound, and τ is the maximum coefficient bitsize. Finally, a careful infinitesimal symbolic perturbation of the system allows us to treat degenerate and positive dimensional systems, thus making our algorithms and complexity analysis applicable to the general case.
Document type :
Conference papers
Complete list of metadata

Cited literature [50 references]  Display  Hide  Download

Contributor : Ioannis Emiris Connect in order to contact the contributor
Submitted on : Monday, September 2, 2019 - 10:17:37 AM
Last modification on : Friday, February 4, 2022 - 3:13:13 AM
Long-term archiving on: : Thursday, January 9, 2020 - 9:07:16 AM


Files produced by the author(s)



Ioannis Emiris, Angelos Mantzaflaris, Elias Tsigaridas. On the Bit Complexity of Solving Bilinear Polynomial Systems. ISSAC '16 - 41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, Canada. pp.215-222, ⟨10.1145/2930889.2930919⟩. ⟨hal-01401134⟩



Record views


Files downloads