Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization

DOI10.1016/J.JSC.2017.08.001MaRDI QIDQ1690788zbMATH OpenOpenAlexFDO

Authors Mohab Safey El Din, Éric Schost

Publication date 12 January 2018

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.07433

zbMATH Keywords

multi-homogeneous systems polynomial optimization polynomial system solving

Mathematics Subject Classification ID

Solving polynomial systems; resultants (13P15) Symbolic computation and algebraic computation (68W30)

Abstract: Multi-homogeneous polynomial systems arise in many applications. We provide bit complexity estimates for solving them which, up to a few extra other factors, are quadratic in the number of solutions and linear in the height of the input system under some genericity assumptions. The assumptions essentially imply that the Jacobian matrix of the system under study has maximal rank at the solution set and that this solution set if finite. The algorithm is probabilistic and a probability analysis is provided. Next, we apply these results to the problem of optimizing a linear map on the real trace of an algebraic set. Under some genericity assumptions, we provide bit complexity estimates for solving this polynomial minimization problem.

Review text

Let us give first some basic concepts to state the main results of the paper. Let \(X_1,\ldots ,X_m\) be a partition of the set of given variables and \(\mathbf{X}=(X_1,\ldots ,X_m)\). Let also \(\mathbf{d}=(d_1,\ldots ,d_m)\) be a sequence of positive integers. A polynomial \(f\in K[\mathbf{X}]\) is called multi-homogeneous of multi-degree \(\mathbf{d}\) if every term appearing in \(f\) is multi-homogeneous of multi-degree \(\mathbf{d}\) w.r.t. \(\mathbf{X}\). In addition, we shall need the height of a polynomial over rationals. For \(a = u/v \in {\mathbb Q}\setminus \{0\}\), the height of \(a\), denoted by \(\mathrm{ht}(a)\), is \(\max(\log(|u|), \log(v))\), with \(u\in \mathbb{Z}\) and \(v\in \mathbb{N}\) coprime. For a non-zero univariate or multivariate polynomial \(f\) with rational coefficients, let \(v\in \mathbb{N}\) be the minimal common denominator of all its non-zero coefficients. Then \(\mathrm{ht}(f)\) is defined as the maximum of the logarithms of \(v\) and of the absolute values of the coefficients of \(v f\) (which are integers). In this paper, bit complexity estimates for solving multi-homogeneous polynomial systems are presented which, up to a few extra other factors, are quadratic in the number of solutions and linear in the height of the input system, under some genericity assumptions. Furthermore, these results are applied to the problem of optimizing a linear map on the real trace of an algebraic set.

Recommendations

Cites work

Cited in

(18)

Describes a project that uses

Uses Software

This page was built for publication: Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1690788)