Προβολή πηγαίου κώδικα για τη σελίδα Αραιοί πίνακες

{| class=wikitable align=right width=240px style="margin: 3px 0 5px 14px;"
| {{center|'''Παράδειγμα αραιού πίνακα'''}}
{{center|<math>\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)</math>}}
|-
| {{center|{{midsize|Ο παραπάνω αραιός πίνακας περιέχει μόνο 9 μη μηδενικά στοιχεία, με 26 μηδενικά στοιχεία. Η αραιότητά του είναι 74% και η πυκνότητά του είναι 26%.}}}}
|}
[[Image:Finite element sparse matrix.png|right|thumb|Ένας αραιός πίνακας που λαμβάνεται κατά την επίλυση ενός προβλήματος πεπερασμένων στοιχείων σε δύο διαστάσεις. Τα μη μηδενικά στοιχεία εμφανίζονται με μαύρο χρώμα.]]

Στην [[αριθμητική ανάλυση]] και τους επιστημονικούς υπολογισμούς, ένας '''αραιός πίνακας''' είναι ένας [[Πίνακας (μαθηματικά)|πίνακας]] στον οποίο τα περισσότερα στοιχεία είναι μηδενικά<ref name="Yan Wu Liu Gao 2017 p. ">{{cite conference | last1=Yan | first1=Di | last2=Wu | first2=Tao | last3=Liu | first3=Ying | last4=Gao | first4=Yang | title=2017 IEEE 17th International Conference on Communication Technology (ICCT) | chapter=An efficient sparse-dense matrix multiplication on a multicore system | publisher=IEEE | year=2017 | pages=1880–1883 | isbn=978-1-5090-3944-9 | doi=10.1109/icct.2017.8359956 | quote=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. }}</ref>. Δεν υπάρχει αυστηρός ορισμός του ποσοστού των μηδενικών στοιχείων για να θεωρείται ένας πίνακας αραιός, αλλά ένα κοινό κριτήριο είναι ότι ο αριθμός των μη μηδενικών στοιχείων είναι περίπου ίσος με τον αριθμό των γραμμών ή των στηλών. Αντιθέτως, εάν τα περισσότερα στοιχεία είναι μη μηδενικά, ο πίνακας θεωρείται πυκνός<ref name="Yan Wu Liu Gao 2017 p. "/>. Ο αριθμός των μηδενικών στοιχείων διαιρεμένος με τον συνολικό αριθμό των στοιχείων (παραδείγματος χάριν, ''m'' × ''n'' για έναν πίνακα ''m'' × ''n'') ονομάζεται μερικές φορές '''αραιότητα''' του πίνακα.

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

