Algebraic combinatorics and resultant methods for polynomial system solving

Anna Karasoulou 1, 2
2 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , National and Kapodistrian University of Athens
Abstract : The contribution of the thesis is threefold. The first Problem is computing the discriminant, when the system’s dimension varies. Thus solving polynomial equations and systems by exploiting the structure and sparseness of them have been studied. Specifically, closed formulas for the degree of the sparse (mixed) discriminant and the sparse resultant of polynomial equations have been studied, as well as relationships between them. Closed formulas when one of the polynomials factors in the context of the theory of sparse elimination using the Newton polytope have been proposed. The purpose is to facilitate the computation of the sparse (or mixed) discriminant of a well-constrained polynomial system and to generalize the formula that connects the mixed discriminant with the sparse resultant. Further, we are given a system of n ⩾ 2 homogeneous polynomials in n variables which is equivariant with respect to the symmetric group of n symbols. We then prove that its resultant can be decomposed into a product of several resultants that are given in terms of some divided differences. As an application, we obtain a decomposition formula for the discriminant. The second Problem is computing the Minkowski decomposition of a polytope and the third one was the problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. We present an algorithm for computing all Minkowski Decompositions (MinkDecomp) of a given convex, integral d-dimensional polytope. Further, we consider the approximation of two NP-hard problems: Minkowski Decomposition (MinkDecomp) of lattice polygons in the plane and the closely related problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. In kD-SS, a multiset S of k-dimensional vectors is given, along with a target vector t, and one must decide whether there exists a subset of S that sums up to t. We prove, through a gap-preserving reduction from Set Cover that, for general dimension k, the corresponding optimization problem kD-SS-opt is not in APX, although the classic 1D-SS-opt has a PTAS. On the positive side, we present an approximation algorithm for 2D-SS-opt, where ε > 0 bounds the additive error in terms of some property of the input. By a reduction of the optimization version of MinkDecomp to 2D-SS-opt we approximate the former.
Liste complète des métadonnées

Cited literature [88 references]  Display  Hide  Download

https://hal.inria.fr/tel-01671507
Contributor : Ioannis Emiris <>
Submitted on : Friday, January 5, 2018 - 11:34:34 AM
Last modification on : Wednesday, October 10, 2018 - 10:09:14 AM
Document(s) archivé(s) le : Wednesday, May 2, 2018 - 11:05:22 AM

File

PhDthesisKarasoulou.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01671507, version 1

Collections

Citation

Anna Karasoulou. Algebraic combinatorics and resultant methods for polynomial system solving. Computer Science [cs]. National and Kapodistrian University of Athens, Greece, 2017. English. ⟨tel-01671507⟩

Share

Metrics

Record views

337

Files downloads

208