Μελέτη και επίλυση πολυωνυμικών συστημάτων με χρήση αλγεβρικών και συνδυαστικών μεθόδων

Abstract

The 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.

Η διδακτορική διατριβή της Άννας Καρασούλου επικεντρώνεται στην επίλυση πολυωνυμικών συστημάτων χρησιμοποιώντας εργαλεία από την αλγεβρική και την συνδυαστική γεωμετρία. Η χρήση συνδυαστικών μεθόδων κατέστη απαραίτητη για την εκμετάλλευση της δομής και της αραιότητας των πολυωνυμικών εξισώσεων. Περιγράφονται επίσης γεωμετρικοί αλγορίθμοι για την διάσπαση πολυτόπων κατά Minkowski, με απώτερη εφαρμογή την παραγοντοποίηση των αντίστοιχων πολυωνύμων στο πλαίσιο της εκμετάλλευσης της αραιότητάς τους. Η κ. Άννα Καρασούλου αντιμετώπισε με επιτυχία ορισμένα μη τετριμμένα προβλήματα, τα οποία επιγραμματικά αναφέρουμε εδώ και τα αναλύουμε στην συνέχεια.Το πρώτο πρόβλημα είναι ο υπολογισμός τύπου της αραιής απαλοίφουσας (sparse resultant) και της αραιής διακρίνουσας (sparse discriminant) [14], [29], [39], με χρήση της δομής των εξισώσεων. Επιπλέον μελετήθηκε και βρέθηκε κλειστός τύπος για τον βαθμό της διακρίνουσας και της απαλοίφουσας πολυωνυμικών εξισώσεων καθώς και η μεταξύ τους σχέση.Ειδικότερα, διενεργήθηκε μελέτη τύπων για τον βαθμό της αραιής (μεικτής) διακρίνουσας και της αραιής απαλοίφουσας πολυωνυμικών εξισώσεων. Ο σκοπός της μελέτης αυτής είναι να διερευνηθεί ο τρόπος υπολογισμού της αραιής διακρίνουσας ενός καλώς ορισμένου συστήματος μέσω ενός τύπου που την συνδέει με την αραιή απαλοίφουσα ενός υπερπροσδιορισμένου πολυωνυμικού συστήματος, εξετάζοντας τα αραιά πολυώνυμα μέσω της θεωρίας των πολυτόπων του Νεύτωνα. Στα πλαίσια της μελέτης αυτής προέκυψαν δύο ερευνητικές εργασίες [39], [29], οι οποίες περιγράφονται αναλυτικά στα κεφάλαια 4 και 6. Στο κεφάλαιο 4 μελετάται η σχέση της αραιής διακρίνουσας και της απαλοίφουσας με έμφαση στις εφαρμογές της διακρίνουσας. Μελετάται η σχέση της αραιής διακρίνουσας με την αραιή απαλοίφουσα του συστήματος των πολυωνύμων επαυξημένου με τον Τορικό Ιακωβιανό πίνακα του συστήματος. Η σχέση αυτή οδηγεί σε έναν τύπο για την αραιή διακρίνουσα, ο οποίος επιτρέπει τον υπολογισμό της αποτελεσματικά, χωρίς την εισαγωγή νέων μεταβλητών, όπως γίνεται με τη μέθοδο του Cayley. Δίνεται επίσης μία απόδειξη για τον συνολικό βαθμό της αραιής διακρίνουσας 2 πολυωνύμων, καθώς και ένας τύπος για την αραιή διακρίνουσα όταν ένα εκ των πολυωνύμων παραγοντοποιείται, χρησιμοποιώντας τα πολύτοπα του Νεύτωνα.Στο κεφάλαιο 5 περιγράφεται η μελέτη που διενεργήθηκε , πάνω στην διακρίνουσα των ομογενών συμμετρικών πολυωνύμων, δηλαδή των αναλλοίωτων συστημάτων κάτω από την δράση της συμμετρικής ομάδας. Αναζητήθηκε και βρέθηκε κλειστός τύπος για τον υπολογισμό της απαλοίφουσας και της διακρίνουσας τέτοιου συστήματος.Το δεύτερο πρόβλημα το οποίο αντιμετώπισε είναι το NP-δύσκολο πρόβλημα του υπολογισμού της διάσπασης πολυτόπων κατά Minkowski με χρήση προσεγγιστικών [41] και αλγορίθμων ακριβείας [36], καθώς και η μελέτη του προβλήματος του αθροίσματος υποσυνόλων (subset sum) σε αυθαίρετη διάσταση [41].Στο κεφάλαιο 7 μελετάται και προτείνεται αλγόριθμος για τον υπολογισμό όλων των μη τετριμμένων, ανάγωγων διασπάσεων κατά Minkowski, ενός οποιουδήποτε κυρτού πολυτόπου διάστασης d, το οποίο έχει κορυφές με ακέραιες συντεταγμένες. Για τον υπολογισμό αυτό μελετήθηκε ο κώνος όλων των συνδυαστικά ισοδύναμων πολυτόπων. Η υλοποίηση δίνεται σε Sage.Στο κεφάλαιο 8 μελετώνται δύο NP-δύσκολα προβλήματα: το πρόβλημα της διάσπασης κατά Minkowski των ακέραιων πολυτόπων στο επίπεδο και το πρόβλημα του αθροίσματος υποσυνόλων (Subset sum) σε αυθαίρετη διάσταση (kD-SS). Στο πρόβλημα απόφασης δίνεται ένα σύνολο S από διανύσματα διάστασης k, ένα διάνυσμα στόχος t και πρέπει να αποφασιστεί αν υπάρχει ένα υποσύνολο του S το οποίο αθροίζει στο t. Στο αντίστοιχο πρόβλημα βελτιστοποίησης ζητείται υποσύνολο ώστε το αντίστοιχο άθροισμα να προσεγγίζει το διάνυσμα στόχο. Αποδεικνύουμε μέσω αναγωγής από το Set Cover ότι για γενική διάσταση k το αντίστοιχο πρόβλημα βελτιστοποίησης kD-SS-opt δεν είναι ΑPX παρόλοπου το κλασικό πρόβλημα 1D-SS-opt έχει PTAS. Η προσέγγισή μας σχετίζει το kD-SS με το πρόβλημα του Closest Vector. Παρουσιάζουμε έναν O(n3/ϵ2) προσεγγιστικό αλγόριθμο για το 2D-SS-opt, όπου n είναι ο πληθάριθμος του S και ϵ > 0 φράσσει το αθροιστικό σφάλμα και σχετίζεται με μία ιδιότητα του δοθέντος αντικειμένου από τον χρήστη. Μετά από μία αναγωγή από το πρόβλημα βελτιστοποίησης της διάσπασης κατά Minkowski στο 2D-SS-opt προσεγγίζουμε το εξής: Δοθέντος ενός πολυγώνου Q και μίας παραμέτρου ϵ > 0 , υπολογίζουμε τα δύο πολύτοπα της διάσπασης και , όπου Q′ = A + B είναι τέτοιο ώστε το Q και το Q′ διαφέρουν κατά O(ϵD), όπου D η διάμετρος του Q, ή η Hausdorff απόσταση του Q από το Q′ είναι O(ϵD). Η υλοποίηση διατίθεται στο Github.