Řídká matice

Technology

12 hours ago

Author

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. +more * Ří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. +more 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. +more ří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}. +more 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, 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

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í. +more 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).