Κατά την αποθήκευση και τον χειρισμό αραιών πινάκων σε έναν [[Ηλεκτρονικός υπολογιστής|υπολογιστή]], είναι χρήσιμο και συχνά απαραίτητο να χρησιμοποιούνται εξειδικευμένοι αλγόριθμοι και δομές δεδομένων που εκμεταλλεύονται την αραιή δομή του πίνακα. Για τους αραιούς πίνακες κατασκευάστηκαν εξειδικευμένοι υπολογιστές<ref>{{Cite web|url=https://www.businesswire.com/news/home/20190819005148/en/Cerebras-Systems-Unveils-Industry%E2%80%99s-Trillion-Transistor-Chip|title=Cerebras Systems Unveils the Industry's First Trillion Transistor Chip| quote=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|date=2019-08-19 |website=www.businesswire.com|language=en|access-date=2019-12-02}}</ref>, καθώς είναι συνηθισμένοι στον τομέα της μηχανικής μάθησης<ref>{{Cite press release|url=https://www.anl.gov/article/argonne-national-laboratory-deploys-cerebras-cs1-the-worlds-fastest-artificial-intelligence-computer|title=Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer {{!}} Argonne National Laboratory|quote=The WSE is the largest chip ever made at 46,225 square millimeters in area, it is 56.7 times larger than the largest graphics processing unit. It contains 78 times more AI optimized compute cores, 3,000 times more high speed, on-chip memory, 10,000 times more memory bandwidth, and 33,000 times more communication bandwidth.| website=www.anl.gov|language=en|access-date=2019-12-02}}</ref>. Οι λειτουργίες που χρησιμοποιούν τις τυπικές δομές και αλγορίθμους πυκνών πινάκων είναι αργές και αναποτελεσματικές όταν εφαρμόζονται σε μεγάλους αραιούς πίνακες, καθώς η επεξεργασία και η μνήμη σπαταλώνται στα μηδενικά. Τα αραιά δεδομένα είναι εκ φύσεως ευκολότερο να συμπιεστούν και συνεπώς απαιτούν πολύ λιγότερη αποθήκευση. Ορισμένοι πολύ μεγάλοι αραιοί πίνακες είναι ανέφικτο να χειριστούν με τη χρήση τυπικών αλγορίθμων πυκνών πινάκων.

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

===Προσαρμοσμένες===
Ένας σημαντικός ειδικός τύπος αραιών πινάκων είναι ο πίνακας ζώνης, ο οποίος ορίζεται ως εξής. Το κατώτερο [[εύρος ζώνης]] ενός πίνακα {{math|'''A'''}} είναι ο μικρότερος αριθμός {{math|''p''}} τέτοιος ώστε η είσοδος {{math|''a''<sub>''i'',''j''</sub>}} να εξαφανίζεται κάθε φορά που {{math|''i'' > ''j'' + ''p''}}. Ομοίως, το ανώτερο εύρος ζώνης είναι ο μικρότερος αριθμός p τέτοιος ώστε {{math|1=''a''<sub>''i'',''j''</sub> = 0}} κάθε φορά που {{math|''i'' < ''j'' − ''p''}} {{harv|Golub|Van Loan|1996|loc=§1.2.1}}. Για παράδειγμα, ένας τριδιαγώνιος πίνακας έχει κατώτερο εύρος ζώνης {{math|1}}. και ανώτερο εύρος ζώνης {{math|1}}. Ως άλλο παράδειγμα, ο ακόλουθος αραιός πίνακας έχει κατώτερο και ανώτερο εύρος ζώνης και τα δύο ίσα με 3. Σημειώστε ότι τα μηδενικά αναπαρίστανται με τελείες για λόγους σαφήνειας.

<math>\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}</math>

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

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

===Διαγώνια===
Μια πολύ αποδοτική δομή για μια ακραία περίπτωση πινάκων ζωνών, τον διαγώνιο πίνακα, είναι η αποθήκευση μόνο των καταχωρήσεων στην κύρια διαγώνιο ως μονοδιάστατος πίνακας, έτσι ώστε ένας διαγώνιος πίνακας {{math|''n'' × ''n''}} να απαιτεί μόνο {{math|''n''}} καταχωρήσεις.

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

===Διαγώνιος μπλοκ=== 
Ένας διαγώνιος κατά μπλοκ πίνακας αποτελείται από υποπίνακες κατά μήκος των διαγώνιων μπλοκ του. Ένας block-διαγώνιος πίνακας A έχει τη μορφή
<math>\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},</math>

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

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

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

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

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

Οι επαναληπτικές μέθοδοι, όπως η μέθοδος της συζυγούς κλίσης και η GMRES, χρησιμοποιούν γρήγορους υπολογισμούς των παραγώγων πίνακα-διανύσματος <math>A x_i</math>, όπου ο πίνακας <math>A</math> είναι αραιός. Η χρήση προαπαιτούμενων μπορεί να επιταχύνει σημαντικά τη σύγκλιση αυτών των επαναληπτικών μεθόδων.

===Αποθήκευση===
Ένας πίνακας αποθηκεύεται γενικά με τη μορφή δισδιάστατου πίνακα. Κάθε καταχώρηση στον πίνακα αντιπροσωπεύει ένα στοιχείο {{math|''a''<sub>''i'',''j''</sub>}} του πίνακα και είναι προσβάσιμη από τους δύο δείκτες {{math|''i''}} και {{math|''j''}}. Κατά σύμβαση, {{math|''i''}}  είναι ο δείκτης γραμμής, αριθμημένος από πάνω προς τα κάτω, και {{math|''j''}} είναι ο δείκτης στήλης, αριθμημένος από αριστερά προς τα δεξιά. Για έναν πίνακα {{math|''m'' × ''n''}} το μέγεθος της μνήμης που απαιτείται για την αποθήκευση του πίνακα σε αυτή τη μορφή είναι ανάλογο του {{math|''m'' × ''n''}} (ανεξάρτητα από το γεγονός ότι πρέπει να αποθηκευτούν και οι διαστάσεις του πίνακα).

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

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

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

