Rzadka macierz

„rzadkość” przekierowuje tutaj. W przypadku innych zastosowań zobacz Rzadkie (ujednoznacznienie) .

Przykład rzadkiej macierzy ${\ Displaystyle \ lewo ({\ rozpocząć {mała matryca} 11 i 22 i 0 i 0 i 0 i 0 i 0 \\ 0 i 33 i 44 i 0 i 0 i 0 i 0 \\ 0 i 0 i 55 i 66 i 77 i 0 i 0 \\ 0 i 0 i 0 i 0 i 88 i 0 \\ 0 i 0 i 0&0&0&0&99\\\koniec {małamacierz}}\prawo)}$

Powyższa rzadka macierz zawiera tylko 9 niezerowych elementów, z 26 elementami zerowymi. Jego rzadkość wynosi 74%, a gęstość 26%.

Rzadka macierz uzyskana podczas rozwiązywania problemu elementów skończonych w dwóch wymiarach. Elementy niezerowe są pokazane na czarno.

W analizie numerycznej i obliczeniach naukowych rzadka macierz lub rzadka tablica to macierz , w której większość elementów wynosi zero. Nie ma ścisłej definicji dotyczącej proporcji elementów o wartości zerowej, aby macierz kwalifikowała się jako rzadka , ale powszechnym kryterium jest to, że liczba elementów niezerowych jest w przybliżeniu równa liczbie wierszy lub kolumn. Natomiast jeśli większość elementów jest różna od zera, macierz jest uważana za gęstą . Liczba elementów o wartości zerowej podzielona przez całkowitą liczbę elementów (np. m × n dla macierzy m × n ) jest czasami określana jako rzadkość macierzy.

Koncepcyjnie rzadkość odpowiada systemom z kilkoma interakcjami parami. Rozważmy na przykład linię kulek połączonych sprężynami od jednej do drugiej: jest to rzadki system, ponieważ połączone są tylko sąsiednie kulki. Z drugiej strony, gdyby ta sama linia kulek miała sprężyny łączące każdą kulkę ze wszystkimi innymi kulkami, system odpowiadałby gęstej matrycy. Koncepcja rzadkości jest przydatna w kombinatoryce i obszarach zastosowań, takich jak teoria sieci i analiza numeryczna , które zazwyczaj mają niską gęstość istotnych danych lub połączeń. Często pojawiają się duże rzadkie macierze zastosowania naukowe lub inżynierskie przy rozwiązywaniu równań różniczkowych cząstkowych .

Podczas przechowywania i manipulowania macierzami rozrzedzonymi na komputerze korzystne i często konieczne jest stosowanie wyspecjalizowanych algorytmów i struktur danych , które wykorzystują rozrzedzoną strukturę macierzy. Wyspecjalizowane komputery zostały stworzone dla rzadkich macierzy, ponieważ są one powszechne w dziedzinie uczenia maszynowego. Operacje wykorzystujące standardowe struktury i algorytmy gęstej macierzy są powolne i nieefektywne, gdy są stosowane do dużych rzadkich macierzy, ponieważ przetwarzanie i pamięć są marnowane na zerach. Rzadkie dane są z natury łatwiejsze do skompresowania a tym samym wymaga znacznie mniej miejsca do przechowywania . Niektórymi bardzo dużymi rzadkimi macierzami nie da się manipulować przy użyciu standardowych algorytmów gęstej macierzy.

Przechowywanie rzadkiej macierzy

Macierz jest zwykle przechowywana jako tablica dwuwymiarowa. Każdy wpis w tablicy reprezentuje element ai _{. , j} macierzy i jest dostępny za pomocą dwóch indeksów i oraz j Konwencjonalnie, i to indeks wiersza, numerowany od góry do dołu, a j to indeks kolumny, numerowany od lewej do prawej. W przypadku m × n ilość pamięci wymaganej do przechowywania macierzy w tym formacie jest proporcjonalna do m × n (pomijając fakt, że wymiary macierzy również muszą być przechowywane).

W przypadku rzadkiej macierzy można uzyskać znaczne zmniejszenie zapotrzebowania na pamięć, przechowując tylko niezerowe wpisy. W zależności od liczby i rozkładu niezerowych wpisów można zastosować różne struktury danych, co daje ogromne oszczędności pamięci w porównaniu z podejściem podstawowym. Kompromis polega na tym, że dostęp do poszczególnych elementów staje się bardziej złożony i potrzebne są dodatkowe struktury, aby móc jednoznacznie odzyskać oryginalną matrycę.

