| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
On the Bit Complexity of Solving Bilinear Polynomial Systems
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.
Cited literature [50 references]
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
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)