„Ritka mátrix” változatai közötti eltérés

nincs szerkesztési összefoglaló
a (+A)
Nagyméretű ritka mátrixokat leggyakrabban [[parciális differenciálegyenlet]]ek megoldásai eredményeznek.
 
Ritka mátrixok [[számítógép|számítógépes]] kezelése vagy tárolása esetén sokszor előnyös, néhol egyenesen szükséges, olyan [[algoritmus|algoritmusok]] és [[adatszerkezet|adatszerkezetek]] alkalmazása, melyeket kihasználják a mátrixok ritka szerkezetét, vagyis kifejezetten ilyen esetekre vannak kidolgozva. A hagyományos mátrixokkal dolgozó műveletek használata ez esetben lassú és fölöslegesen nagy [[memória (számítástechnika)|memóriaigényű]]. Az adatok ritkaságukból adódóan könnyen [[adattömmörítésadattömörítés|tömöríthetőek]] s ezáltal lényegesen kisebb a memóriaigényük. Valóban, nagyon nagy ritka mátrixok hagyományos módszerek, algoritmusok által való kezelése megvalósíthatatlan.
 
=={{anchor|storage}} Ritka mátrixok tárolása==
* melyek hatékonyan vethetők alá különböző, mátrixokkal végzett műveleteknek
 
Előbbibe tartozik például a DOK (Dictionary of keys - kulcsszótár), a LIL (List of lists - listák listája), a COO (Coordinate list – koordináták listája), ezeket általában a mátrix felépítésére használják. Ha a mátrix már fel van építve, átalakításra kerül a CSR (Compressed Sparse Row – sortömörítés) vagy a CSC (Compressed Sparse Column – oszloptömörítés) formátumok valamelyikébe, melyek optimálisabbak mátrixműveletek elvégzésekor.
 
===Kulcsszótár (DOK – dictionary of keys)===
 
===Yale-formátum===
A Yale ritkamátrix-formátum sorként tárolja az eredetileg ''m''x''n'' méretű ''M'' mátrixot, három egydimenziós tömböt használva. Legyen <code>NN</code> a nemnulla elemek száma ''M''-ben. Legyen az <code>A</code> tömb <code>NN</code> hosszúságú s tárolja ''M'' összes nemnulla elemét balról jobbra és fentről lefele haladva a mátrixban. A második tömb legyen <code>IA</code>, melynek hossza ''m+1'' s melynek ''i.'' eleme tartalmazza az ''M'' mátrix ''i.'' sorából az első nemnulla elem <code>A</code> tömbbeli indexét. A mátrix ''i.'' sora <code>A[IA[i]]</code>-tól <code>A[IA[i+1]-1]</code>-ig tart, azaz az adott sor első nemnulla elemétől a következő sort kezdő elemet megelőző nemnulla elemig. A harmadik tömb, a <code>JA</code>, az <code>A</code> elemeinek ''M'' mátrixbeli oszlopindexét tárolja, így hossza ugyancsak <code>NN</code>. Például a
 
:::<code> [ 1 2 0 0 ]</code>
:::<code> JA = [ 0 1 1 2 1 2 ]</code> &nbsp; (az A elemeinek oszlopindexei)
 
Azaz a <code>JA</code> tömbnek megfelelően az <code>A</code> tömb ’1’-es elemének oszlopindexe 0, a ’2’ és ’3’ oszlopindexe 1, a ’9’ oszlopindexe 2, a második ’1’-es oszlopindexe 1, a ’4’-es oszlopindexe pedig 2. A matematikában az oszlopok számozása 1-től 4-ig terjed, a számítástechnikában azonban 0-tól 3-ig.
 
Feltűnik, hogy a Yale felírási módszer során 16 bejegyzést tárolunk az eredeti mátrix 12 bejegyzéséhez képest, ugyanis a Yale-formátum használata csak akkor előnyös, ha <math>NN < (m(n-1)-1)/2</math>. Egy újabb példában az ''M'' mátrix
[ 0 0 0 0 0 80 ]
 
4 x 6-os, azaz 24 bejegyzést tartalmaz, ebből 8 nemnulla elem, így
A = [ 10 20 30 40 50 60 70 80 ]
IA = [ 0 2 4 7 8 ]
JA = [ 0 1 1 3 2 3 4 5 ]
 
Ez esetben már csak 21 bejegyzés volt szükséges.
:* az <code>IA</code> sorokra bontja az <code>A</code> tömböt: <code>(10, 20) (30, 40) (50, 60, 70) (80)</code>
:* a <code>JA</code> oszlopokba rendezi az értékeket: <code>(10, 20, …) (0, 30, 0, 40, …) (0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80)</code>
\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{smallmatrix}
\right)
 
==Irodalom==
* {{Cite book | first1=Gene H. | last1=Golub | author1-link=Gene H. Golub | first2=Charles F. | last2=Van Loan | author2-link=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 | 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}}
* {{Cite book |last=Pissanetzky|first= Sergio|year= 1984|title=Sparse Matrix Technology|publisher= Academic Press}}
 
==További információk==
* {{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. }}
* {{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 }}
* [http://www.cise.ufl.edu/research/sparse Sparse Matrix Algorithms Research] at the University of Florida, containing the UF sparse matrix collection.
* [http://www.small-project.eu SMALL project] A EU-funded project on sparse models, algorithms and dictionary learning for large-scale data.
==Külső hivatkozások==
*[http://www.solvingequations.net Equations Solver Online]
*[http://purl.umn.edu/107467 Oral history interview with Harry M. Markowitz], [[Charles Babbage Institute]], University of Minnesota. [[Harry Markowitz|Markowitz]] discusses his development of [[portfolio theory]] (for which he received a Nobel Prize in Economics), '''sparse matrix methods''', and his work at the [[RAND Corporation]] and elsewhere on simulation software development (including computer language [[SIMSCRIPT]]), modeling, and operations research.
 
{{DEFAULTSORT:Sparse Matrix}}