Formaty można podzielić na dwie grupy:

• Te, które wspierają wydajną modyfikację, takie jak DOK (Słownik kluczy), LIL (Lista list) czy COO (Lista współrzędnych). Są one zwykle używane do konstruowania macierzy.
• Te, które wspierają wydajny dostęp i operacje macierzowe, takie jak CSR (Compressed Sparse Row) lub CSC (Compressed Sparse Column).

Słownik kluczy (DOK)

DOK składa się ze słownika , który odwzorowuje (wiersz, kolumna) - pary na wartości elementów. Elementy, których brakuje w słowniku, są traktowane jako zero. Format jest dobry do przyrostowego konstruowania rzadkiej macierzy w przypadkowej kolejności, ale kiepski do iteracji po wartościach niezerowych w porządku leksykograficznym. Zwykle konstruuje się macierz w tym formacie, a następnie konwertuje do innego, bardziej wydajnego formatu do przetwarzania.

Lista list (LIL)

LIL przechowuje jedną listę na wiersz, z każdym wpisem zawierającym indeks kolumny i wartość. Zazwyczaj wpisy te są sortowane według indeksu kolumny w celu szybszego wyszukiwania. Jest to kolejny format dobry do budowy macierzy przyrostowej.

Lista współrzędnych (COO)

COO przechowuje listę krotek (wiersz, kolumna, wartość) . Idealnie wpisy są sortowane najpierw według indeksu wiersza, a następnie według indeksu kolumny, aby poprawić czasy dostępu swobodnego. Jest to kolejny format, który jest dobry do budowy macierzy przyrostowej.

Skompresowany rzadki wiersz (format CSR, CRS lub Yale)

Skompresowany rzadki wiersz (CSR) lub skompresowany magazyn wierszy (CRS) lub format Yale reprezentuje macierz M za pomocą trzech (jednowymiarowych) tablic, które odpowiednio zawierają wartości niezerowe, zakresy wierszy i indeksy kolumn. Jest podobny do COO, ale kompresuje indeksy wierszy, stąd nazwa. Ten format umożliwia szybki dostęp do wierszy i mnożenie macierzy przez wektory ( M x ). Format CSR jest używany co najmniej od połowy lat 60., a pierwszy pełny opis pojawił się w 1967 r.

Format CSR przechowuje rzadką macierz m × n M w postaci wierszy przy użyciu trzech (jednowymiarowych) tablic (V, COL_INDEX, ROW_INDEX) . Niech NNZ oznacza liczbę niezerowych wpisów w M . (Zauważ, że należy tu stosować indeksy od zera ).

• Tablice V i COL_INDEX mają długość NNZ i zawierają odpowiednio wartości niezerowe i indeksy kolumn tych wartości.
• Tablica ROW_INDEX ma długość m + 1 i koduje indeks w V i COL_INDEX , gdzie zaczyna się dany wiersz. Jest to równoważne z ROW_INDEX[j] całkowitej liczby niezerowych powyżej wiersza j . Ostatnim elementem jest NNZ , tj. fikcyjny indeks w V zaraz po ostatnim poprawnym indeksie NNZ - 1 .

Na przykład macierz

$${\ Displaystyle {\ początek {pmatrix} 5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\koniec {pmatrix}}}$$

jest macierzą 4 × 4 z 4 niezerowymi elementami, stąd

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

zakładając język o zerowym indeksie.

Aby wyodrębnić wiersz, najpierw definiujemy:

wiersz_początkowy = ROW_INDEX[wiersz] wiersz_end = ROW_INDEX[wiersz + 1]

Następnie bierzemy wycinki z V i COL_INDEX zaczynając od row_start i kończąc na row_end.

Aby wyodrębnić wiersz 1 (drugi wiersz) tej macierzy, ustawiamy row_start=1 i row_end=2 . Następnie tworzymy plasterki V[1:2] = [8] i COL_INDEX[1:2] = [1] . Teraz wiemy, że w 1. wierszu mamy jeden element w 1. kolumnie o wartości 8.

W tym przypadku reprezentacja CSR zawiera 13 wpisów, w porównaniu do 16 w oryginalnej matrycy. Format CSR zapisuje w pamięci tylko wtedy, gdy NNZ < ( m ( n - 1) - 1) / 2 .