Το DOK αποτελείται από ένα λεξικό το οποίο συσχετίζει ζεύγη (γραμμή, στήλη) με την τιμή των στοιχείων. Τα στοιχεία που λείπουν από το λεξικό θεωρούνται μηδενικά. Αυτή η μορφή επιτρέπει την προοδευτική κατασκευή ενός αραιού πίνακα με τυχαία σειρά, αλλά δεν επιτρέπει την επανάληψη των μη μηδενικών τιμών με λεξικογραφική σειρά. Ένας πίνακας γενικά κατασκευάζεται σε αυτή τη μορφή και στη συνέχεια μετατρέπεται σε άλλη μορφή που είναι πιο αποδοτική για την επεξεργασία <ref>See [http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.dok_matrix.html <code>scipy.sparse.dok_matrix</code>]</ref>.

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

Η LIL αποθηκεύει μία λίστα ανά σειρά, με κάθε καταχώρηση να περιέχει τον δείκτη της στήλης και την τιμή. Συνήθως, οι καταχωρήσεις αυτές ταξινομούνται με βάση τον δείκτη στήλης για ταχύτερη αναζήτηση. Αυτή είναι μια άλλη μορφή κατάλληλη για την αυξητική κατασκευή πινάκων<ref>See [http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.lil_matrix.html <code>scipy.sparse.lil_matrix</code>]</ref>.

===Κατάλογος συντεταγμένων (COO)===
Η λίστα συντεταγμένων αποθηκεύει έναν κατάλογο πλειάδων (γραμμή, στήλη, τιμή). Κατά προτίμηση, οι καταχωρήσεις ταξινομούνται πρώτα με βάση τον δείκτη γραμμής και μετά με βάση τον δείκτη στήλης, για να βελτιωθούν οι χρόνοι τυχαίας πρόσβασης. Αυτή είναι μια άλλη μορφή κατάλληλη για τη σταδιακή κατασκευή πινάκων.<ref>See [http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.coo_matrix.html <code>scipy.sparse.coo_matrix</code>]</ref>

