Search

Abstract: The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of homogeneous equations in variables is satisfiable (the resultant is a polynomial in the system’s coefficients which vanishes if and only if the system is satisfiable). In this paper, we investigate the complexity of computing the multivariate resultant. First, we study the complexity of testing the multivariate resultant for zero. Our main result is that this problem is -hard under deterministic reductions in any characteristic, for systems of low-degree polynomials with coefficients in the ground field (rather than in an extension). In null characteristic, we observe that this problem is in the Arthur–Merlin class if the generalized Riemann hypothesis holds true, while the best known upper bound in positive characteristic remains . Second, we study the classical algorithms to compute the resultant. They usually rely on the computation of the determinant of an exponential-size matrix, known as Macaulay matrix. We show that this matrix belongs to a class of succinctly representable matrices, for which testing the determinant for zero is proved -complete. This means that improving Canny’s upper bound requires either to look at the fine structure of the Macaulay matrix to find an ad hoc algorithm for computing its determinant, or to use altogether different techniques. [Copyright &y& Elsevier]

Abstract: Many methods to compute the winding number of plane curves have been proposed, often with the aim of counting the number of roots of polynomials (or, more generally, zeros of analytic functions) inside some region by using the principle of argument. In this paper we propose another method, which are not based on numerical integration, but on discrete geometry. We give conditions that ensure its correct behavior, and a complexity bound based on the distance of the curve to singular cases. Besides, we provide a modification of the algorithm that detects the proximity to a singular case of the curve. If this proximity is such that the number of operations required grows over certain threshold, set by the user, the modified algorithm returns without winding number computation, but with information about the distance to singular case. When the method is applied to polynomials, this information refers to the localization of the roots placed near the curve. [Copyright &y& Elsevier]

Abstract: In this paper we study planar polynomial differential systems of this form: where and , , and. A lot of properties of planar polynomial differential systems are related to irreducible Darboux polynomials of the corresponding derivation: . Darboux polynomials are usually computed with the method of undetermined coefficients. With this method we have to solve a polynomial system. We show that this approach can give rise to the computation of an exponential number of reducible Darboux polynomials. Here we show that the Lagutinskii–Pereira algorithm computes irreducible Darboux polynomials with degree smaller than , with a polynomial number, relatively to , and , binary operations. We also give a polynomial-time method to compute, if it exists, a rational first integral with bounded degree. [Copyright &y& Elsevier]