Wikipédia

„Szerkesztő:Vigyori93/próbalap” változatai közötti eltérés

Laptörténet interaktív böngészése
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
Vigyori93 (vitalap | szerkesztései)
16 szerkesztés
Nincs szerkesztési összefoglaló
Vigyori93 (vitalap | szerkesztései)
16 szerkesztés
Nincs szerkesztési összefoglaló
1. sor:
{| class=wikitable align=right width=240px style="margin:3px 15px 5px 0;"
{{tataroz}}
| <center>'''Példa ritka mátrixra'''</center>
<small>
<code>
&nbsp; [ 11 22 &nbsp;0 &nbsp;0 &nbsp;0 &nbsp;0 &nbsp;0 ]<br>
&nbsp; [ &nbsp;0 33 44 &nbsp;0 &nbsp;0 &nbsp;0 &nbsp;0 ]<br>
&nbsp; [ &nbsp;0 &nbsp;0 55 66 77 &nbsp;0 &nbsp;0 ]<br>
&nbsp; [ &nbsp;0 &nbsp;0 &nbsp;0 &nbsp;0 &nbsp;0 88 &nbsp;0 ]<br>
&nbsp; [ &nbsp;0 &nbsp;0 &nbsp;0 &nbsp;0 &nbsp;0 &nbsp;0 99 ]<br>
</code>
</small>
|-
| <center>A fenti ritka mátrix csupán<br>9 nemnulla elemet tartalmaz a 35ből, <br>&nbsp;a maradék 26 elem értéke nulla.</center>
|}
[[Image:Finite element sparse matrix.png|right|thumb|Kétdimenziós [[végeselemes módszer|végeselemes feladat]] megoldásaként kapott ritka mátrix. A nemnulla elemeket fekete pontok jelölik.]]
 
'''Ritka mátrix''' a [[numerikus analízis]] alterületében olyan [[mátrix (matematika)]], melyben elemek túlnyomó része 0 (nulla) {{harv|Stoer|Bulirsch|2002|p=619}}. Ezzel ellentétben a túlnyomórészt nemnulla elemet tartalmazó mátrixokat '''sűrű mátrixnak''' nevezzük. A nulla- (vagy éppen nemnulla) elemek aránya a mátrix méretéhez képest, annak '''ritkaságát''' ('''sűrűségét''') adja.
[[Image:Khettaras.jpg|thumb|upright 1.2|Khettara Erfoud ([[Marokkó]]) közelében]]
 
