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

Η διδακτορική διατριβή της Άννας Καρασούλου επικεντρώνεται στην επίλυση πολυωνυμικών συστημάτων χρησιμοποιώντας εργαλεία από την αλγεβρική και την συνδυαστική γεωμετρία. Η χρήση συνδυαστικών μεθόδων κατέστη απαραίτητη για την εκμετάλλευση της δομής και της αραιότητας των πολυωνυμικών εξισώσεων. Περιγράφονται επίσης γεωμετρικοί αλγορίθμοι για την διάσπαση πολυτόπων κατά 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.