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

https://hal.inria.fr/hal-01401134
Contributor : Ioannis Emiris <>
Submitted on : Monday, September 2, 2019 - 10:17:37 AM
Last modification on : Friday, January 8, 2021 - 5:44:01 PM
Long-term archiving on: : Thursday, January 9, 2020 - 9:07:16 AM

File

bilinear.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

437

Files downloads

343