Řídká matice

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Řídká matice získána jako řešení příkladu pomocí metody konečných prvků. Nenulové prvky jsou zakresleny jako černé čtverečky.

Řídké matice představují speciální třídu matic, jejichž struktura (zpravidla) nulových a nenulových prvků umožňuje provádět operace (klasické maticové operace ale i výpočetní, zejména uložení do paměti počítače) efektivněji, než pro tzv. plné (husté) matice, tedy matice mající všechny prvky obecně nenulové.

Konkrétní definice řídké matice se v různých pramenech liší. Nejčastěji se setkáme s některou z následujících definic:

  • Řídká je matice, která má převážnou většinu prvků nulových.
  • Řídká je matice, která je uložená v řídkém formátu.
  • Řídká je matice, která má strukturu nenulových prvků, kterou dokážeme využít ke zefektivnění práce s maticí.

Uložení řídké matice[editovat | editovat zdroj]

Při praktickém řešení úloh s maticemi na počítači, je primární úkol matici uložit do paměti počítače (na harddisk) a později s ní provádět různé operace (řešení soustavy rovnic, faktorizace, etc.), tedy držet matici v operační paměti počítače.

Uvažujme pro jednoduchost čtvercové regulární matice (tedy matice mající, mimo jiné, alespoň jeden nenulový prvek v každém řádku a sloupci). Uvažujme dále, že všechna čísla jsou uložena v dnes standardní dvojité přesnosti (double), tedy každé číslo zabere 8 bytů.

Na uložení matice A\in\mathbb{R}^{n\times n} klasickým způsobem je třeba 8n^2 bytů.

Nejrozsáhlejší maticová úloha, v roce 2002, dle [1], byl výpočet dominantního vlastního vektoru matice řádu n=2.7\times 10^9 (jedná se o tzv. Google matrix (googlovská matice), kde počet řádků a sloupců matice odpovídá počtu webových stránek indexovaných vyhledávačem Google, je tedy zřejmé, že velikost nejrozsáhlejšího problému od roku 2002 narostla). Pro uložení jednoho řádku této matice v hustém formátu by bylo zapotřebí cca 20.1 GB, pro uložení celé matice pak cca 39290171 TB. Připomeňme, že matici není potřeba jen uložit na harddisk(y); je též potřeba s ní provádět operace, a tedy s ní manipulovat v operační paměti.

Googlovská matice je nicméně silně strukturovaná a většina jejích prvků je nulových (prvek a_{i,j} je nenulový, pokud webová stránka s indexem i obsahuje hypertextový odkaz na webovou stránku s indexem j). Pro uložení (nejen) takto rozsáhlých matic se používají tzv. řídké formáty.

Souřadnicový formát[editovat | editovat zdroj]

Nejjednodušší z hlediska implementace (nikoliv však z hlediska provádění maticových operací) je souřadnicový formát. Uvažujme matici A\in\mathbb{R}^{n\times n} mající k>n nenulových prvků a_{i,j}. V souřadnicovém formátu ukládáme v podstatě uspořádané trojice

(i,j,a_{i,j}).

Na uložení celé matice je tedy potřeba řádově 3k čísel (celočíselná proměnná dostatečného rozsahu zabere stejně jako reálné číslo ve formátu double 8 bytů). Pokud 3k<n^2, pak je řídký formát úspornější.

Uspořádané trojice mohou být v paměti seřazeny různým způsobem (matice může být uložena po řádcích, po sloupcích, či náhodně) což může usnadnit ale i z komplikovat (zrychlit či výrazně zpomalit) přístup k datům.

Souřadnicový formát řídkých matic ukládaný po sloupcích používá například Matlab.

CSR formát[editovat | editovat zdroj]

Standardním formátem pro ukládání řídkých matic je CSR (compressed sparse rows), volně přeloženo: komprimované řídké řádky. Matice se uloží do tří polí. První pole obsahuje všechny nenulové (respektive ukládané) prvky matice srovnané po řádcích (prvky v rámci jednoho řádku mohou být srovnány v libovolném pořadí). Druhé pole obsahuje sloupcové indexy jednotlivých prvků. Třetí pole obsahuje ukazatele začátků řádků. Uvažujme následující příklad:

A=\left[\begin{array}{cccc}10&&3\\&8&&4\\2&2&6\\&&&5\end{array}\right],

pak jednotlivá pole CSR formátu jsou

Data=[10,3,8,4,2,2,6,5] (pole obsahující všechny ukládané prvky),
Cols=[1,3,2,4,1,2,3,4] (pole sloupcových indexů ukládaných prvků),
Rows=[1,3,5,8] (pole ukazatelů na začátky řádků do pole Data).

Pokud ukládáme k prvků, pak je k uložení matice v CSR formátu potřeba 2k+n čísel.

Analogicky lze použít formát CSC (compressed sparse columns).

Literatura[editovat | editovat zdroj]

Bartko, R. - Miller, M.: MATLAB I - algoritmizácia a riešenie úloh