Multilinear Polynomial Systems: Root Isolation and Bit Complexity

Ioannis Z. Emiris (1, 2) , Angelos Mantzaflaris (3, 1) , Elias Tsigaridas (4, 5)

1 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
2 ATHENA - Research and Innovation Center in Information, Communication and Knowledge Technologies
3 COMUE UCA - COMUE Université Côte d'Azur (2015-2019)
4 OURAGAN - OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs
5 PolSys - Polynomial Systems

We exploit structure in polynomial system solving by considering polyno-mials that are linear in subsets of the variables. We focus on algorithms and their Boolean complexity for computing isolating hyperboxes for all the isolated complex roots of well-constrained, unmixed systems of multilinear polynomials based on resultant methods. We enumerate all expressions of the multihomogeneous (or multigraded) resultant of such systems as a determinant of Sylvester-like matrices, aka generalized Sylvester matrices. We construct these matrices by means of Weyman homological complexes, which generalize the Cayley-Koszul complex. The computation of the determinant of the resultant matrix is the bottleneck for the overall complexity. We exploit the quasi-Toeplitz structure to reduce the problem to efficient matrix-vector multiplication, which corresponds to multivariate polynomial multiplication, by extending the seminal work on Macaulay matrices of Canny, Kaltofen, and Yagati [9] to the multi-homogeneous case. We compute a rational univariate representation of the roots, based on the primitive element method. In the case of 0-dimensional systems we present a Monte Carlo algorithm with probability of success 1 − 1/2^r, for a given r ≥ 1, and bit complexity O_B (n^2 D^(4+e) (n^(N +1) + τ) + n D^(2+e) r (D +r)) for any e> 0, where n is the number of variables, D equals the multilinear Bézout bound, N is the number of variable subsets, and τ is the maximum coefficient bitsize. We present an algorithmic variant to compute the isolated roots of overdetermined and positive-dimensional systems. Thus our algorithms and complexity analysis apply in general with no assumptions on the input.

Mots clés: Bit complexity; Primitive element; Cayley-Koszul complex; Resultant matrix; Rational univariate representation; DMM separation bound

Domaines: Calcul formel [cs.SC]; Modélisation et simulation; Analyse numérique [math.NA]

Ioannis Z. Emiris, Angelos Mantzaflaris, Elias Tsigaridas. Multilinear Polynomial Systems: Root Isolation and Bit Complexity. Journal of Symbolic Computation, 2021, Special Issue on Milestones in Computer Algebra (MICA 2016), 105, pp.145-164. ⟨10.1016/j.jsc.2020.06.005⟩. ⟨hal-02099556⟩