Αλγεβρικοί αλγόριθμοι για την επίλυση πολυωνυμικών συστημάτων και εφαρμογές

Abstract

The main object of study in this dissertation is the sparse resultant. Resultants are defined in the sparse (or toric) context in order to exploit the structure of the polynomials as expressed by their Newton polytopes. We consider sparse elimination theory in order to describe the Newton polytope of the sparse resultant of a given overconstrained algebraic system, by enumerating equivalence classes of mixed subdivisions. In particular, we consider specializations of this resultant to a polynomial in a constant number of variables, typically up to 3. We sketch an algorithm that avoids computing the entire secondary polytope; our goal is that it examines only the silhouette of this polytope with respect to an orthogonal projection. Moreover, since determinantal formulae are not always possible, the most efficient general method for computing resultants is by rational formulae. We propose a single lifting function which yields a simple method for computing Macaulay-type formulae of sparse resultants, in the case of generalized unmixed systems, where all Newton polytopes are scaled copies of each other. As another application of sparse elimination, we consider rationally parameterized plane curves and determine the vertex representation of the implicit equation's Newton polygon.

Στην εργασία αυτή μελετάμε την αραιή ή τορική απαλοίφουσα ενός συστήματος πολυωνυμικών εξισώσεων. Αυτή είναι ένα πολυώνυμο στους συντελεστές του συστήματος, ο μηδενισμός του οποίου αποτελεί κριτήριο ύπαρξης ριζών. Οι μέθοδοι που χρησιμοποιούμε εκμεταλλεύονται την στενή σχέση αλγεβρικής και συνδυαστικής γεωμετρίας, όπως αυτή εκφράζεται μέσω του πολύτοπου του Νεύτωνα ενός πολυωνύμου. Οι στόχοι μας είναι ο υπολογισμός της αραιής απαλοίφουσας και του πολυτόπου του Νεύτωνα αυτής. Για τον πρώτο χρησιμοποιούμε πίνακες οι οποίοι υπολογίζονται μέσω μιας μεικτής υποδιαίρεσης των πολυτόπων του Νεύτωνα των πολυωνύμων του συστήματος η οποία κατασκευάζεται με χρήση μιας συνάρτησης ανύψωσης. Προτείνουμε μια συνάρτηση ανύψωσης η οποία οδηγεί σε πίνακα της απαλοίφουσας τύπου Macaulay, όταν τα πολυώνυμα έχουν πολύτοπα του Νεύτωνα τα οποία είναι βαθμωτά γινόμενα του ίδιου πολυτόπου. Για τον υπολογισμό του πολυτόπου του Νεύτωνα της αραιής απαλοίφουσας αναγόμαστε στον υπολογισμό τριγωνοποιήσεων. Τροποποιούμε έναν αλγόριθμο απαρίθμησης κανονικών τριγωνοποιήσεων ώστε να απαριθμεί μόνο κλάσεις ισοδυναμίας τους, μέσω των οποίων μπορούμε να ανακτήσουμε τις κορυφές του πολυτόπου της απαλοίφουσας. Τέλος, δίνουμε μια πλήρη περιγραφή του πολυτόπου του Νεύτωνα της αλγεβρικής εξίσωσης μιας παραμετρικής καμπύλης χρησιμοποιώντας μια ειδική προβολή του πολυτόπου της απαλοίφουσας κατάλληλου συστήματος εξισώσεων. Το πολύτοπο αυτό το υπολογίζουμε μέσω τριγωνοποιήσεων και μεικτών υποδιαιρέσεων.