Inny przykład, macierz

$${\ Displaystyle {\ początek {pmatrix} 10 i 20 i 0&0&0&0 \\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\koniec {pmatrix}}}$$

jest macierzą 4 × 6 (24 wpisy) z 8 niezerowymi elementami, więc

 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 ] 

Całość jest przechowywana jako 21 wpisów: 8 w V , 8 w COL_INDEX i 5 w ROW_INDEX .

• ROW_INDEX dzieli tablicę V na wiersze: (10, 20) (30, 40) (50, 60, 70) (80) , wskazując indeks V (i COL_INDEX ), gdzie każdy wiersz się zaczyna i kończy;
• COL_INDEX wyrównuje wartości w kolumnach: (10, 20, ...) (0, 30, 0, 40, ...) (0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80) .

Zauważ, że w tym formacie pierwsza wartość ROW_INDEX to zawsze zero, a ostatnia to zawsze NNZ , więc są one w pewnym sensie redundantne (chociaż w językach programowania, w których długość tablicy musi być jawnie przechowywana, NNZ nie byłoby redundantne). Niemniej jednak pozwala to uniknąć konieczności obsługi wyjątkowego przypadku podczas obliczania długości każdego wiersza, ponieważ gwarantuje, że formuła ROW_INDEX[ i + 1] − ROW_INDEX[ i ] działa dla dowolnego wiersza i . Co więcej, koszt pamięci tej nadmiarowej pamięci jest prawdopodobnie nieistotny dla wystarczająco dużej macierzy.

(Stare i nowe) rzadkie formaty macierzy Yale są instancjami schematu CSR. Stary format Yale działa dokładnie tak, jak opisano powyżej, z trzema tablicami; nowy format łączy ROW_INDEX i COL_INDEX w jedną tablicę i oddzielnie obsługuje przekątną macierzy.

W przypadku logicznych macierzy sąsiedztwa tablicę danych można pominąć, ponieważ istnienie wpisu w tablicy wierszy jest wystarczające do zamodelowania binarnej relacji sąsiedztwa.

Jest prawdopodobnie znany jako format Yale, ponieważ został zaproponowany w raporcie Yale Sparse Matrix Package z 1977 r. Z Wydziału Informatyki Uniwersytetu Yale.

Skompresowana kolumna rzadka (CSC lub CCS)

CSC jest podobny do CSR, z tą różnicą, że wartości są odczytywane najpierw przez kolumnę, dla każdej wartości przechowywany jest indeks wiersza, a wskaźniki kolumn są przechowywane. Na przykład CSC to (val, row_ind, col_ptr) , gdzie val jest tablicą (od góry do dołu, a następnie od lewej do prawej) niezerowych wartości macierzy; row_ind to indeksy wierszy odpowiadające wartościom; a col_ptr jest listą val indeksy, od których zaczyna się każda kolumna. Nazwa opiera się na fakcie, że informacje o indeksie kolumn są kompresowane względem formatu COO. Zwykle do budowy używa się innego formatu (LIL, DOK, COO). Ten format jest wydajny w przypadku operacji arytmetycznych, dzielenia kolumn i iloczynów macierzowo-wektorowych. Zobacz scipy.sparse.csc_matrix . Jest to tradycyjny format określania rzadkiej macierzy w MATLAB-ie (poprzez rozrzedzoną ).

Specjalna struktura

Naprzemiennie

Główny artykuł: macierz pasm

Ważnym specjalnym typem rzadkich macierzy jest macierz pasmowa , zdefiniowana w następujący sposób. Niższa ai _{szerokość , j} pasma macierzy A jest najmniejszą liczbą p taką, że wpis znika zawsze, gdy i > j + p . Podobnie górna szerokość pasma jest najmniejszą liczbą p taką, że a _{i , j} = 0 zawsze, gdy i < j − p ( Golub i Van Loan 1996 , §1.2.1). Na przykład macierz trójdiagonalna ma niższą szerokość pasma 1 i górną szerokość pasma 1 . Jako inny przykład, poniższa rzadka macierz ma zarówno dolną, jak i górną szerokość pasma równą 3. Zauważ, że zera są reprezentowane przez kropki dla przejrzystości.

$${\ Displaystyle {\ rozpocząć {bmatrix} 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 &\cdot &\cdot &X&\ cdot &X&\\\koniec{bmacierzy}}}$$

