Multilinear polynomial systems: Root isolation and bit complexity. (July 2021)

• Record Type: Journal Article
• Authors: Emiris, Ioannis Z.; Mantzaflaris, Angelos; Tsigaridas, Elias P.
• Is Part Of: Journal of symbolic computation. Volume 105(2021)
• Page Start: 145
• Page End: 164
• Publication Date: 2021-07
• Subjects: Multilinear polynomial -- DMM separation bound -- Resultant matrix -- Cayley-Koszul complex -- Primitive element -- Rational univariate representation -- Bit complexity; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2020.06.005
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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 probability of success 1 − 1 / 2 ϱ, for a given ϱ ≥ 1, and bit complexity O ˜ B ( n 2 D 4 + ϵ ( n N + 1 + τ ) + n D 2 + ϵ ϱ ( D + ϱ ) ) for any ϵ > 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.