Co to jest narzut w rzadkim mnożeniu macierzy

10

Czy mnożenie macierzy (zarówno Mat * Mat, jak i Mat * Vec) skaluje się z liczbą niezerowych lub z rozmiarem macierzy? Lub jakąś kombinację tych dwóch.

Co z kształtem.

Na przykład mam macierz 100 x 100 ze 100 wartościami lub macierz 1000 x 1000 ze 100 wartościami.

Czy podczas kwadratowania tych macierzy (lub mnożenia ich przez podobne macierze o podobnej rzadkości) pierwsza (100 x 100) będzie szybsza niż druga (1000 x 1000)? Czy to zależy od tego, gdzie są wartości?

Jeśli zależy to od implementacji, jestem zainteresowany odpowiedzią na PETSc.

linear-algebra performance sparse-matrix

— Andrew Spott
źródło

11

Koszt rzadkiego mnożenia macierzy-wektora skaluje się liniowo z liczbą niezerowych wpisów, ponieważ każdy wpis jest mnożony raz przez pewien wpis w wektorze.

$A$

A = (\begin{array}{ccccc} δ_{1} & β_{1} \\ δ_{2} & β_{2} \\ ⋱ & ⋮ \\ δ_{n - 1} & β_{n - 1} \\ γ_{1} & γ_{2} & \dots & γ_{n - 1} & δ_{n} \end{array}),

$A = \left(\begin{array}{ccccc} \delta_1 & & & & \beta_1 \\ & \delta_2 & & & \beta_2 \\ & & \ddots & & \vdots \\ & & & \delta_{n-1} & \beta_{n-1} \\ \gamma_1 & \gamma_2 & \cdots & \gamma_{n-1} & \delta_n \end{array}\right),$

$A$ $O(n)$ $A^2$ $A$ $A^2$ $A^2$

— Jack Poulson
źródło

4

Po pierwsze, zależy od implementacji. Jeśli zaimplementujesz rzadką macierz jako gęstą macierz i wypełnisz wartości niezerowe, będzie ona skalowana wraz z ogólnym rozmiarem macierzy. Jeśli jest przechowywany jako nonzeroes, będzie skalowany wraz ze skalowaniem czasu dostępu wraz z rozmiarem matrycy.

$O(r^2 n^2)$

Należy jednak zauważyć, że nie ma sensu przechowywać tego, czego nie ma; jeśli zależy Ci na tej wydajności, dlaczego przechowujesz 100 wartości dla matrycy 1000 x 1000? Oznacza to, że co najmniej 90% wierszy / kolumn w ogóle nie ma niezerowych wartości i można je całkowicie usunąć z matrycy. Jeśli wzorzec wartości niezerowych nie zmienia się, rozważ usunięcie zawsze zawsze zerowych wierszy zarówno z tej, jak i z macierzy docelowej; usunie około 90% wysiłku, pozostawiając wydajność dwóch macierzy (100 ² , 1000 ² ) zasadniczo równoważnych.

— Phil H.
źródło

Puste wiersze i kolumny często działają w odniesieniu do problemu (np. Utrzymanie jednolitego odwzorowania między numerem wiersza na lokalizację na obrazie). Będzie kompromis, którego się nie pozbędziesz.

— meawoppl

Dokładnie; pogorszenie wydajności środowiska uruchomieniowego około 10x tylko po to, aby utrzymać mapowanie, które można przechowywać w jednej tablicy 100 ints, nie jest normalnym kompromisem. Ponieważ pytanie dotyczyło wydajności jako pustego rozmiaru skal macierzy, jest to bardzo ważna kwestia, szczególnie dla PETSc, o co pytał.

— Phil H

3

Pełny model wydajności SpMV podano w tym artykule . Pokazuje to wyraźnie, że głównym ogranicznikiem jest szerokość pasma, chociaż można zmniejszyć obciążenie, stosując wiele wektorów. Potem napotkasz ograniczenia dotyczące wydawania instrukcji i limit zaległych instrukcji zapisu, jak sądzę.

— Matt Knepley
źródło