Αραιοί πίνακες

Παράδειγμα αραιού πίνακα $\left({\begin{smallmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&99\\\end{smallmatrix}}\right)$
Ο παραπάνω αραιός πίνακας περιέχει μόνο 9 μη μηδενικά στοιχεία, με 26 μηδενικά στοιχεία. Η αραιότητά του είναι 74% και η πυκνότητά του είναι 26%.

Στην αριθμητική ανάλυση και τους επιστημονικούς υπολογισμούς, ένας αραιός πίνακας είναι ένας πίνακας στον οποίο τα περισσότερα στοιχεία είναι μηδενικά^[1]. Δεν υπάρχει αυστηρός ορισμός του ποσοστού των μηδενικών στοιχείων για να θεωρείται ένας πίνακας αραιός, αλλά ένα κοινό κριτήριο είναι ότι ο αριθμός των μη μηδενικών στοιχείων είναι περίπου ίσος με τον αριθμό των γραμμών ή των στηλών. Αντιθέτως, εάν τα περισσότερα στοιχεία είναι μη μηδενικά, ο πίνακας θεωρείται πυκνός^[1]. Ο αριθμός των μηδενικών στοιχείων διαιρεμένος με τον συνολικό αριθμό των στοιχείων (παραδείγματος χάριν, m × n για έναν πίνακα m × n) ονομάζεται μερικές φορές αραιότητα του πίνακα.

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

Κατά την αποθήκευση και τον χειρισμό αραιών πινάκων σε έναν υπολογιστή, είναι χρήσιμο και συχνά απαραίτητο να χρησιμοποιούνται εξειδικευμένοι αλγόριθμοι και δομές δεδομένων που εκμεταλλεύονται την αραιή δομή του πίνακα. Για τους αραιούς πίνακες κατασκευάστηκαν εξειδικευμένοι υπολογιστές^[2], καθώς είναι συνηθισμένοι στον τομέα της μηχανικής μάθησης^[3]. Οι λειτουργίες που χρησιμοποιούν τις τυπικές δομές και αλγορίθμους πυκνών πινάκων είναι αργές και αναποτελεσματικές όταν εφαρμόζονται σε μεγάλους αραιούς πίνακες, καθώς η επεξεργασία και η μνήμη σπαταλώνται στα μηδενικά. Τα αραιά δεδομένα είναι εκ φύσεως ευκολότερο να συμπιεστούν και συνεπώς απαιτούν πολύ λιγότερη αποθήκευση. Ορισμένοι πολύ μεγάλοι αραιοί πίνακες είναι ανέφικτο να χειριστούν με τη χρήση τυπικών αλγορίθμων πυκνών πινάκων.

Ειδικές περιπτώσεις[Επεξεργασία | επεξεργασία κώδικα]

Προσαρμοσμένες[Επεξεργασία | επεξεργασία κώδικα]

Ένας σημαντικός ειδικός τύπος αραιών πινάκων είναι ο πίνακας ζώνης, ο οποίος ορίζεται ως εξής. Το κατώτερο εύρος ζώνης ενός πίνακα $A$ είναι ο μικρότερος αριθμός $p$ τέτοιος ώστε η είσοδος $a i, j$ να εξαφανίζεται κάθε φορά που $i > j + p$ . Ομοίως, το ανώτερο εύρος ζώνης είναι ο μικρότερος αριθμός p τέτοιος ώστε $a i, j = 0$ κάθε φορά που $i < j - p$ (Golub & Van Loan 1996, §1.2.1). Για παράδειγμα, ένας τριδιαγώνιος πίνακας έχει κατώτερο εύρος ζώνης $1$ . και ανώτερο εύρος ζώνης $1$ . Ως άλλο παράδειγμα, ο ακόλουθος αραιός πίνακας έχει κατώτερο και ανώτερο εύρος ζώνης και τα δύο ίσα με 3. Σημειώστε ότι τα μηδενικά αναπαρίστανται με τελείες για λόγους σαφήνειας.

${\begin{bmatrix}X&X&X&\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &X&X&\cdot &\cdot &\\X&\cdot &X&\cdot &X&\cdot &\cdot &\\\cdot &X&\cdot &X&\cdot &X&\cdot &\\\cdot &X&X&\cdot &X&X&X&\\\cdot &\cdot &\cdot &X&X&X&\cdot &\\\cdot &\cdot &\cdot &\cdot &X&\cdot &X&\\\end{bmatrix}}$

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

Με αναδιάταξη των γραμμών και των στηλών ενός πίνακα $A$ μπορεί να προκύψει ένας πίνακας $A''$ με μικρότερο εύρος ζώνης. Ένας αριθμός αλγορίθμων έχει σχεδιαστεί για την ελαχιστοποίηση του εύρους ζώνης.

Διαγώνια[Επεξεργασία | επεξεργασία κώδικα]

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

Συμμετρική[Επεξεργασία | επεξεργασία κώδικα]

Ένας συμμετρικός αραιός πίνακας είναι ο πίνακας γειτνίασης ενός μη κατευθυνόμενου γράφου- μπορεί να αποθηκευτεί αποτελεσματικά με τη μορφή λίστας γειτνίασης.

Διαγώνιος μπλοκ[Επεξεργασία | επεξεργασία κώδικα]

Ένας διαγώνιος κατά μπλοκ πίνακας αποτελείται από υποπίνακες κατά μήκος των διαγώνιων μπλοκ του. Ένας block-διαγώνιος πίνακας A έχει τη μορφή $\mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1}&0&\cdots &0\\0&\mathbf {A} _{2}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &\mathbf {A} _{n}\end{bmatrix}},$

