National and Kapodistrian University of Athens
Μελέτη και επίλυση πολυωνυμικών συστημάτων με χρήση αλγεβρικών και συνδυαστικών μεθόδων
Abstract
dc:descriptionThe contribution of the thesis is threefold. We worked on Problems in the areas of algebraic algorithms, computational geometry and algebraic combinatorics. 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 main 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. The results of this work are presented in Chapter 4 and 6 of the thesis and have been published in [39] and [29] . In Chapter 5 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 of a multivariate homogeneous symmetric polynomial. The results of this work have been published in [14].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.Firstly, we present an algorithm for computing all Minkowski Decompositions (MinkDecomp) of a given convex, integral d-dimensional polytope, using the cone of combinatorially equivalent polytopes. An implementation is given in sage. The results of this work are presented in Chapter 7 of the thesis and have been published in [36] .Secondly, 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. Our approach relates kD-SS with the well studied Closest Vector Problem. On the positive side, we present a O(n3/ϵ2) approximation algorithm for 2D-SS-opt, where n is the cardinality of the multiset and ϵ > 0 bounds the additive error in terms of some property of the input. We state two variations of this algorithm, which are more suitable for implementation. Employing a reduction of the optimization version of MinkDecomp to 2D-SS-opt we approximate the former: For an input polygon Q and parameter ϵ > 0, we compute summand polygons A and B, where Q′ = A + B is such that some geometric function differs on Q and Q′ by O(ϵD), where D is the diameter of Q, or the Hausdorff distance between Q and Q′ is also in O(ϵD). We conclude with experimental results based on our implementations. The results of this work are presented in Chapter 8 of the thesis and have been published in [41],[40].Finally, in Chapter 9 we provide extensions and open problems.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2017
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Karasoulou, Anna
- Καρασούλου, Άννα
Subjects
dc:subject × 16Rights
dc:rights- Statement dc:rights
-
- BY_NC_ND
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/45663