Multilinear polynomial systems: Root isolation and bit complexity

摘要

We exploit structure in polynomial system solving by considering polynomials 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 Canny et al. (1989) to the multihomogeneous 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 probabil- ity of success 1 - 1/2(rho), for a given rho = 1, and bit complexity (O) over tilde (B) (n(2)D(4+epsilon)(n(N+1) + tau) + nD(2+epsilon) rho(D + rho)) for any epsilon 0, where n is the number of variables, D equals the multilinear Bezout bound, N is the number of variable subsets, and tau 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. (C) 2020 Published by Elsevier Ltd.