όπου $\mathbf {A} _{k}$ είναι ένας τετραγωνικός πίνακας για όλα τα ${\mathit {k}}=1,...,{\mathit {n}}$

Χρήση[Επεξεργασία | επεξεργασία κώδικα]

Μείωση της συμπλήρωσης[Επεξεργασία | επεξεργασία κώδικα]

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

Υπάρχουν και άλλες μέθοδοι εκτός από την αποσύνθεση Τσολέσκι. Οι μέθοδοι ορθογωνοποίησης (όπως η παραγοντοποίηση QR) είναι κοινές, για παράδειγμα, στην επίλυση προβλημάτων ελαχίστων τετραγώνων. Αν και η θεωρητική πλήρωση είναι πάντα η ίδια, από πρακτική άποψη τα "ψευδή μη μηδενικά" μπορεί να είναι διαφορετικά για διαφορετικές μεθόδους. Συμβολικές εκδόσεις αυτών των αλγορίθμων μπορούν να χρησιμοποιηθούν με τον ίδιο τρόπο όπως ο συμβολικός Τσολέσκι για τον υπολογισμό της χειρότερης πλήρωσης.

Επίλυση εξισώσεων αραιών πινάκων[Επεξεργασία | επεξεργασία κώδικα]

Υπάρχουν τόσο επαναληπτικές όσο και άμεσες μέθοδοι για την επίλυση αραιών πινάκων.

Οι επαναληπτικές μέθοδοι, όπως η μέθοδος της συζυγούς κλίσης και η GMRES, χρησιμοποιούν γρήγορους υπολογισμούς των παραγώγων πίνακα-διανύσματος $Ax_{i}$ , όπου ο πίνακας $A$ είναι αραιός. Η χρήση προαπαιτούμενων μπορεί να επιταχύνει σημαντικά τη σύγκλιση αυτών των επαναληπτικών μεθόδων.

Αποθήκευση[Επεξεργασία | επεξεργασία κώδικα]

Ένας πίνακας αποθηκεύεται γενικά με τη μορφή δισδιάστατου πίνακα. Κάθε καταχώρηση στον πίνακα αντιπροσωπεύει ένα στοιχείο $a i, j$ του πίνακα και είναι προσβάσιμη από τους δύο δείκτες $i$ και $j$ . Κατά σύμβαση, $i$ είναι ο δείκτης γραμμής, αριθμημένος από πάνω προς τα κάτω, και $j$ είναι ο δείκτης στήλης, αριθμημένος από αριστερά προς τα δεξιά. Για έναν πίνακα $m \times n$ το μέγεθος της μνήμης που απαιτείται για την αποθήκευση του πίνακα σε αυτή τη μορφή είναι ανάλογο του $m \times n$ (ανεξάρτητα από το γεγονός ότι πρέπει να αποθηκευτούν και οι διαστάσεις του πίνακα).

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

