Ορίζουσα: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Γραμμή 428:
===Επιπρόσθετες μέθοδοι===
Αν η ορίζουσα του ''A'' και ο αντίστροφος του ''A'' έχουν ήδη υπολογιστεί, το [[λήμμα ορίζουσας πίνακα]] μας επιτρέπει να υπολογίσουμε γρήγορα την ορίζουσα του {{nowrap|''A'' + ''uv''<sup>T</sup>}}, όπου ''u'' και ''v'' είναι διανύσματα στήλης.
Δεδομένου ότι ο ορισμός της ορίζουσας δεν χρειάζεται διαιρέσεις, προκύπτει ένα ερώτημα: υπάρχουν γρήγοροι αλγόριθμοι που δεν χρειάζονται διαιρέσεις; Αυτό είναι ιδιαίτερα ενδιαφέρον για τους πίνακες πάνω σε δακτυλίους. Πράγματι αλγόριθμοι με χρόνο εκτέλεσης αναλογικά με το ''n''<sup>4</sup> υπάρχει. Ένας αλγόριθμος από τον Mahajan, τον Vinay, και τον Berkowitz<ref>http://page.inf.fu-berlin.de/~rote/Papers/pdf/Division-free+algorithms.pdf</ref> είναι βασισμένος σε κλειστούς διατεταγμένους περιπάτους. Υπολογίζει περισσότερα γινόμενα από όσα απαιτεί ο ορισμός της ορίζουσας, αλλά μερικά από αυτά τα γινόμενα ακυρώνονται και το άθροισμα τους μπορεί να υπολογιστεί ικανοποιητικά. Ο τελικός αλγόριθμος μοιάζει πολύ με ένα επαναλαμβανόμενο γινόμενο τριγωνικών πινάκων.
Αν δύο πίνακες τάξης ''n'' μπορούν να πολλαπλασιαστούν επί ''M''(''n''), όπου ''M''(''n'') ≥ ''n''<sup>''a''</sup> για κάποια ''a'' > 2, τότε η ορίζουσα μπορεί να υπολογιστεί επί O(''M''(''n'')).<ref>J.R. Bunch and J.E. Hopcroft, Triangular factorization and inversion by fast matrix multiplication, ''Mathematics of Computation'', 28 (1974) 231–236.</ref> Αυτό σημαίνει, για παράδειγμα, ότι ένας O(''n''<sup>2.376</sup>) αλγόριθμος υπάρχει βασισμένος στον [[αλγόριθμος Coppersmith–Winograd|αλγόριθμο Coppersmith–Winograd]].
Οι αλγόριθμοι μπορούν επίσης να αξιολογούνται σύμφωνα με πολυπλοκότητα των bit, δηλ., πόσα bits ακρίβειας χρειάζονται για να αποθηκευτούν οι ενδιάμεσες τιμές που συμβαίνουν στον υπολογισμό. Για παράδειγμα, η [[απαλοιφή του Gauss]] (ή LU ανάλυση) μέθοδοι είναι της τάξης O(''n''<sup>3</sup>), αλλά το μήκος των bit των ενδιαμέσων τιμών μπορεί μπορεί να γίνει εκθετικά μεγάλο.<ref>{{Cite conference
| first1 = Xin Gui
| last1 = Fang
| first2 = George
| last2 = Havas
| title = On the worst-case complexity of integer Gaussian elimination
| booktitle = Proceedings of the 1997 international symposium on Symbolic and algebraic computation
| conference = ISSAC '97
| pages = 28–31
| publisher = ACM
| year = 1997
| location = Kihei, Maui, Hawaii, United States
| url = http://perso.ens-lyon.fr/gilles.villard/BIBLIOGRAPHIE/PDF/ft_gateway.cfm.pdf
| doi = 10.1145/258726.258740
| isbn = 0-89791-875-4}}</ref> Ο [[αλγόριθμος Bareiss]],από την άλλη μεριά, είναι μια ακριβής μέθοδος διαίρεσης βασίζεται στην [[θεώρημα οριζουσών του Sylvester theorem|ταυτότητα του Sylvester]] είναι επίσης τάξης ''n''<sup>3</sup>, αλλά η περιπλοκότητα των bit είναι περίπου το μέγεθος των bit των αρχικών στοιχείων του πίνακα επί ''n''.<ref>{{citation|first=Erwin|last=Bareiss|title= Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination|pages=565–578|url=http://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf|journal=Mathematics of computation|year=1968|volume=22|issue=102}}</ref>
==Ιστορία==
| |||