Řídká matice

Ří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é.

Řídká matice získána jako řešení příkladu pomocí metody konečných prvků. Nenulové prvky jsou zakresleny jako černé čtverečky.

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

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, 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.

Typickými představiteli řídkých matic jsou matice používané pro výpočet metodou konečných prvků (např. matice tuhosti), kde spolu typicky interagují nejbližší prvky a tato interakce je reprezentována prvky matice, které leží na její diagonále, případně v její blízkosti.

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

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 zkomplikovat (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

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}{rrrr}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).

Odkazy

Literatura

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

Externí odkazy

• Obrázky, zvuky či videa k tématu řídká matice na Wikimedia Commons