Οι μορφές μπορούν να χωριστούν σε δύο ομάδες:

Αυτές που υποστηρίζουν αποτελεσματική τροποποίηση, όπως DOK (Λεξικό κλειδιών), LIL ("Κατάλογος λιστών") ή COO (Κατάλογος συντεταγμένων). Αυτές χρησιμοποιούνται συνήθως για την κατασκευή των πινάκων.
Εκείνοι που υποστηρίζουν αποδοτική πρόσβαση και λειτουργίες πινάκων, όπως CSR ("Συμπιεσμένη αραιή γραμμή") ή CSC ("Συμπιεσμένη αραιή στήλη").

Λεξικό κλειδιών (DOK)[Επεξεργασία | επεξεργασία κώδικα]

Το DOK αποτελείται από ένα λεξικό το οποίο συσχετίζει ζεύγη (γραμμή, στήλη) με την τιμή των στοιχείων. Τα στοιχεία που λείπουν από το λεξικό θεωρούνται μηδενικά. Αυτή η μορφή επιτρέπει την προοδευτική κατασκευή ενός αραιού πίνακα με τυχαία σειρά, αλλά δεν επιτρέπει την επανάληψη των μη μηδενικών τιμών με λεξικογραφική σειρά. Ένας πίνακας γενικά κατασκευάζεται σε αυτή τη μορφή και στη συνέχεια μετατρέπεται σε άλλη μορφή που είναι πιο αποδοτική για την επεξεργασία ^[4].

Λίστα καταλόγων (LIL)[Επεξεργασία | επεξεργασία κώδικα]

Η LIL αποθηκεύει μία λίστα ανά σειρά, με κάθε καταχώρηση να περιέχει τον δείκτη της στήλης και την τιμή. Συνήθως, οι καταχωρήσεις αυτές ταξινομούνται με βάση τον δείκτη στήλης για ταχύτερη αναζήτηση. Αυτή είναι μια άλλη μορφή κατάλληλη για την αυξητική κατασκευή πινάκων^[5].

Κατάλογος συντεταγμένων (COO)[Επεξεργασία | επεξεργασία κώδικα]

Η λίστα συντεταγμένων αποθηκεύει έναν κατάλογο πλειάδων (γραμμή, στήλη, τιμή). Κατά προτίμηση, οι καταχωρήσεις ταξινομούνται πρώτα με βάση τον δείκτη γραμμής και μετά με βάση τον δείκτη στήλης, για να βελτιωθούν οι χρόνοι τυχαίας πρόσβασης. Αυτή είναι μια άλλη μορφή κατάλληλη για τη σταδιακή κατασκευή πινάκων.^[6]

Συμπιεσμένη αραιή σειρά (μορφή CSR, CRS ή Yale)[Επεξεργασία | επεξεργασία κώδικα]

Η συμπιεσμένη αραιή γραμμή (CSR) ή η συμπιεσμένη αποθήκευση γραμμής (CRS) ή η μορφή Yale αναπαριστά έναν πίνακα $M$ από τρεις (μονοδιάστατους) πίνακες, οι οποίοι περιέχουν αντίστοιχα μη μηδενικές τιμές, τις εκτάσεις των γραμμών και τους δείκτες των στηλών. Είναι παρόμοιο με το COO, αλλά συμπιέζει τους δείκτες γραμμών, εξ ου και το όνομα. Αυτή η μορφή επιτρέπει τη γρήγορη πρόσβαση στις γραμμές και τους πολλαπλασιασμούς πινάκων-διανυσμάτων ( $M x$ ). Η μορφή CSR χρησιμοποιείται τουλάχιστον από τα μέσα της δεκαετίας του 1960, με την πρώτη πλήρη περιγραφή να εμφανίζεται το 1967^[7].

