On the Bit Complexity of Solving Bilinear Polynomial Systems

Ioannis Emiris 1 Angelos Mantzaflaris 2 Elias Tsigaridas 3
1 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , National and Kapodistrian University of Athens
3 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 OB(n4 D4 + n2D4 τ), 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.
Type de document :
Communication dans un congrès
ISSAC '16 - 41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, Canada. ACM, ISSAC '16 - Proc. ACM International Symposium on Symbolic and Algebraic Computation, pp.215-222, 〈10.1145/2930889.2930919〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01401134
Contributeur : Ioannis Emiris <>
Soumis le : mardi 22 novembre 2016 - 23:19:24
Dernière modification le : mercredi 12 septembre 2018 - 01:15:37

Identifiants

Collections

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. ACM, ISSAC '16 - Proc. ACM International Symposium on Symbolic and Algebraic Computation, pp.215-222, 〈10.1145/2930889.2930919〉. 〈hal-01401134〉

Partager

Métriques

Consultations de la notice

264