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

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  klasickým způsobem je třeba  bytů.

Nejrozsáhlejší maticová úloha, v roce 2002, byl výpočet dominantního vlastního vektoru matice řádu  (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  je nenulový, pokud webová stránka s indexem  obsahuje hypertextový odkaz na webovou stránku s indexem ). 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  mající  nenulových prvků . V souřadnicovém formátu ukládáme v podstatě uspořádané trojice

Na uložení celé matice je tedy potřeba řádově  čísel (celočíselná proměnná dostatečného rozsahu zabere stejně jako reálné číslo ve formátu double 8 bytů). Pokud , 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:

pak jednotlivá pole CSR formátu jsou

 (pole obsahující všechny ukládané prvky),
 (pole sloupcových indexů ukládaných prvků),
 (pole ukazatelů na začátky řádků do pole Data).

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

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

Odkazy

Poznámky

Reference

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

Externí odkazy