Η μορφή CSR αποθηκεύει έναν αραιό $m \times n$ πίνακα $\mathbf {M}$ σε μορφή γραμμής χρησιμοποιώντας τρεις (μονοδιάστατους) πίνακες $(V, COL_INDEX, ROW_INDEX)$ . Έστω $NNZ$ ο αριθμός των μη μηδενικών καταχωρήσεων στο $M$ . (Σημειώστε ότι εδώ θα χρησιμοποιηθούν δείκτες με βάση το μηδέν).

Οι πίνακες $V$ και $COL_INDEX$ έχουν μήκος $NNZ$ και περιέχουν τις μη μηδενικές τιμές και τους δείκτες στήλης αυτών των τιμών αντίστοιχα.
Η $COL_INDEX$ περιέχει τη στήλη στην οποία βρίσκεται η αντίστοιχη καταχώρηση $V$ .
Ο πίνακας $ROW_INDEX$ έχει μήκος $m + 1$ και κωδικοποιεί τον δείκτη στο $V$ και $COL_INDEX$ από όπου ξεκινάει η συγκεκριμένη γραμμή. Αυτό είναι ισοδύναμο με το $ROW_INDEX[j]$ που κωδικοποιεί το συνολικό αριθμό των μη μηδενικών πάνω από τη γραμμή $j$ . Το τελευταίο στοιχείο είναι το $NNZ$ , δηλαδή ο πλασματικός δείκτης στο $V$ αμέσως μετά τον τελευταίο έγκυρο δείκτη $NNZ - 1$ .^[8]

Παραδείγματος χάριν, ο πίνακας

${\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}$

είναι ο $4 \times 4$ πίνακας με 4 μη μηδενικά στοιχεία, άρα

V         = [ 5 8 3 6 ]
COL_INDEX = [ 0 1 2 1 ]
ROW_INDEX = [ 0 1 2 3 4 ]

υποθέτοντας μια γλώσσα με μηδενικό δείκτη.

Για να εξάγουμε μια γραμμή, ορίζουμε πρώτα:

row_start = ROW_INDEX[row]
row_end   = ROW_INDEX[row + 1]

Στη συνέχεια, παίρνουμε φέτες από το V και το COL_INDEX ξεκινώντας από την αρχή της γραμμής και τελειώνοντας στο τέλος της γραμμής.

Για να εξάγουμε τη γραμμή 1 (τη δεύτερη γραμμή) αυτού του πίνακα, ορίζουμε row_start=1 και row_end=2. Στη συνέχεια κάνουμε τις φέτες V[1:2] = [8] και COL_INDEX[1:2] = [1]. Γνωρίζουμε τώρα ότι στη γραμμή 1 έχουμε ένα στοιχείο στη στήλη 1 με τιμή 8.

Στην περίπτωση αυτή, η αναπαράσταση CSR περιέχει 13 καταχωρήσεις, σε σύγκριση με 16 στον αρχικό πίνακα. Η μορφή CSR εξοικονομεί μνήμη μόνο όταν $NNZ < (m (n - 1) - 1) / 2$ .

Ένα άλλο παράδειγμα, ο πίνακας ${\begin{pmatrix}10&20&0&0&0&0\\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\end{pmatrix}}$

είναι ένας $4 \times 6$ πίνακας (24 εγγραφές) με 8 μη μηδενικά στοιχεία, οπότε

V         = [ 10 20 30 40 50 60 70 80 ]
COL_INDEX = [  0  1  1  3  2  3  4  5 ]   
ROW_INDEX = [  0  2  4  7  8 ]

Το σύνολο αποθηκεύεται ως 21 καταχωρίσεις: 8 στο $V$ , 8 στο $COL_INDEX$ και 5 στο $ROW_INDEX$ .

