Αλγόριθμος Μπούχμπεργκερ

Στη θεωρία των πολυμεταβλητών πολυωνύμων, ο αλγόριθμος Μπούχμπεργκερ είναι μια μέθοδος για τη μετατροπή ενός δεδομένου συνόλου πολυωνύμων σε μια βάση Γκρέμπνερ, η οποία είναι ένα άλλο σύνολο πολυωνύμων που έχουν τα ίδια κοινά μηδενικά και είναι πιο κατάλληλο για την εξαγωγή πληροφοριών σχετικά με αυτά τα κοινά μηδενικά. Εισήχθη από τον Μπρούνο Μπούχμπεργκερ ταυτόχρονα με τον ορισμό των βάσεων Γκρέμπνερ.

Ο Ευκλείδειος αλγόριθμος για τον υπολογισμό του μεγαλύτερου κοινού διαιρέτη πολυωνύμων και η απαλοιφή γραμμικών συστημάτων κατά Γκάους είναι ειδικές περιπτώσεις του αλγορίθμου του Μπούχμπεργκερ όταν ο αριθμός των μεταβλητών ή οι βαθμοί των πολυωνύμων είναι αντίστοιχα ίσοι με ένα.

Για άλλους αλγορίθμους της βάσης Γκρέμπνερ, βλέπε βάση Γκρέμπνερ § Αλγόριθμοι και υλοποιήσεις.

Αλγόριθμος 
Μια απλή εκδοχή αυτού του αλγορίθμου για την εύρεση μιας βάσης για ένα ιδανικό  ενός πολυωνυμικού δακτυλίου R έχει ως εξής:

Είσοδος Ένα σύνολο πολυωνύμων F που παράγει 
Έξοδος Μια βάση Γκρέμπνερ G για το 
 G := F
 Για κάθε fi, fj στο G, δηλώνουμε με gi τον κορυφαίο όρο του fi σε σχέση με τη δεδομένη μονωνυμική διάταξη και με aij το ελάχιστο κοινό πολλαπλάσιο των gi και gj.
 Επιλέγουμε δύο πολυώνυμα στο G και έστω  (Σημειώστε ότι οι κορυφαίοι όροι εδώ θα ακυρωθούν από την κατασκευή).
 Μειώστε το Sij, με τον αλγόριθμο πολυμεταβλητής διαίρεσης σε σχέση με το σύνολο G μέχρι το αποτέλεσμα να μην είναι πλέον αναγώγιμο. Εάν το αποτέλεσμα είναι μη μηδενικό, προσθέστε το στο G.

Το πολυώνυμο Sij αναφέρεται συνήθως ως S-πολυώνυμο, όπου το S αναφέρεται στην αφαίρεση (Μπούχμπεργκερ)) ή στη συζυγία (άλλοι). Το ζεύγος πολυωνύμων με το οποίο συνδέεται αναφέρεται συνήθως ως κρίσιμο ζεύγος.

Υπάρχουν πολυάριθμοι τρόποι βελτίωσης αυτού του αλγορίθμου πέραν των όσων αναφέρθηκαν παραπάνω. Παραδείγματος χάριν, θα μπορούσε κανείς να ελαττώσει όλα τα νέα στοιχεία του F σε σχέση μεταξύ τους πριν τα προσθέσει. Αν οι κορυφαίοι όροι των fi και fj δεν έχουν κοινές μεταβλητές, τότε το Sij θα ανάγεται πάντα στο 0 (αν χρησιμοποιούμε μόνο τα  και  για αναγωγή), οπότε δεν χρειάζεται να το υπολογίσουμε καθόλου.

Ο αλγόριθμος τερματίζει επειδή αυξάνει σταθερά το μέγεθος του μονωνυμικού ιδεώδους που παράγεται από τους κορυφαίους όρους του συνόλου F μας, και το λήμμα του Ντίκσον (ή το θεώρημα βάσης Χίλμπερτ) εγγυάται ότι οποιαδήποτε τέτοια αύξουσα αλυσίδα πρέπει τελικά να γίνει σταθερή.

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

,

όπου  είναι ο αριθμός των μεταβλητών και  ο μέγιστος συνολικός βαθμός των πολυωνύμων εισόδου. Αυτό επιτρέπει, θεωρητικά, τη χρήση γραμμικής άλγεβρας πάνω στο διανυσματικό χώρο των πολυωνύμων βαθμού που περιορίζεται από αυτή την τιμή, για να πάρουμε έναν αλγόριθμο πολυπλοκότητας.

.

και το παραπάνω άνω όριο πολυπλοκότητας είναι βέλτιστο. Ωστόσο, τέτοια παραδείγματα είναι εξαιρετικά σπάνια.

Από την ανακάλυψή του, έχουν εισαχθεί πολλές παραλλαγές του Μπούχμπεργκερ για τη βελτίωση της αποτελεσματικότητάς του. Οι αλγόριθμοι F4 και F5 του Φογκέρ είναι σήμερα οι πιο αποδοτικοί αλγόριθμοι για τον υπολογισμό βάσεων Γκρόμπνερ και επιτρέπουν τον υπολογισμό βάσεων Γκρόμπνερ ρουτίνας που αποτελούνται από πολλές εκατοντάδες πολυώνυμα, με το καθένα από αυτά να έχει πολλές εκατοντάδες όρους και συντελεστές πολλών εκατοντάδων ψηφίων.

Δημοσιεύσεις 


 David Cox, John Little, and Donald O'Shea (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer.  .
 Vladimir P. Gerdt, Yuri A. Blinkov (1998). Involutive Bases of Polynomial Ideals, Mathematics and Computers in Simulation, 45:519ff
The Buchberger Algorithm as a Tool for Ideal Theory of Polynomial Rings in Constructive Mathematics

Δείτε επίσης

 Learning Selection Strategies in Buchberger’s Algorithm

Εξωτερικοί σύνδεσμοι  
English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
"Buchberger algorithm", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Buchberger's algorithm on Scholarpedia
Weisstein, Eric W. "Buchberger's Algorithm". MathWorld.

Παραπομπές

Σημειώσεις

H. Matsumura, Commutative algebra 1980 .

; reprinted by R. E. Krieger Pub. Co (1975) 



Κατηγορία:Αλγεβρική γεωμετρία
Κατηγορία:Αλγόριθμοι
Κατηγορία:Αντιμεταθετική άλγεβρα
Κατηγορία:Επιστήμη υπολογιστών