Řídká matice

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledává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 klasickým způsobem je třeba bytů.

Nejrozsáhlejší maticová úloha, v roce 2002, dle [1], 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. 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 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[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 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 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:

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

Literatura[editovat | editovat zdroj]

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