$ROW_INDEX$ χωρίζει τον πίνακα $V$ σε σειρές: (10, 20) (30, 40) (50, 60, 70) (80), που υποδεικνύει το δείκτη του $V$ (και $COL_INDEX$ ) όπου αρχίζει και τελειώνει κάθε σειρά,
$COL_INDEX$ ευθυγραμμίζει τις τιμές των στηλών: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Ας σημειωθεί ότι σε αυτή τη μορφή, η πρώτη τιμή της $ROW_INDEX$ είναι πάντα μηδέν και η τελευταία είναι πάντα $NNZ$ , οπότε είναι κατά κάποιο τρόπο περιττές (αν και σε γλώσσες προγραμματισμού όπου το μήκος του πίνακα πρέπει να αποθηκεύεται ρητά, η $NNZ$ δεν θα ήταν περιττή). Παρ' όλα αυτά, έτσι αποφεύγεται η ανάγκη χειρισμού μιας εξαιρετικής περίπτωσης κατά τον υπολογισμό του μήκους κάθε γραμμής, καθώς εγγυάται ότι ο τύπος $ROW_INDEX[i + 1] - ROW_INDEX[i]$ λειτουργεί για κάθε γραμμή $i$ . Επιπλέον, το κόστος μνήμης αυτής της περιττής αποθήκευσης είναι πιθανότατα ασήμαντο για έναν αρκετά μεγάλο πίνακα.

Οι (παλιές και νέες) μορφές αραιών πινάκων Yale είναι περιπτώσεις του σχήματος CSR. Η παλιά μορφή Yale λειτουργεί ακριβώς όπως περιγράφεται παραπάνω, με τρεις πίνακες- η νέα μορφή συνδυάζει τους ROW_INDEX και COL_INDEX σε έναν ενιαίο πίνακα και χειρίζεται τη διαγώνιο του πίνακα ξεχωριστά^[9].

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

Είναι πιθανό να είναι γνωστή ως η μορφή Yale επειδή προτάθηκε στην έκθεση Yale Sparse Matrix Package του 1977 από το Τμήμα Επιστήμης Υπολογιστών του Πανεπιστημιο του Γέιλ^[10].

Συμπιεσμένη αραιή στήλη (CSC ή CCS)[Επεξεργασία | επεξεργασία κώδικα]

Το CSC είναι παρόμοιο με το CSR με τη διαφορά ότι οι τιμές διαβάζονται πρώτα ανά στήλη, αποθηκεύεται ένας δείκτης γραμμής για κάθε τιμή και αποθηκεύονται δείκτες στήλης. Παραδείγματος χάριν, το CSC είναι $(val, row_ind, col_ptr)$ , όπου $val$ είναι ένας πίνακας με τις (από πάνω προς τα κάτω, και στη συνέχεια από αριστερά προς τα δεξιά) μη μηδενικές τιμές του πίνακα, $col_ptr$ είναι οι δείκτες γραμμής που αντιστοιχούν στις τιμές και, $col_ptr$ είναι ο κατάλογος των δεικτών val όπου αρχίζει κάθε στήλη. Το όνομα βασίζεται στο γεγονός ότι οι πληροφορίες για τους δείκτες στήλης είναι συμπιεσμένες σε σχέση με τη μορφή COO. Συνήθως χρησιμοποιείται μια άλλη μορφή (LIL, DOK, COO) για την κατασκευή. Αυτή η μορφή είναι αποδοτική για αριθμητικές πράξεις, τεμαχισμό στηλών και γινόμενα πινάκων-διανυσμάτων. Αυτή είναι η κλασική μορφή για τον προσδιορισμό ενός αραιού πίνακα στο MATLAB (μέσω της συνάρτησης sparse function).

Λογισμικό[Επεξεργασία | επεξεργασία κώδικα]

Πολλές βιβλιοθήκες λογισμικού υποστηρίζουν αραιούς πίνακες και παρέχουν επιλυτές για εξισώσεις αραιών πινάκων. Οι ακόλουθες είναι ανοικτού κώδικα: Οι ακόλουθες εφαρμογές είναι open-source:

SuiteSparse, σειρά αλγορίθμων αραιών πινάκων, με στόχο την άμεση επίλυση αραιών γραμμικών συστημάτων.
SPArse Matrix (spam) Πακέτο R και Python για αραιούς πίνακες.
Wolfram Language Εργαλεία για το χειρισμό αραιών πινάκων
Basic Matrix Library (bml) υποστηρίζει διάφορες μορφές αραιών πινάκων και αλγορίθμους γραμμικής άλγεβρας με δεσμεύσεις για C, C++ και Fortran.
SPARSKIT Μια βασική εργαλειοθήκη για υπολογισμούς αραιών πινάκων από το Πανεπιστήμιο της Μινεσότα.

Εξωτερικοί Σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

Gibbs, Norman E.; Poole, William G.; Stockmeyer, Paul K. (1976). «A comparison of several bandwidth and profile reduction algorithms». ACM Transactions on Mathematical Software 2 (4): 322–330. doi:10.1145/355705.355707. http://portal.acm.org/citation.cfm?id=355707.
Gilbert, John R.; Moler, Cleve; Schreiber, Robert (1992). «Sparse matrices in MATLAB: Design and Implementation». SIAM Journal on Matrix Analysis and Applications 13 (1): 333–356. doi:10.1137/0613024. http://citeseer.ist.psu.edu/gilbert91sparse.html.
Sparse Matrix Algorithms Research at the Texas A&M University.
SuiteSparse Matrix Collection
SMALL project A EU-funded project on sparse models, algorithms and dictionary learning for large-scale data.
Wolfgang Hackbusch: Iterative Solution of Large Sparse Systems of Equations, Springer, (1994).
Yousef Saad: Iterative Methods for Sparse Linear Systems, SIAM, ISBN 978-0-89871-534-7 (2003).
Timothy A. Davis: Direct Methods for Sparse Linear Systems, SIAM, ISBN 978-0-89871-613-9 (2006).

Πηγές[Επεξεργασία | επεξεργασία κώδικα]

Golub, Gene H.· Van Loan, Charles F. (1996). Matrix Computations (3rd έκδοση). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
Stoer, Josef· Bulirsch, Roland (2002). Introduction to Numerical Analysis (3rd έκδοση). Berlin, New York: Springer-Verlag. ISBN 978-0-387-95452-3.
Tewarson, Reginald P. (Μαΐου 1973). Sparse Matrices (Part of the Mathematics in Science & Engineering series). Academic Press Inc. (This book, by a professor at the State University of New York at Stony Book, was the first book exclusively dedicated to Sparse Matrices. Graduate courses using this as a textbook were offered at that University in the early 1980s).
Bank, Randolph E.· Douglas, Craig C. «Sparse Matrix Multiplication Package» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 21 Δεκεμβρίου 2014. Ανακτήθηκε στις 25 Ιανουαρίου 2024.
Pissanetzky, Sergio (1984). Sparse Matrix Technology. Academic Press. ISBN 9780125575805.
Snay, Richard A. (1976). «Reducing the profile of sparse symmetric matrices». Bulletin Géodésique 50 (4): 341–352. doi:10.1007/BF02521587. Bibcode: 1976BGeod..50..341S. Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.^[11]
Jennifer Scott and Miroslav Tuma: "Algorithms for Sparse Linear Systems", Birkhauser, (2023), DOI: https://doi.org/10.1007/978-3-031-25820-6 (Open Access Book)

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ ^1,0 ^1,1 Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). «2017 IEEE 17th International Conference on Communication Technology (ICCT)». IEEE, pp. 1880–1883. doi:10.1109/icct.2017.8359956. ISBN 978-1-5090-3944-9. «The computation kernel of DNN is large sparse-dense matrix multiplication. In the field of numerical analysis, a sparse matrix is a matrix populated primarily with zeros as elements of the table. By contrast, if the number of non-zero elements in a matrix is relatively large, then it is commonly considered a dense matrix. The fraction of zero elements (non-zero elements) in a matrix is called the sparsity (density). Operations using standard dense-matrix structures and algorithms are relatively slow and consume large amounts of memory when applied to large sparse matrices.»
↑ «Cerebras Systems Unveils the Industry's First Trillion Transistor Chip». www.businesswire.com (στα Αγγλικά). 19 Αυγούστου 2019. Ανακτήθηκε στις 2 Δεκεμβρίου 2019. The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation
↑ Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer | Argonne National Laboratory. Δελτίο τύπου.
↑ See scipy.sparse.dok_matrix
↑ See scipy.sparse.lil_matrix
↑ See scipy.sparse.coo_matrix
↑ Buluç, Aydın; Fineman, Jeremy T.; Frigo, Matteo; Gilbert, John R.; Leiserson, Charles E. (2009). «Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks». ACM Symp. on Parallelism in Algorithms and Architectures. https://people.eecs.berkeley.edu/~aydin/csb2009.pdf.
↑ Saad, Yousef (2003). Iterative methods for sparse linear systems. SIAM.
↑ Bank, Randolph E.; Douglas, Craig C. (1993), «Sparse Matrix Multiplication Package (SMMP)», Advances in Computational Mathematics 1: 127–137, doi:10.1007/BF02070824, http://www.mgnet.org/~douglas/Preprints/pub0034.pdf, ανακτήθηκε στις 2024-01-25
↑ Eisenstat, S. C.· Gursky, M. C.· Schultz, M. H.· Sherman, A. H. (Απριλίου 1977). «Yale Sparse Matrix Package» (PDF) (στα English). Αρχειοθετήθηκε (PDF) από το πρωτότυπο στις 6 Απριλίου 2019. Ανακτήθηκε στις 6 Απριλίου 2019. CS1 maint: Μη αναγνωρίσιμη γλώσσα (link)
↑ Saad, Yousef (2003). Iterative methods for sparse linear systems. SIAM.