Macierze o stosunkowo małej górnej i dolnej przepustowości są znane jako macierze pasmowe i często nadają się do prostszych algorytmów niż ogólne macierze rzadkie; lub czasami można zastosować gęste algorytmy macierzowe i zwiększyć wydajność po prostu zapętlając zmniejszoną liczbę indeksów.

Poprzez przestawienie wierszy i kolumn macierzy A możliwe może być uzyskanie macierzy A ′ o mniejszej szerokości pasma. Szereg algorytmów zaprojektowano w celu minimalizacji przepustowości .

Przekątna

Bardzo wydajna struktura dla skrajnego przypadku macierzy pasmowych, macierzy diagonalnej , polega na przechowywaniu tylko wpisów na głównej przekątnej jako jednowymiarowej tablicy , więc macierz diagonalna n × n wymaga tylko n wpisów.

Symetryczny

Symetryczna rzadka macierz powstaje jako macierz sąsiedztwa grafu nieskierowanego ; może być wydajnie przechowywany jako lista sąsiedztwa .

Przekątna bloku

Macierz diagonalna bloków składa się z podmacierzy wzdłuż jej diagonalnych bloków. Macierz A o przekątnej bloku ma postać

$${\ Displaystyle \ mathbf {A} = {\ rozpocząć {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}},}$$

gdzie A _k jest macierzą kwadratową dla wszystkich k = 1, ..., n .

Zmniejszenie wypełnienia

Wypełnieniem macierzy są te wpisy, które zmieniają się od początkowego zera do wartości niezerowej podczas wykonywania algorytmu. Aby zmniejszyć wymagania dotyczące pamięci i liczbę operacji arytmetycznych używanych podczas algorytmu, warto zminimalizować wypełnianie, przełączając wiersze i kolumny w macierzy. Symboliczna dekompozycja Cholesky'ego może być wykorzystana do obliczenia najgorszego możliwego wypełnienia przed wykonaniem rzeczywistej dekompozycji Cholesky'ego .

są inne metody niż rozkład Cholesky'ego . Metody ortogonalizacji (takie jak faktoryzacja QR) są powszechne, na przykład przy rozwiązywaniu problemów metodą najmniejszych kwadratów. Chociaż teoretyczne wypełnienie jest nadal takie samo, w praktyce „fałszywe zera” mogą być różne dla różnych metod. A symbolicznych wersji tych algorytmów można używać w taki sam sposób, jak symbolicznego Cholesky'ego do obliczania wypełnienia w najgorszym przypadku.

Rozwiązywanie rzadkich równań macierzowych

zarówno iteracyjne , jak i bezpośrednie metody rozwiązywania rzadkich macierzy.

Metody iteracyjne, takie jak $metoda$ gradientu sprzężonego i GMRES $,$ wykorzystują szybkie obliczenia iloczynów macierzowo-wektorowych gdzie rzadka Zastosowanie warunków wstępnych może znacznie przyspieszyć konwergencję takich metod iteracyjnych.

Oprogramowanie

Wiele bibliotek oprogramowania obsługuje rzadkie macierze i zapewnia rozwiązania dla rzadkich równań macierzowych. Następujące są open-source:

