On the Bit Complexity of Solving Bilinear Polynomial Systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

On the Bit Complexity of Solving Bilinear Polynomial Systems

Résumé

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.
Fichier principal
Vignette du fichier
bilinear.pdf (362.56 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01401134 , version 1 (02-09-2019)

Identifiants

Citer

Ioannis Z. 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⟩
265 Consultations
142 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More