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

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

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

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

Αλγόριθμος

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

Είσοδος Ένα σύνολο πολυωνύμων F που παράγει I

Έξοδος Μια βάση Γκρέμπνερ G για το I

1. G := F
2. Για κάθε f_i, f_j στο G, δηλώνουμε με g_i τον κορυφαίο όρο του f_i σε σχέση με τη δεδομένη μονωνυμική διάταξη και με a_ij το ελάχιστο κοινό πολλαπλάσιο των g_i και g_j.
3. Επιλέγουμε δύο πολυώνυμα στο G και έστω S_ij = a_ij/ g_i f_i − a_ij/ g_j f_j (Σημειώστε ότι οι κορυφαίοι όροι εδώ θα ακυρωθούν από την κατασκευή).
4. Μειώστε το S_ij, με τον αλγόριθμο πολυμεταβλητής διαίρεσης σε σχέση με το σύνολο G μέχρι το αποτέλεσμα να μην είναι πλέον αναγώγιμο. Εάν το αποτέλεσμα είναι μη μηδενικό, προσθέστε το στο G.

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

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

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

Πολυπλοκότητα

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

$2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}$,

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

$d^{2^{n+o(1)}}$.

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

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

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

• Buchberger, B. (August 1976). «Theoretical Basis for the Reduction of Polynomials to Canonical Forms». ACM SIGSAM Bulletin (ACM) 10 (3): 19–29. doi:10.1145/1088216.1088219. MR 0463136. 
• David Cox, John Little, and Donald O'Shea (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer. (ISBN 0-387-94680-2).
• 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 (ISBN 0-8053-7026-9).
• Nagata, Masayoshi (1956), «On the chain problem of prime ideals», Nagoya Math. J. 10: 51–64, doi:10.1017/S0027763000000076, http://projecteuclid.org/euclid.nmj/1118799769 
• Nagata, Masayoshi (1962), Local rings, Interscience Tracts in Pure and Applied Mathematics, 13, New York-London: Interscience Publishers, a division of John Wiley & Sons ; reprinted by R. E. Krieger Pub. Co (1975) (ISBN 0-88275-228-6)