• SuiteSparse , zestaw rzadkich algorytmów macierzowych, ukierunkowanych na bezpośrednie rozwiązanie rzadkich systemów liniowych.
• PETSc , duża biblioteka C, zawierająca wiele różnych rozwiązań macierzowych dla różnych formatów przechowywania macierzy.
• Trilinos , duża biblioteka C++ z podbibliotekami przeznaczonymi do przechowywania gęstych i rzadkich macierzy oraz rozwiązywania odpowiednich systemów liniowych.
• Eigen3 to biblioteka C++, która zawiera kilka solwerów macierzy rzadkich. Jednak żaden z nich nie jest równoległy .
• MUMPS ( M assively P arallel sparse direct S olver ) , napisany w Fortran90, to frontalny solver .
• deal.II , biblioteka elementów skończonych, która ma również podbibliotekę dla rzadkich systemów liniowych i ich rozwiązań.
• DUNE , kolejna biblioteka elementów skończonych, która ma również podbibliotekę dla rzadkich systemów liniowych i ich rozwiązań.
• PaStix .
• SuperLU .
• Armadillo zapewnia przyjazne dla użytkownika opakowanie C++ dla BLAS i LAPACK.
• SciPy zapewnia obsługę kilku rzadkich formatów macierzy, algebry liniowej i solwerów.
• SPArse Matrix (spam) Pakiet R i Python dla rzadkich macierzy.
• Wolfram Language Tools do obsługi rzadkich tablic
• ALGLIB to biblioteka C++ i C# z rzadką obsługą algebry liniowej
• ARPACK Fortran 77 do diagonalizacji i manipulacji macierzami rzadkimi przy użyciu algorytmu Arnoldiego
• SPARSE Reference (stary) pakiet NIST do (rzeczywistej lub złożonej) rzadkiej diagonalizacji macierzy
• SLEPc Biblioteka do rozwiązywania wielkoskalowych systemów liniowych i rzadkich macierzy
• Sympiler , specyficzny dla domeny generator kodu i biblioteka do rozwiązywania problemów z systemami liniowymi i programowaniem kwadratowym.
• scikit-learn , biblioteka Pythona do uczenia maszynowego , zapewnia obsługę rzadkich macierzy i solwerów.
• sprs implementuje rzadkie macierzowe struktury danych i algorytmy algebry liniowej w czystym Rust.
• Basic Matrix Library (bml) obsługuje kilka rzadkich formatów macierzy i algorytmów algebry liniowej z powiązaniami dla języków C, C++ i Fortran.

Historia

Termin macierz rzadka został prawdopodobnie ukuty przez Harry'ego Markowitza , który zainicjował pionierskie prace, ale potem opuścił pole.

Zobacz też

• Reprezentacja macierzowa
• Zasada Pareto
• Poszarpana matryca
• Macierz jednowejściowa
• Matryca Skyline
• Rzadki kod wykresu
• Rzadki plik
• Format pliku Harwell-Boeing
• Formaty wymiany Matrix Market

Notatki

•   Golub, Gene H .; Van Loan, Charles F. (1996). Obliczenia macierzowe (wyd. 3). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9 .
•   Stoer, Józef; Bulirsch, Roland (2002). Wprowadzenie do analizy numerycznej (wyd. 3). Berlin, Nowy Jork: Springer-Verlag . ISBN 978-0-387-95452-3 .
• Tewarson, Reginald P. (maj 1973). Matryce rzadkie (część serii Matematyka w nauce i inżynierii) . Academic Press Inc. (Ta książka, napisana przez profesora na Uniwersytecie Stanowym Nowego Jorku w Stony Book, była pierwszą książką poświęconą wyłącznie rzadkim macierzom. Kursy dla absolwentów wykorzystujące ją jako podręcznik były oferowane na tym uniwersytecie we wczesnych latach 80-tych).
• Bank, Randolph E.; Douglas, Craig C. „Pakiet mnożenia rzadkiej macierzy” (PDF) .
•   Pissanetzky, Sergio (1984). Technologia rzadkiej matrycy . Prasa akademicka. ISBN 9780125575805 .
•   Snay, Richard A. (1976). „Zmniejszenie profilu rzadkich macierzy symetrycznych”. Biuletyn Géodésique . 50 (4): 341–352. Bibcode : 1976BGeod..50..341S . doi : 10.1007/BF02521587 . hdl : 2027/uc1.31210024848523 . S2CID 123079384 . Również memorandum techniczne NOAA NOS NGS-4, National Geodetic Survey, Rockville, MD.

Dalsza lektura

•   Gibbs, Norman E.; Poole, William G.; Stockmeyer, Paul K. (1976). „Porównanie kilku algorytmów redukcji przepustowości i profilu” . Transakcje ACM dotyczące oprogramowania matematycznego . 2 (4): 322–330. doi : 10.1145/355705.355707 . S2CID 14494429 .
•   Gilbert, John R.; Moler, Cleve; Schreiber, Robert (1992). „Rzadkie macierze w MATLAB: projektowanie i wdrażanie” . SIAM Journal o analizie macierzy i zastosowaniach . 13 (1): 333–356. CiteSeerX 10.1.1.470.1054 . doi : 10.1137/0613024 .
• Badania rzadkich algorytmów macierzy na Uniwersytecie Texas A&M.
• Kolekcja SuiteSparse Matrix
• Projekt SMALL Finansowany ze środków UE projekt poświęcony modelom rzadkim, algorytmom i uczeniu słownikowemu na potrzeby danych na dużą skalę.