===Συμπιεσμένη αραιή σειρά (μορφή CSR, CRS ή Yale)===
Η συμπιεσμένη αραιή γραμμή (CSR) ή η συμπιεσμένη αποθήκευση γραμμής (CRS) ή η μορφή Yale αναπαριστά έναν πίνακα {{math|'''M'''}} από τρεις (μονοδιάστατους) πίνακες, οι οποίοι περιέχουν αντίστοιχα μη μηδενικές τιμές, τις εκτάσεις των γραμμών και τους δείκτες των στηλών. Είναι παρόμοιο με το COO, αλλά συμπιέζει τους δείκτες γραμμών, εξ ου και το όνομα. Αυτή η μορφή επιτρέπει τη γρήγορη πρόσβαση στις γραμμές και τους πολλαπλασιασμούς πινάκων-διανυσμάτων ({{math|'''M'''''x''}}). Η μορφή CSR χρησιμοποιείται τουλάχιστον από τα μέσα της δεκαετίας του 1960, με την πρώτη πλήρη περιγραφή να εμφανίζεται το 1967<ref>{{cite conference |first1=Aydın |last1=Buluç |first2=Jeremy T. |last2=Fineman |first3=Matteo |last3=Frigo |first4=John R. |last4=Gilbert |first5=Charles E. |last5=Leiserson |authorlink5=:en:Charles E. Leiserson |title=Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks |year=2009 |conference=ACM Symp. on Parallelism in Algorithms and Architectures |url=https://people.eecs.berkeley.edu/~aydin/csb2009.pdf |citeseerx=10.1.1.211.5256}}</ref>.

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

* Οι πίνακες {{math|V}} και {{math|COL_INDEX}} έχουν μήκος {{math|NNZ}} και περιέχουν τις μη μηδενικές τιμές και τους δείκτες στήλης αυτών των τιμών αντίστοιχα.
* Η {{math|COL_INDEX}} περιέχει τη στήλη στην οποία βρίσκεται η αντίστοιχη καταχώρηση {{math|V}}.
* Ο πίνακας {{math|ROW_INDEX}} έχει μήκος {{math|''m'' + ''1''}} και κωδικοποιεί τον δείκτη στο {{math|V}} και {{math|COL_INDEX}} από όπου ξεκινάει η συγκεκριμένη γραμμή. Αυτό είναι ισοδύναμο με το {{math|ROW_INDEX[j]}} που κωδικοποιεί το συνολικό αριθμό των μη μηδενικών πάνω από τη γραμμή {{math|j}}.  Το τελευταίο στοιχείο είναι το {{math|NNZ}} , δηλαδή ο πλασματικός δείκτης στο {{Math|V}} αμέσως μετά τον τελευταίο έγκυρο δείκτη {{math|NNZ - 1}}.<ref name="SIAM">{{cite book |last1=Saad |first1=Yousef |title=Iterative methods for sparse linear systems |url=https://archive.org/details/iterativemethods0000saad |date=2003 |publisher=SIAM}}</ref>

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

<math>\begin{pmatrix}
5 & 0 & 0 & 0 \\
0 & 8 & 0 & 0 \\
0 & 0 & 3 & 0 \\
0 & 6 & 0 & 0 \\
\end{pmatrix}</math>

είναι ο {{math|4 × 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 (τη δεύτερη γραμμή) αυτού του πίνακα, ορίζουμε <code>row_start=1</code> και <code>row_end=2</code>. Στη συνέχεια κάνουμε τις φέτες <code>V[1:2] = [8]</code> και <code>COL_INDEX[1:2] = [1]</code>. Γνωρίζουμε τώρα ότι στη γραμμή 1 έχουμε ένα στοιχείο στη στήλη 1 με τιμή 8.

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

Ένα άλλο παράδειγμα, ο πίνακας
<math>\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}</math>

είναι ένας {{math|4 × 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 στο {{math|V}}, 8 στο {{math|COL_INDEX}} και 5 στο {{math|ROW_INDEX}}.

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

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

Οι (παλιές και νέες) μορφές αραιών πινάκων Yale είναι περιπτώσεις του σχήματος CSR. Η παλιά μορφή Yale λειτουργεί ακριβώς όπως περιγράφεται παραπάνω, με τρεις πίνακες- η νέα μορφή συνδυάζει τους ROW_INDEX και COL_INDEX σε έναν ενιαίο πίνακα και χειρίζεται τη διαγώνιο του πίνακα ξεχωριστά<ref>{{citation |title=Sparse Matrix Multiplication Package (SMMP) |first1=Randolph E. |last1=Bank |first2=Craig C. |last2=Douglas |journal=Advances in Computational Mathematics |volume=1 |year=1993 |pages=127–137 |doi=10.1007/BF02070824 |s2cid=6412241 |url=http://www.mgnet.org/~douglas/Preprints/pub0034.pdf |accessdate=2024-01-25 |archivedate=2014-12-21 |archiveurl=https://web.archive.org/web/20141221225953/http://www.mgnet.org/~douglas/Preprints/pub0034.pdf |deadurl= }}</ref>.

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

Είναι πιθανό να είναι γνωστή ως η μορφή Yale επειδή προτάθηκε στην έκθεση Yale Sparse Matrix Package του 1977 από το Τμήμα Επιστήμης Υπολογιστών του [[Πανεπιστήμιο Γέιλ|Πανεπιστημιο του Γέιλ]]<ref>{{cite web |url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a047724.pdf |archive-url=https://web.archive.org/web/20190406045412/https://apps.dtic.mil/dtic/tr/fulltext/u2/a047724.pdf |url-status=live |archive-date=April 6, 2019 |title=Yale Sparse Matrix Package |last1=Eisenstat  |first1=S. C. |last2=Gursky |first2=M. C. |last3=Schultz |first3=M. H. |last4=Sherman |first4=A. H. |date=April 1977 |language=English |access-date=6 April 2019 }}</ref>.

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

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

==Λογισμικό==

Πολλές βιβλιοθήκες λογισμικού υποστηρίζουν αραιούς πίνακες και παρέχουν επιλυτές για εξισώσεις αραιών πινάκων. Οι ακόλουθες είναι ανοικτού κώδικα: Οι ακόλουθες εφαρμογές είναι open-source:
* [http://faculty.cse.tamu.edu/davis/suitesparse.html SuiteSparse], σειρά αλγορίθμων αραιών πινάκων, με στόχο την άμεση επίλυση αραιών γραμμικών συστημάτων.
* [https://cran.r-project.org/web/packages/spam/index.html SPArse Matrix (spam)] Πακέτο R και [[Python]] για αραιούς πίνακες.
* [https://reference.wolfram.com/language/guide/SparseArrays.html Wolfram Language] Εργαλεία για το χειρισμό αραιών πινάκων
* [https://basic-matrix-library.readthedocs.io/en/latest/ Basic Matrix Library (bml)] υποστηρίζει διάφορες μορφές αραιών πινάκων και αλγορίθμους γραμμικής άλγεβρας με δεσμεύσεις για C, C++ και Fortran.
* [https://www-users.cse.umn.edu/~saad/software/SPARSKIT/ SPARSKIT] Μια βασική εργαλειοθήκη για υπολογισμούς αραιών πινάκων από το Πανεπιστήμιο της Μινεσότα.

==Εξωτερικοί Σύνδεσμοι  ==
* {{cite journal | title = A comparison of several bandwidth and profile reduction algorithms | journal = ACM Transactions on Mathematical Software | year = 1976 | volume = 2 | issue = 4 | pages = 322–330 | url = http://portal.acm.org/citation.cfm?id=355707 | doi = 10.1145/355705.355707 | last1 = Gibbs | first1 = Norman E. | last2 = Poole | first2 = William G. | last3 = Stockmeyer | first3 = Paul K.  | s2cid = 14494429 }}
* {{cite journal | title = Sparse matrices in MATLAB: Design and Implementation | journal = SIAM Journal on Matrix Analysis and Applications | year = 1992 | volume = 13 | issue = 1 | pages = 333–356 | url = http://citeseer.ist.psu.edu/gilbert91sparse.html | doi = 10.1137/0613024 | last1 = Gilbert | first1 = John R. | last2 = Moler | first2 = Cleve | last3 = Schreiber | first3 = Robert | citeseerx = 10.1.1.470.1054 }}
* [http://faculty.cse.tamu.edu/davis/research.html  Sparse Matrix Algorithms Research] at the Texas A&M University.
* [https://sparse.tamu.edu/ SuiteSparse Matrix Collection]
* [http://www.small-project.eu 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 | first1=Gene H. | last1=Golub | author1-link=:en:Gene H. Golub | first2=Charles F. | last2=Van Loan | author2-link=:en:Charles F. Van Loan | year=1996 | title=Matrix Computations | edition=3rd | publisher=Johns Hopkins | place=Baltimore | isbn=978-0-8018-5414-9 }}
* {{Cite book | last1=Stoer | first1=Josef | last2=Bulirsch | first2=Roland | title=Introduction to Numerical Analysis | url=https://archive.org/details/introductiontonu0000stoe_t7w1 | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=3rd | isbn=978-0-387-95452-3 | year=2002}}
* {{Cite book | last=Tewarson| first=Reginald P.|title=Sparse Matrices (Part of the Mathematics in Science & Engineering series)|publisher= Academic Press Inc.|date=May 1973}} (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|title= Sparse Matrix Multiplication Package|first1= Randolph E.|last1= Bank|first2= Craig C.|last2= Douglas|url= http://www.mgnet.org/~douglas/Preprints/pub0034.pdf|accessdate= 2024-01-25|archive-date= 2014-12-21|archive-url= https://web.archive.org/web/20141221225953/http://www.mgnet.org/~douglas/Preprints/pub0034.pdf|url-status= }}
* {{Cite book |last=Pissanetzky|first= Sergio|year= 1984|title=Sparse Matrix Technology|url=https://archive.org/details/sparsematrixtech0000piss|url-access=registration|publisher= Academic Press|isbn= 9780125575805}}
*{{cite journal|doi=10.1007/BF02521587|title=Reducing the profile of sparse symmetric matrices|year=1976|last1=Snay|first1=Richard A.|journal=[[:en:Bulletin Géodésique|Bulletin Géodésique]]|volume=50|issue=4|pages=341–352|bibcode=1976BGeod..50..341S|hdl=2027/uc1.31210024848523|s2cid=123079384|hdl-access=free}} Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.<ref name="SIAM"/>
* [https://link.springer.com/book/10.1007/978-3-031-25820-6 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)]

==Παραπομπές==
<references />

{{Authority control}} 
{{Γραμμική Άλγεβρα}}
{{Portal bar|Μαθηματικά}}

[[Κατηγορία:Γραμμική άλγεβρα]]
[[Κατηγορία:Αριθμητική γραμμική άλγεβρα]]
[[Κατηγορία:Πίνακες (μαθηματικά)]]