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

Πρότυπο:Center

Πρότυπο:Center

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

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

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

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

Ειδικές περιπτώσεις

Προσαρμοσμένες

Ένας σημαντικός ειδικός τύπος αραιών πινάκων είναι ο πίνακας ζώνης, ο οποίος ορίζεται ως εξής. Το κατώτερο εύρος ζώνης ενός πίνακα Πρότυπο:Math είναι ο μικρότερος αριθμός Πρότυπο:Math τέτοιος ώστε η είσοδος Πρότυπο:Math να εξαφανίζεται κάθε φορά που Πρότυπο:Math. Ομοίως, το ανώτερο εύρος ζώνης είναι ο μικρότερος αριθμός p τέτοιος ώστε Πρότυπο:Math κάθε φορά που Πρότυπο:Math Πρότυπο:Harv. Για παράδειγμα, ένας τριδιαγώνιος πίνακας έχει κατώτερο εύρος ζώνης Πρότυπο:Math. και ανώτερο εύρος ζώνης Πρότυπο:Math. Ως άλλο παράδειγμα, ο ακόλουθος αραιός πίνακας έχει κατώτερο και ανώτερο εύρος ζώνης και τα δύο ίσα με 3. Σημειώστε ότι τα μηδενικά αναπαρίστανται με τελείες για λόγους σαφήνειας.

$\left[\begin{array}{cccccccc}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{array}\right]$

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

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

Διαγώνια

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

Συμμετρική

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

Διαγώνιος μπλοκ

Ένας διαγώνιος κατά μπλοκ πίνακας αποτελείται από υποπίνακες κατά μήκος των διαγώνιων μπλοκ του. Ένας block-διαγώνιος πίνακας A έχει τη μορφή $𝐀=\left[\begin{array}{cccc}{𝐀}_1& 0& \cdots & 0\\ 0& {𝐀}_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {𝐀}_n\end{array}\right],$

όπου ${𝐀}_k$ είναι ένας τετραγωνικός πίνακας για όλα τα $𝑘=1,...,𝑛$

Χρήση

Μείωση της συμπλήρωσης

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

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

Επίλυση εξισώσεων αραιών πινάκων

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

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

Αποθήκευση

Ένας πίνακας αποθηκεύεται γενικά με τη μορφή δισδιάστατου πίνακα. Κάθε καταχώρηση στον πίνακα αντιπροσωπεύει ένα στοιχείο Πρότυπο:Math του πίνακα και είναι προσβάσιμη από τους δύο δείκτες Πρότυπο:Math και Πρότυπο:Math. Κατά σύμβαση, Πρότυπο:Math είναι ο δείκτης γραμμής, αριθμημένος από πάνω προς τα κάτω, και Πρότυπο:Math είναι ο δείκτης στήλης, αριθμημένος από αριστερά προς τα δεξιά. Για έναν πίνακα Πρότυπο:Math το μέγεθος της μνήμης που απαιτείται για την αποθήκευση του πίνακα σε αυτή τη μορφή είναι ανάλογο του Πρότυπο:Math (ανεξάρτητα από το γεγονός ότι πρέπει να αποθηκευτούν και οι διαστάσεις του πίνακα).

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

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

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

Λεξικό κλειδιών (DOK)

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

Λίστα καταλόγων (LIL)

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

Κατάλογος συντεταγμένων (COO)

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

Συμπιεσμένη αραιή σειρά (μορφή CSR, CRS ή Yale)

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

Η μορφή CSR αποθηκεύει έναν αραιό Πρότυπο:Math πίνακα $𝐌$ σε μορφή γραμμής χρησιμοποιώντας τρεις (μονοδιάστατους) πίνακες Πρότυπο:Math. Έστω Πρότυπο:Math ο αριθμός των μη μηδενικών καταχωρήσεων στο Πρότυπο:Math. (Σημειώστε ότι εδώ θα χρησιμοποιηθούν δείκτες με βάση το μηδέν).

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

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

$\left(\begin{array}{cccc}5& 0& 0& 0\\ 0& 8& 0& 0\\ 0& 0& 3& 0\\ 0& 6& 0& 0\end{array}\right)$

είναι ο Πρότυπο:Math πίνακας με 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 εξοικονομεί μνήμη μόνο όταν Πρότυπο:Math.

Ένα άλλο παράδειγμα, ο πίνακας $\left(\begin{array}{cccccc}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{array}\right)$

είναι ένας Πρότυπο:Math πίνακας (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 στο Πρότυπο:Math, 8 στο Πρότυπο:Math και 5 στο Πρότυπο:Math.

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

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

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

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

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

Συμπιεσμένη αραιή στήλη (CSC ή CCS)

Το CSC είναι παρόμοιο με το CSR με τη διαφορά ότι οι τιμές διαβάζονται πρώτα ανά στήλη, αποθηκεύεται ένας δείκτης γραμμής για κάθε τιμή και αποθηκεύονται δείκτες στήλης. Παραδείγματος χάριν, το CSC είναι Πρότυπο:Math, όπου Πρότυπο:Math είναι ένας πίνακας με τις (από πάνω προς τα κάτω, και στη συνέχεια από αριστερά προς τα δεξιά) μη μηδενικές τιμές του πίνακα, Πρότυπο:Math είναι οι δείκτες γραμμής που αντιστοιχούν στις τιμές και, Πρότυπο:Math είναι ο κατάλογος των δεικτών 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 Μια βασική εργαλειοθήκη για υπολογισμούς αραιών πινάκων από το Πανεπιστήμιο της Μινεσότα.

Εξωτερικοί Σύνδεσμοι

• Πρότυπο:Cite journal
• Πρότυπο:Cite journal
• 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).

Πηγές

• Πρότυπο:Cite book
• Πρότυπο:Cite book
• Πρότυπο:Cite book (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).
• Πρότυπο:Cite web
• Πρότυπο:Cite book
• Πρότυπο:Cite journal Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.
• 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)