A ritka mátrixok gyakorlatilag lazán csatolt rendszereknek felelnek meg. Tekintsünk egy rugókkal összekapcsolt golyókból álló láncot; ez egy ritka rendszer. Azonban ha az összes golyó össze kötve lenne egy rugón keresztül az összes többivel, a rendszert egy sűrű mátrix jellemezné. A ritkaság fogalmát főleg a [[kombinatorika|kombinatorikában]] és annak alkalmazási területein használják, mint például a hálózatelméletben, ahol kicsi a jelentős adatok vagy összeköttetések sűrűsége.
A '''qanāt''' ([http://hu.wikipedia.org/wiki/Arab_nyelv arabul] قناة, [http://hu.wikipedia.org/wiki/Perzsa_nyelv perzsául] کاریز‎ ''kariz'') a meleg, [http://hu.wikipedia.org/wiki/%C3%89ghajlati_%C3%B6vezetek#Sz.C3.A1raz_kontinent.C3.A1lis_.C3.A9ghajlat száraz] és félszáraz éghajlatokon használt vízrendszer, mely az emberi települések és az [[öntözés]] vízellátását biztosítja. Megbízhatósága miatt elterjedt. Más ismert elnevezései: '''kārīz''' vagy '''kārēz''' ([[Irán]], [[Afganisztán]], [[Pakisztán]] és [[Közép-Ázsia]] területén, a perzsa كاهریز-ból), '''kahan''' (a perzsa کهن-ból), '''kahriz''' vagy '''kəhriz''' ([[Azerbajdzsán]]), '''khettara''' ([[Marokkó]]), '''galeria''' ([[Spanyolország]]), '''falaj''' ([[Egyesült Arab Emírségek]] és [[Omán]]), '''kahn''' ([[Beludzsisztán (Pakisztán)|Beludzsisztán]]), '''foggara''' vagy '''fughara''' ([[Észak-Afrika]]).<ref>Dr. V. Sankaran Nair: [http://www.boloji.com/index.cfm?md=Content&sd=Articles&ArticleID=5238 Etymological conduit to the land of Qanat] (2004)</ref> Emellett Ázsiában és Észak-Afrikában használatosak a '''kakuriz''', '''chin-avulz''' és '''mayun''' elnevezések is.
 
Nagyméretű ritka mátrixokat eredményeznek a parciális differenciálegyenletek megoldásai különböző [[tudomány|tudományos]] vagy [[műszaki tudomány|műszaki]] területeken.
A qanat [[technológia|technológiáját]] feltehetőleg a perzsák fejlesztették ki az i.e. 1. évezred elején, ahonnan aztán lassan terjedt el Nyugat, illetve Kelet irányába.<ref>Andrew Wilson: "Hydraulic Engineering and Water Supply", John Peter Oleson: ''Handbook of Engineering and Tehnology in the Classical World'' c. könyvéből, New York, Oxford University Press, 2008. ISBN 978-0-19-973485-6. 291. old.</ref><ref>[http://www.edwardgoldsmith.org/1031/the-qanats-of-iran/ Edward Goldsmith: The qanats of Iran]</ref><ref>H. E. Wuff: [http://users.bart.nl/~leenders/txt/qanats.html The Qanats of Iran], ''Scientific American'', 1968. április, 94-105. old.</ref><ref>[http://www.waterhistory.org/histories/qanats/qanats.pdf Qanats]</ref><ref>K. E. Eduljee: Zoroastrian Heritage - [http://www.heritageinstitute.com/zoroastrianism/kareez/index.htm Kareez]</ref>
 
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é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.
Egy qanat értékét nagyban befolyásolta minősége, mérete és a [[vízhozam]] folytonossága. Irán és más száraz éghajlatú ázsiai, illetve észak-afrikai ország népességének jelentős része függött a qanatok vizétől, településeik, élőhelyeik olyan területeken alakultak ki, ahol lehetséges volt qanatok kiépítése. Bár a kiépítés igencsak költséges volt, hosszútávú értéke a közösség – így a megépítésbe és karbantartásba befektetők is – számára jelentős volt.<ref name='Kheirabadi'>Masoud Kheirabadi: ''Iranian Cities: Formation and Development'', University of Texas Press, 1991. ISBN 0-292-78517-8</ref>
 
=={{anchor|storage}} Ritka mátrixok tárolása==
Mátrixok tárolására alapvetően kétdimenziós [[tömb (adatszerkezet)|tömbök]] használatosak, melyekben a tömb minden egyes <code>t[i][j]</code> eleme a mátrix egy-egy ''a''<sub>''i'',''j''</sub> elemének felel meg. Egyezményesen ''i'' a sort jelöli fentről lefele haladva, míg ''j'' az oszlopot balról jobbra haladva. Egy ''m'' x ''n'' méretű mátrix tárolása így ''m''•''n'' darab bejegyzésnek megfelelő memóriát igényel.
 
Jelentős mennyiségű memória spórolható meg, ha csak a nemnulla elemeket tároljuk. Ezek száma és eloszlása függvényében többféle adatszerkezet is rendelkezésünkre áll, melyek nagymértékű memória-megtakarítást szolgáltatnak a hagyományos módszerekkel szemben.
 
Formátum szempontjából két fő csoportról beszélhetünk:
* melyek hatékonyan módosíthatók
* 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)===
A DOK egyfajta szótárként tárolja a nemnulla elemeket (pl. [[hash tábla]] vagy bináris fa formájában), minden <code>(sor, oszlop)</code> [[rendezett pár|számpárnak]] megfeleltetve egy értéket. Ez az alak előnyös a mátrix fokozatos felépítésekor, azonban gyenge abban az esetben, ha a nemnulla elemek valamilyen sorrend szerint akarjuk iterálni. Az általános eljárás az, hogy a DOK alapján felépítik a mátrixot, majd egy könnyebben kezelhető formátumba konvertálják.
 
===Listák listája (LIL – List of lists)===
A LIL listánként egy sort tartalmaz s minden bejegyzés tartalmazza az oszlopindexet és az értéket. A gyors keresés érdekében az oszlopindexek szerint rendezve tárolják. Ez ugyancsak előnyös formátum a mátrix fokozatos felépítésére. Lásd [http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.lil_matrix.html scipy.sparse.lil_matrix].
 
===Koordináták listája (COO – Coordinate list)===
A COO egy lista, mely <code>(sor, oszlop, érték)</code> számhármasokat tároló [[rendezett n-es]]ekből áll. Kedvező esetben a bejegyzések sorok, ezeken belül oszlop szerint rendezettek a hozzáférhetőség megkönnyítése céljából. Jelen tárolási módszer ugyancsak előnyös a mátrixok fokozatos felépítésekor. Lásd [http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.coo_matrix.html scipy.sparse.coo_matrix].
 
===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 <math>m+1</math> 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> [ 0 3 9 0 ]</code>
:::<code> [ 0 1 4 0 ]</code>
 
3 x 4-es mátrixnak 6 nemnulla eleme van, így az őt jellemző tömbök:
 
:::<code> A = [ 1 2 3 9 1 4 ]</code> &nbsp; (a nemnulla elemeket tartalmazó tömb)
:::<code> IA = [ 0 2 4 6 ]</code> &nbsp; (az i. sor első nemnulla elemének indexét tároló tömb)
:::<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
[ 10 20 0 0 0 0 ]
[ 0 30 0 40 0 0 ]
[ 0 0 50 60 70 0 ]
[ 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>
 
(Megjegyzés: Ebben a formátumban <code>IA</code> első eleme mindig 0, utolsó eleme mindig <code>NN</code>, így ez a két bejegyzés fölösleges lehet.)
 
===Sortömörítés (CSR – Compressed Sparse Row)===
A [http://netlib.org/linalg/html_templates/node91.html#SECTION00931100000000000000 CSR] hatékonyságában a Yale-formátummal megegyező, azzal a különbséggel, hogy az oszlopindexeket tartalmazó tömb általában a sorindexeket tartalmazó előtt kerül tárolásra. Alakja <code>(érték, oszlop_index, sor_pointer)</code>, ahol az <code>érték</code> a nemnulla elemek tömbje (balról jobbra és fentről lefele járva be a mátrixot), az <code>oszlop_index</code> az értékeknek megfelelő oszlopindexek tömbje, míg a <code>sor_pointer</code> a sorokat kezdő nemnulla elemek indexeinek listája. Elnevezését arról kapta, hogy a COO formátumhoz képest a sorindexek tárolása tömörített. Előnyös aritmetikai műveletek elvégzésekor, mátrix-vektor szorzat kiszámításakor, sorszeleteléskor, azonban a mátrix felépítésére nem szokás használni. Lásd [http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csr_matrix.html scipy.sparse.csr_matrix].
 
===Oszloptömörítés (CSC – Compressed Sparse Column)===
A [http://netlib.org/linalg/html_templates/node92.html#SECTION00931200000000000000 CSC] a CSR-hez hasonló módszer, a különbség abban rejlik, hogy az elemek oszloponként vannak beolvasva, minden elemnek a sorindexe van tárolva s az oszlopokat tároljuk pointerekben. Alakja <code>(érték, sor_index, oszlop_pointer)</code>, ahol az <code>érték</code> a nemnulla elemek tömbje (balról jobbra és fentről lefele járva be a mátrixot), a <code>sor_index</code> az értékeknek megfelelő sorindexek tömbje, míg az <code>oszlop_pointer</code> az oszlopokat kezdő nemnulla elemek indexeinek listája. Elnevezését arról kapta, hogy a COO formátumhoz képest az oszlopindexek tárolása tömörített. Előnyös aritmetikai műveletek elvégzésekor, mátrix-vektor szorzat kiszámításakor, oszlopszeleteléskor, azonban a mátrix felépítésére nem szokás használni. Lásd [http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csc_matrix.html scipy.sparse.csc_matrix].
Hagyományosan ezt a formátumot használja a MATLAB egy ritka mátrix jellemzésére a <code>sparse</code> függvény által.
 
==Különleges szerkezet==
===Sávmátrix===
A sávmátrix a ritka mátrixok egy különleges típusa, melyben az alsó- és felsősáv szélesség viszonylag kis érték. Ezek meghatározása a következő: Az ''A'' mátrix ''alsósáv szélessége'' az a legkisebb ''p'' szám, melyre az ''a''<sub>''i'',''j''</sub> = 0 bármely ''i'' > ''j''+''p'' esetén. Hasonlóképpen az ''A'' mátrix ''felsősáv szélessége'' az a legkisebb ''p'' szám, melyre az ''a''<sub>''i'',''j''</sub> = 0 bármely ''i'' < ''j''-''p'' esetén {{harv|Golub|Van Loan|1996|loc=§1.2.1}}. Például egy [[tridiagonális mátrix]] alsó- és felsősáv szélessége is 1. A következő példában azonban mindkettő értéke 3 (az X-ek a nemnulla elemek, a pontok a nullaelemek):
::<math>
\left(
\begin{smallmatrix}
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{smallmatrix}
\right)
</math>
 
Különleges szerkezetükből adódóan a kezelésükre kidolgozott algoritmusok jóval egyszerűbbek az általános ritka mátrixokkal dolgozó algoritmusoknál, de néha sűrű mátrixok algoritmusai is alkalmazhatók, amikor is a hatékonyságot a feldolgozandó indexek kis száma biztosítja.
 
Egy ''A'' mátrix sorainak és oszlopainak átrendezésével lehetséges egy olyan ''A’'' mátrix, mely rendelkezik alsósáv szélességgel. Számos algoritmus létezik a sávszélességek minimalizálására.
 
===Átlós mátrix===
A sávmátrix sajátos típusa az [[diagonális mátrix|átlós mátrix]], ennek legoptimálisabb tárolási módja egy egydimenziós tömb, melybe a főátló elemeit visszük be, így az ''n'' x ''n'' számú bejegyzés ''n''-re csökken.
 
===Szimmetrikus mátrix===
A szimmetrikus ritka mátrixok [[irányítatlan gráf]]ok [[szomszédsági mátrix|szomszédsági mátrixaiból]] erednek, hatékony tárolási módjuk a szomszédsági lista.
 
===Helyettesítések csökkentése===
'''Helyettesítésnek''' nevezzük azt a folyamatot, mely során egy eredetileg nulla értékű elem nemnulla elemmé válik, például egy algoritmus futtatása alatt. Az egy algoritmus futtatása során elvégzendő műveletek memóriaigényének csökkentésére hasznos a helyettesítések számának minimalizálása a mátrix sorainak és oszlopainak átrendezésével. A szimbolikus Cholesky-felbontás felhasználható a lehető legrosszabb helyettesítés kiszámolására még mielőtt alkalmaznánk a tényleges [[Cholesky-felbontás]]t.
 
Természetesen nem csak Cholesky módszere létezik, népszerűek az ortogonalizációs módszerek (pl. QR felbontás) is a legkisebb négyzetek módszerét használó feladatok esetén. Bár elméletileg a helyettesítés változatlan, a gyakorlatban a „hamis nemnullák” változhatnak módszerenként. Továbbá ezen algoritmusok szimbolikus változatai ugyanúgy használhatók a legrosszabb helyettesítés felmérésére, akárcsak a szimbolikus Cholesky-féle felbontás.
 
==Ritka mátrixok egyenleteinek megoldása==
Ritka mátrixok egyenleteinek megoldására iteratív és direkt módszereket is dolgoztak ki.
 
A [[konjugált gradiens módszer]]hez vagy az általánosított minimális reziduális módszerhez hasonló iteratív módszerek az <math>Ax_i</math> mátrix-vektor szorzat gyors kiszámítását használják fel, ahol ''A'' egy ritka mátrix. Az előtesztelők használata jelentősen felgyorsítja az efféle iteratív módszerek konvergenciáját.
 
==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}}
*{{cite journal|doi=10.1007/BF02521587|title=Reducing the profile of sparse symmetric matrices|year=1976|last1=Snay|first1=Richard A.|journal=Bulletin Géodésique|volume=50|issue=4|pages=341}} Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.
 
==Bővebben==
* {{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}}
[[Category:Sparse matrices]]
 
== Műszaki jellemzők ==
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Szerkesztő:Vigyori93/próbalap”