Ο όρος «πίνακας mxn» περιγράφει διατάξεις m επί n στοιχείων, τοποθετημένα σε m σειρές και n στήλες:
Αν και μερικοί θεωρούν αυτά τα μαθηματικά αντικείμενα ως άχρηστα αποκυήματα της φαντασίας των μαθηματικών που προκαλούν δυστυχία στους μαθητές, η χρησιμότητά τους στον προγραμματισμό των υπολογιστών είναι ανεκτίμητη, π.χ. στην επίλυση γραμμικών εξισώσεων στα μοντέλα πρόβλεψης του καιρού, την επεξεργασία ψηφιακών βίντεο ή την κατασκευή γραφικών κ.ά. Ένας λόγος που οι πίνακες έχουν τεράστια σημασία στην επιστήμη των υπολογιστών είναι ότι μπορούμε να ορίσουμε τις πράξεις της πρόσθεσης και κυρίως του πολλαπλασιασμού μεταξύ πινάκων.
Σημαντικό ρόλο στους αλγορίθμους παίζει το πόσο σύντομη είναι η μέθοδος με την οποία γίνεται ο πολλαπλασιασμός των πινάκων, ώστε εξοικονομείται υπολογιστικός χρόνος. Σε μια πρόσφατη δημοσίευση με τίτλο «A Refined Laser Method and Faster Matrix Multiplication» , οι Josh Alman και Vassilevska Williams εκτός του ότι θέτουν το ταχύτερο ρεκόρ όσον αφορά τον πολλαπλασιασμό δύο πινάκων, σηματοδοτούν επίσης και το τέλος της μεθόδου βελτίωσης στην οποία βασίζονταν οι μαθηματικοί εδώ και δεκαετίες.
Αλλά ας πάρουμε τα πράγματα από την αρχή. Γενικά, δυο πίνακες mxn και nxp μπορούν να πολλαπλασιαστούν μεταξύ τους και να δώσουν έναν νέο πίνακα mxp. Αν περιοριστούμε στους τετραγωνικούς πίνακες nxn (οι στήλες είναι όσες και οι γραμμές), τότε από το γινόμενο δυο πινάκων nxn (n2 στοιχεία ο καθένας) θα προκύψει ένας νέος πίνακας nxn που θα περιέχει επίσης n2 στοιχεία. Έτσι, για να εκτελέσουμε έναν τέτοιο πολλαπλασιασμό απαιτούνται τουλάχιστον n2 βήματα. Αλλά αυτός ο ο στόχος ανήκει στην σφαίρα της μυθολογίας.
Εμείς οι αρχάριοι, για να εκτελέσουμε το γινόμενο δυο πινάκων nxn μεταξύ τους, θα πραγματοποιήσουμε n3 πολλαπλασιασμούς μεταξύ των στοιχείων του πίνακα. Αν για παράδειγμα πολλαπλασιάσουμε δυο πίνακες 2×2, τότε προκύπτει ένας πίνακας επίσης 2×2 που περιέχει 4 στοιχεία τα οποία υπολογίζονται ως εξής:
Παρατηρείστε ότι για να βρούμε το γινόμενο των 2×2 πινάκων απαιτούνται 8=23 πολλαπλασιασμοί. Για το γινόμενο πινάκων 3×3 απαιτούνται 27= 33 πολλαπλασιασμοί και για το γινόμενο πινάκων 4×4 χρειάζονται 64= 43 πολλαπλασιασμοί. Βέβαια, αυξάνεται και ο αριθμός των προσθέσεων που απαιτούνται, αλλά είναι σαφώς μικρότερος από τους απαιτούμενους πολλαπλασιασμούς. Και αν ληφθεί υπόψιν ότι η διαδικασία πραγματοποίησης ενός πολλαπλασιασμού μεταξύ αριθμών από τους υπολογιστές είναι σαφώς πιο περίπλοκη από την πρόσθεσή τους, καταλαβαίνουμε γιατί οι ερευνητές μετρούν την ταχύτητα εκτέλεσης του γινομένου πινάκων καθαρά από την άποψη του αριθμού των απαιτούμενων πολλαπλασιασμών. Οι προσθέσεις αγνοούνται.
Για αιώνες λοιπόν οι μαθηματικοί θεωρούσαν ότι για να πάρουν το αποτέλεσμα του γινομένου δυο πινάκων nxn χρειάζονται n3 πολλαπλασιασμοί. To 1969 o Volker Strassen (Gaussian elimination is not optimal) ανακάλυψε έναν τρόπο να εκτελεί το γινόμενο μεταξύ πινάκων 2×2 χρησιμοποιώντας λιγότερους από 23=8 πολλαπλασιασμούς. Διαμέσου ενός περίπλοκου συνόλου σχέσεων αντικατέστησε έναν από αυτούς τους 8 πολλαπλασιασμούς με 14 επιπλέον προσθέσεις. Αυτό δεν φαίνεται να κάνει κάποια διαφορά, αλλά αποδίδει εξαιτίας των δυσκολιών του πολλαπλασιασμού έναντι της πρόσθεσης. Και με την εύρεση ενός τρόπου που μας γλιτώνει από έναν μόνο πολλαπλασιασμό στο γινόμενο μικρών πινάκων 2×2, ο Strassen άνοιξε την κερκόπορτα που θα μπορούσε να εκμεταλλευτεί για να μειώσει την ταχύτητα εκτέλεσης γινομένων με μεγαλύτερους πίνακες.
Ένα ελάχιστο βήμα στο γινόμενο 2×2 πινάκων οδηγεί σε τεράστιες βελτιώσεις στα γινόμενα μεγάλων πινάκων. Ας πούμε, για παράδειγμα, ότι θέλετε να πολλαπλασιάσετε ένα ζεύγος πινάκων 8×8. Ένας τρόπος να το κάνετε είναι να χωρίσετε κάθε μεγάλο πίνακα σε τέσσερις πίνακες 4×4, οπότε ο καθένας έχει 4 στοιχεία. Επειδή ένας πίνακας μπορεί να έχει στοιχεία που είναι και τα ίδια πίνακες, δείτε τους αρχικούς πίνακες ως ζεύγος πινάκων 2×2, καθένας από τους οποίους περιέχει 4 στοιχεία που είναι πίνακες 4×4. Στην συνέχεια αυτοί οι πίνακες 4×4 μπορούν επίσης να χωριστούν σε 4 πίνακες 2×2.
Το νόημα αυτής της μείωσης – της επανειλημμένης διάσπασης μεγαλύτερων πινάκων σε μικρότερους πίνακες – είναι ότι μπορούμε να εφαρμόσουμε τον αλγόριθμο του Strassen ξανά και ξανά σε μικρότερους πίνακες, κερδίζοντας τα πλεονεκτήματα της μεθόδου του σε κάθε βήμα. Συνολικά, ο αλγόριθμος του Strassen βελτίωσε την ταχύτητα του γινομένου πινάκων από n3 ενδιάμεσα βήματα πολλαπλασιασμών σε n2,81.
Η επόμενη μεγάλη βελτίωση πραγματοποιήθηκε στα τέλη της δεκαετίας του 1970, με ένα νέο τρόπο προσέγγισης του προβλήματος. Περιλαμβάνει την «μετάφραση» του πολλαπλασιασμού πινάκων σε ένα διαφορετικό υπολογιστικό πρόβλημα της γραμμικής άλγεβρας που περιλαμβάνει αντικείμενα που ονομάζονται τανυστές. Οι συγκεκριμένοι τανυστές που χρησιμοποιούνται σε αυτό το πρόβλημα είναι τρισδιάστατες διατάξεις αριθμών που αποτελούνται από πολλά διαφορετικά μέρη, καθένα από τα οποία μοιάζει με ένα μικρό πρόβλημα πολλαπλασιασμού πινάκων. Το γινόμενο πινάκων και το πρόβλημα που αφορά τους τανυστές είναι ισοδύναμα μεταξύ τους, αλλά οι ερευνητές είχαν ήδη ταχύτερες διαδικασίες για την επίλυση του τελευταίου. Το 1981 ο Arnold Schönhage χρησιμοποίησε αυτήν την προσέγγιση για να αποδείξει ότι είναι δυνατό να εκτελεστεί γινόμενο πινάκων σε n2.522 βήματα (πολλαπλασιασμών). Ο Strassen ονόμασε αυτή την προσέγγιση ως «μέθοδο λέιζερ».
Στο γράφημα που ακολουθεί βλέπουμε τις διαδοχικές βελτιώσεις στο γινόμενο πινάκων όσον αφορά τους απαιτούμενους πολλαπλασιασμούς μεταξύ των στοιχείων πινάκων nxn, από το πρωτόγονο n3 μέχρι το σημερινό n2.37286.
Η Vassilevska Williams θυμάται μια συνομιλία που είχε κάποτε με τον πρωτοπόρο Strassen: «Τον ρώτησα αν νομίζει ότι θα μπορούσαμε να φτάσουμε το όριο στον αριθμό των στοιχείων του πίνακα nxn, δηλαδή στο n2. Η απάντησή του ήταν: όχι, όχι, όχι, όχι, όχι».
διαβάστε περισσότερες λεπτομέρειες ΕΔΩ: https://www.quantamagazine.org/mathematicians-inch-closer-to-matrix-multiplication-goal-20210323/
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου
Το blog TEO O ΜΑΣΤΟΡΑΣ ουδεμία ευθύνη εκ του νόμου φέρει σχετικά σε άρθρα που αναδημοσιεύονται από διάφορα ιστολόγια. Δημοσιεύονται όλα για την δική σας ενημέρωση.