Řídká matice - Sparse matrix

Příklad řídké matice ${\ Displaystyle \ left ({\ begin {smallmatrix} 11 & 22 & 0 & 0 & 0 & 0 & 0 \\ 0 & 33 & 44 & 0 & 0 & 0 \\ 0 & 0 & 55 & 66 & 77 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 88 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 99 \\\ end {smallmatrix}}$
Výše uvedená řídká matice obsahuje pouze 9 nenulových prvků s 26 nulovými prvky. Jeho řídkost je 74%a jeho hustota je 26%.

Řídká matice získaná při řešení úlohy konečných prvků ve dvou rozměrech. Nenulové prvky jsou zobrazeny černě.

V numerické analýze a vědecké práci na počítači , je řídké matice nebo řídké matice je matice , v níž většina prvků jsou nulové. Neexistuje žádná přísná definice týkající se podílu prvků s nulovou hodnotou, aby se matice kvalifikovala jako řídká, ale společným kritériem je, že počet nenulových prvků je zhruba stejný jako počet řádků nebo sloupců. Naopak pokud je většina prvků nenulová, je matice považována za hustou . Počet prvků s nulovou hodnotou dělený celkovým počtem prvků (např. M × n pro matici m × n) se někdy označuje jako řídkost matice.

Koncepčně odpovídá řídkost systémům s několika párovými interakcemi. Zvažte například řadu koulí spojených pružinami od jedné k druhé: jedná se o řídký systém, protože jsou spojeny pouze sousední koule. Naopak, pokud by stejná řada koulí měla pružiny spojující každou kouli se všemi ostatními koulemi, systém by odpovídal husté matici. Koncept sparity je užitečný v kombinatorice a aplikačních oblastech, jako je teorie sítě a numerická analýza , které mají typicky nízkou hustotu významných dat nebo připojení. Velké řídké matice se často objevují ve vědeckých nebo technických aplikacích při řešení parciálních diferenciálních rovnic .

Při ukládání a manipulaci s řídkými maticemi na počítači je výhodné a často nutné používat specializované algoritmy a datové struktury, které využívají výhody řídké struktury matice. Specializované počítače byly vyrobeny pro řídké matice, protože jsou běžné v oblasti strojového učení. Operace využívající standardní struktury a algoritmy s hustou maticí jsou pomalé a neefektivní, když jsou použity na velké řídké matice, protože zpracování a paměť jsou zbytečné na nulách. Řídká data jsou od přírody snadněji komprimovatelná, a proto vyžadují podstatně méně úložiště . S některými velmi velkými řídkými maticemi nelze manipulovat pomocí standardních algoritmů s hustou maticí.

Uložení řídké matice

Matice je obvykle uložena jako dvourozměrné pole. Každý záznam v poli představuje prvek $a i, j$ matice a je přístupný dvěma indexy $i$ a $j$ . Obvykle, $i$ je index řádek, číslované od shora dolů, a $j$ je index sloupce, číslovány zleva doprava. U matice $m \times n$ je množství paměti potřebné k uložení matice v tomto formátu úměrné $m \times n$ (bez ohledu na skutečnost, že rozměry matice je také nutné uložit).

V případě řídké matice lze podstatné snížení požadavků na paměť realizovat uložením pouze nenulových záznamů. V závislosti na počtu a distribuci nenulových položek lze použít různé datové struktury, které ve srovnání se základním přístupem přinesou obrovské úspory v paměti. Kompromisem je, že přístup k jednotlivým prvkům se stává složitějším a jsou zapotřebí další struktury, aby bylo možné jednoznačně obnovit původní matici.

Formáty lze rozdělit do dvou skupin:

Ty, které podporují efektivní úpravy, například DOK (slovník klíčů), LIL (seznam seznamů) nebo COO (seznam souřadnic). Ty se obvykle používají ke konstrukci matic.
Ty, které podporují efektivní přístup a maticové operace, jako CSR (Compressed Sparse Row) nebo CSC (Compressed Sparse Column).

Slovník klíčů (DOK)

DOK se skládá ze slovníku, který mapuje $(řádek, sloupec)$ - páry na hodnotu prvků. Prvky, které ve slovníku chybí, jsou považovány za nulové. Formát je vhodný pro přírůstkovou konstrukci řídké matice v náhodném pořadí, ale špatný pro iteraci nenulových hodnot v lexikografickém pořadí. Jeden obvykle vytvoří matici v tomto formátu a poté převede na jiný efektivnější formát pro zpracování.

Seznam seznamů (LIL)

LIL ukládá jeden seznam na řádek, přičemž každá položka obsahuje index sloupce a hodnotu. Obvykle jsou tyto položky udržovány seřazené podle indexu sloupců pro rychlejší vyhledávání. Toto je další formát vhodný pro inkrementální konstrukci matic.

Seznam souřadnic (COO)

COO ukládá seznam $(řádků, sloupců, hodnot)$ n -tic. V ideálním případě jsou položky seřazeny nejprve podle indexu řádků a poté podle indexu sloupců, aby se zlepšily časy náhodného přístupu. Toto je další formát, který je vhodný pro konstrukci přírůstkové matice.

Komprimovaný řídký řádek (formát CSR, CRS nebo Yale)

Stlačený řídké řádek (CSR) nebo stlačený skladování řádek (CRS), nebo formát Yale představuje matice $M$ o tři (jednorozměrné) pole, které příslušně obsahují nenulové hodnoty, rozsahy řádky a indexy sloupců. Je podobný COO, ale komprimuje řádkové indexy, odtud název. Tento formát umožňuje rychlý přístup k řádkům a násobení maticových vektorů ( $M x$ ). Formát CSR se používá přinejmenším od poloviny 60. let, přičemž první úplný popis se objevuje v roce 1967.

Formát CSR ukládá řídkou $m \times n$ matici $M$ v řádkové formě pomocí tří (jednorozměrných) polí $(V, COL_INDEX, ROW_INDEX)$ . Let $NNZ$ označují počet nenulových vstupů v $M$ . (Všimněte si, že zde budou použity indexy založené na nule .)

Pole $V$ a $COL_INDEX$ mají délku $NNZ$ a obsahují nenulové hodnoty a sloupcové indexy těchto hodnot.

Pole $ROW_INDEX$ má délku $m + 1$ a kóduje index ve $V$ a $COL_INDEX,$ kde daný řádek začíná. To je ekvivalentní $ROW_INDEX [j]$ kódující celkový počet nenulek nad řádkem $j$ . Posledním prvkem je $NNZ$ , tj. Fiktivní index ve $V$ bezprostředně za posledním platným indexem $NNZ - 1$ .

Například matice

{\ displaystyle {\ begin {pmatrix} 5 & 0 & 0 & 0 \\ 0 & 8 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 6 & 0 & 0 \\\ end {pmatrix}}}

je tedy matice $4 \times 4$ se 4 nenulovými prvky

   V         = [ 5 8 3 6 ]
   COL_INDEX = [ 0 1 2 1 ]
   ROW_INDEX = [ 0 1 2 3 4 ]

za předpokladu jazyka s nulovým indexem.

Chcete -li extrahovat řádek, nejprve definujeme:

   row_start = ROW_INDEX[row]
   row_end   = ROW_INDEX[row + 1]

Poté vezmeme řezy z V a COL_INDEX začínající na row_start a končící na row_end.

Chcete -li extrahovat řádek 1 (druhý řádek) této matice, nastavíme row_start=1a row_end=2. Poté uděláme plátky V[1:2] = [8]a COL_INDEX[1:2] = [1]. Nyní víme, že v řádku 1 máme jeden prvek ve sloupci 1 s hodnotou 8.

V tomto případě reprezentace CSR obsahuje 13 záznamů oproti 16 v původní matici. Formát CSR se ukládá do paměti pouze při $NNZ <(m (n - 1) - 1) / 2$ . Další příklad, matice

{\ displaystyle {\ begin {pmatrix} 10 & 20 & 0 & 0 & 0 & 0 \\ 0 & 30 & 0 & 40 & 0 & 0 \\ 0 & 0 & 50 & 60 & 70 & 0 \\ 0 & 0 & 0 & 0 & 0 & 80 \\\ end {pmatrix}}}}

je matice $4 \times 6$ (24 záznamů) s 8 nenulovými prvky, takže

   V         = [ 10 20 30 40 50 60 70 80 ]
   COL_INDEX = [  0  1  1  3  2  3  4  5 ]   
   ROW_INDEX = [  0  2  4  7  8 ]

Celek je uložen jako 21 záznamů.

$ROW_INDEX$ rozděluje pole $V$ do řad: (10, 20) (30, 40) (50, 60, 70) (80);
$COL_INDEX$ vyrovnává hodnoty ve sloupcích: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Všimněte si, že v tomto formátu je první hodnota $ROW_INDEX$ vždy nula a poslední vždy $NNZ$ , takže jsou v jistém smyslu nadbytečné (i když v programovacích jazycích, kde je potřeba explicitně uložit délku pole, by $NNZ$ nebyl nadbytečný). Přesto se tím vyhnete potřebě zpracovat výjimečný případ při výpočtu délky každého řádku, protože to zaručuje, že vzorec $ROW_INDEX [i + 1] - ROW_INDEX [i]$ funguje pro jakýkoli řádek $i$ . Navíc náklady na paměť tohoto nadbytečného úložiště jsou pravděpodobně pro dostatečně velkou matici nevýznamné.

Řídké maticové formáty Yale (staré a nové) jsou instancemi schématu CSR. Starý formát Yale funguje přesně tak, jak je popsáno výše, se třemi poli; nový formát kombinuje $ROW_INDEX$ a $COL_INDEX$ do jednoho pole a řeší diagonálu matice samostatně.

U matic logické sousednosti lze datové pole vynechat, protože existence položky v řádkovém poli je dostatečná k modelování vztahu binární sousednosti.

Je pravděpodobně známý jako formát Yale, protože byl navržen ve zprávě z Yale Sparse Matrix Package z roku 1977 z Katedry informatiky na Yale University.

Komprimovaný řídký sloupec (CSC nebo CCS)

CSC je podobný CSR s tím rozdílem, že hodnoty jsou čteny nejprve podle sloupců, pro každou hodnotu je uložen index řádku a jsou uloženy ukazatele sloupců. Například CSC je $(val, row_ind, col_ptr)$ , kde $val$ je pole nenulových hodnot (shora dolů, pak zleva doprava) matice; $row_ind$ jsou řádkové indexy odpovídající hodnotám; a $col_ptr$ je seznam $val$ indexů, kde každý sloupec začíná. Název je založen na skutečnosti, že informace o indexu sloupců jsou komprimovány vzhledem k formátu COO. Jeden obvykle používá jiný formát (LIL, DOK, COO) pro stavbu. Tento formát je účinný pro aritmetické operace, krájení sloupců a produkty maticových vektorů. Viz scipy.sparse.csc_matrix . Toto je tradiční formát pro specifikaci řídké matice v MATLABu (prostřednictvím sparsefunkce).

Speciální struktura

Páskovaný

Důležitým zvláštním typem řídkých matic je pásová matice , definovaná následovně. Spodní šířka pásma matice $A$ je nejmenší počet $p$ tak, že vstup $i$ $,$ $j$ zmizí, když $i$ $>$ $j$ $+$ $p$ . Podobně je horní šířka pásma nejmenším číslem $p$ , takže $a$ $i$ $,$ $j$ $= 0,$ kdykoli $i$ $<$ $j$ $-$ $p$ ( Golub & Van Loan 1996 , §1.2.1). Například tridiagonální matice má nižší šířku pásma $1$ a horní šířku pásma $1$ . Jako další příklad má následující řídká matice dolní a horní šířku pásma, která se rovná 3. Všimněte si, že nuly jsou kvůli přehlednosti reprezentovány tečkami.

{\ Displaystyle \ left ({\ begin {smallmatrix} X & X & X & \ cdot & \ cdot & \ cdot & \ cdot & \\ X & X & \ cdot & X & X & \ cdot & \ cdot & \\ X & \ cdot & X & \ cdot & X & \ cdot & \ cdot & \\\ cdot & X & \ cdot & X & \ cdot & X & \ cdot & \\\ cdot & X & X & \ cdot & X & X & X & \\\ cdot & \ cdot & \ cdot & X & X & X & \ cdot & \\\ cdot & \ cdot & \ cd cdot & X & \ cdot & X & \\\ end {smallmatrix}} \ right)}

Matice s relativně malou horní a dolní šířkou pásma jsou známé jako pásové matice a často se hodí pro jednodušší algoritmy než obecné řídké matice; nebo lze někdy použít husté maticové algoritmy a získat účinnost jednoduše smyčkou přes snížený počet indexů.

Přeskupením řádků a sloupců matice $A$ může být možné získat matici $A'$ s nižší šířkou pásma. Pro minimalizaci šířky pásma je navržena řada algoritmů .

Úhlopříčka

Velmi účinná struktura pro extrémní případ pásových matic, diagonální matice , je uložit pouze záznamy v hlavní diagonále jako jednorozměrné pole , takže diagonální $n \times n$ matice vyžaduje pouze $n$ záznamů.

Symetrický

Symetrická řídké matice vzniká jako matice přilehlosti o o neřízené grafu ; lze jej efektivně uložit jako seznam sousedících .

Bloková úhlopříčka

Matrice blokové diagonální se skládá z dílčích matic podél úhlopříčky bloků. Bloková diagonální matice A má tvar

{\ Displaystyle \ mathbf {A} = {\ begin {bmatrix} \ mathbf {A} _ {1} & 0 & \ cdots & 0 \\ 0 & \ mathbf {A} _ {2} & \ cdots & 0 \\\ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & \ cdots & \ mathbf {A} _ {n} \ end {bmatrix}},}

kde A _k je čtvercová matice pro všechna k = 1, ..., n .

Snížení výplně

Fill-in matice jsou ty položky, které změna oproti počáteční nuly na nenulovou hodnotu během provádění algoritmu. Aby se snížily požadavky na paměť a počet aritmetických operací použitých během algoritmu, je užitečné minimalizovat vyplňování přepínáním řádků a sloupců v matici. Symbolický Choleského rozklad může být použita k výpočtu nejhorší možné fill-in před provedením skutečné Choleského rozkladu .

Používají se i jiné metody než Choleskyho rozklad . Ortogonalizační metody (jako je QR faktorizace) jsou běžné například při řešení problémů metodami nejmenších čtverců. Zatímco teoretické vyplnění je stále stejné, v praxi se „falešné nuly“ mohou u různých metod lišit. A symbolické verze těchto algoritmů mohou být použity stejným způsobem jako symbolické Cholesky pro výpočet nejhoršího případu.

Řešení rovnic řídké matice

Obě iterační a přímé metody existují řešení řídké matice.

Iterační metody, jako je metoda konjugovaného gradientu a GMRES, využívají rychlé výpočty produktů maticových vektorů , kde je matice řídká. Použití předběžných kondicionérů může výrazně urychlit sbližování takových iteračních metod. ${\ displaystyle Ax_ {i}}$ ${\ displaystyle A}$

Software

Mnoho softwarových knihoven podporuje řídké matice a poskytuje řešení pro rovnice řídké matice. Následující jsou open-source:

SuiteSparse , sada algoritmů řídké matice, zaměřená na přímé řešení řídkých lineárních systémů.
PETSc , velká C knihovna, obsahující mnoho různých maticových řešičů pro různé formáty maticových úložišť.
Trilinos , velká knihovna C ++, s dílčími knihovnami věnovanými ukládání hustých a řídkých matic a řešení odpovídajících lineárních systémů.
Eigen3 je C ++ knihovna, která obsahuje několik řídkých maticových řešičů. Žádný z nich však není paralelizován .
MUMPS ( MU ltifrontal M assively P arallel sparse direct S olver), napsaný ve Fortran90, je frontální řešitel .
DUNE , knihovna konečných prvků, která má také dílčí knihovnu pro řídké lineární systémy a jejich řešení.
PaStix .
SuperLU .
Armadillo poskytuje uživatelsky přívětivý obal C ++ pro BLAS a LAPACK.
SciPy poskytuje podporu pro několik řídkých formátů matic, lineární algebry a řešičů.
Balíček SPArse Matrix (spam) R a Python pro řídké matice.
Wolfram Language Tools pro práci s řídkými poli
ALGLIB je knihovna C ++ a C# s řídkou podporou lineární algebry
Knihovna ARPACK Fortran 77 pro diagonalizaci a manipulaci řídké matice pomocí Arnoldiho algoritmu
SPARSE Reference (starý) Balíček NIST pro (skutečnou nebo komplexní) řídkou diagonalizaci matice
Knihovna SLEPc pro řešení rozsáhlých lineárních systémů a řídkých matic
Sympiler , generátor a knihovna kódů pro konkrétní doménu pro řešení lineárních systémů a kvadratických programovacích problémů.
Scikit-learn Balíček Pythonu pro analýzu dat včetně řídkých matic.

Dějiny

Termín řídká matice pravděpodobně vytvořil Harry Markowitz, který zahájil nějakou průkopnickou práci, ale poté opustil pole.

Viz také

Poznámky

Reference

Golub, Gene H .; Van Loan, Charles F. (1996). Matrix Computations (3. vyd.). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
Stoer, Josef; Bulirsch, Roland (2002). Úvod do numerické analýzy (3. vyd.). Berlín, New York: Springer-Verlag . ISBN 978-0-387-95452-3.
Tewarson, Reginald P. (květen 1973). Řídké matice (součást série Matematika ve vědě a technice) . Academic Press Inc. (Tato kniha profesora Státní univerzity v New Yorku ve Stony Book byla první knihou výhradně věnovanou řídkým matricím. Na této univerzitě byly počátkem 80. let nabízeny postgraduální kurzy využívající toto jako učebnici).
Banka, Randolph E .; Douglas, Craig C. „Sparse Matrix Multiplication Package“ (PDF) .
Pissanetzky, Sergio (1984). Technologie řídké matice . Akademický tisk.
Snay, Richard A. (1976). „Snížení profilu řídkých symetrických matic“. Bulletin Géodésique . 50 (4): 341–352. Bibcode : 1976BGeod..50..341S . doi : 10,1007/BF02521587 . hdl : 2027/uc1.31210024848523 . S2CID 123079384 . Také technické memorandum NOAA NOS NGS-4, National Geodetic Survey, Rockville, MD.

Další čtení

Gibbs, Norman E .; Poole, William G .; Stockmeyer, Paul K. (1976). „Porovnání několika algoritmů redukce šířky pásma a profilu“ . Transakce ACM na matematickém softwaru . 2 (4): 322–330. doi : 10,1145/355705,355707 . S2CID 14494429 .
Gilbert, John R .; Moler, Cleve; Schreiber, Robert (1992). „Řídké matice v MATLABu: Návrh a implementace“ . SIAM Journal o maticové analýze a aplikacích . 13 (1): 333–356. CiteSeerX 10.1.1.470.1054 . doi : 10,1137/0613024 .
Výzkum řídkých algoritmů matice na Texas A&M University.
Kolekce SuiteSparse Matrix
MALÝ projekt Projekt financovaný EU na řídkých modelech, algoritmech a učení se slovníku pro rozsáhlá data.

^ Saad, Yousef (2003). Iterační metody pro řídké lineární systémy . SIAM.

[12] Saad, Yousef (2003). Iterační metody pro řídké lineární systémy . SIAM.

Languages

In other projects