Řídká matice
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8a/Finite_element_sparse_matrix.png/204px-Finite_element_sparse_matrix.png)
Ří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 [1] (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.[pozn. 1]
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).
- (pole sloupcových indexů ukládaných prvků),
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
- ↑ 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.
Reference
- ↑ The World’s Largest Matrix Computation. www.mathworks.com [online]. MathWorks, 2002 [cit. 2021-11-26]. Dostupné online.
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
Média použitá na této stránce
Illustration of the en:Finite element method, the en:sparse matrix of the discretized problem.