[Yan_Wu_Liu_Gao_2017_p.-1] 1,0 ^1,1 Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). «2017 IEEE 17th International Conference on Communication Technology (ICCT)». IEEE, pp. 1880–1883. doi:10.1109/icct.2017.8359956. ISBN 978-1-5090-3944-9. «The computation kernel of DNN is large sparse-dense matrix multiplication. In the field of numerical analysis, a sparse matrix is a matrix populated primarily with zeros as elements of the table. By contrast, if the number of non-zero elements in a matrix is relatively large, then it is commonly considered a dense matrix. The fraction of zero elements (non-zero elements) in a matrix is called the sparsity (density). Operations using standard dense-matrix structures and algorithms are relatively slow and consume large amounts of memory when applied to large sparse matrices.»

[2] «Cerebras Systems Unveils the Industry's First Trillion Transistor Chip». www.businesswire.com (στα Αγγλικά). 19 Αυγούστου 2019. Ανακτήθηκε στις 2 Δεκεμβρίου 2019. The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation

[3] Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer | Argonne National Laboratory. Δελτίο τύπου.

[4] See scipy.sparse.dok_matrix

[5] See scipy.sparse.lil_matrix

[6] See scipy.sparse.coo_matrix

[7] Buluç, Aydın; Fineman, Jeremy T.; Frigo, Matteo; Gilbert, John R.; Leiserson, Charles E. (2009). «Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks». ACM Symp. on Parallelism in Algorithms and Architectures. https://people.eecs.berkeley.edu/~aydin/csb2009.pdf.

[8] Saad, Yousef (2003). Iterative methods for sparse linear systems. SIAM.

[9] Bank, Randolph E.; Douglas, Craig C. (1993), «Sparse Matrix Multiplication Package (SMMP)», Advances in Computational Mathematics 1: 127–137, doi:10.1007/BF02070824, http://www.mgnet.org/~douglas/Preprints/pub0034.pdf, ανακτήθηκε στις 2024-01-25

[10] Eisenstat, S. C.· Gursky, M. C.· Schultz, M. H.· Sherman, A. H. (Απριλίου 1977). «Yale Sparse Matrix Package» (PDF) (στα English). Αρχειοθετήθηκε (PDF) από το πρωτότυπο στις 6 Απριλίου 2019. Ανακτήθηκε στις 6 Απριλίου 2019. CS1 maint: Μη αναγνωρίσιμη γλώσσα (link)

[11] Saad, Yousef (2003). Iterative methods for sparse linear systems. SIAM.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]