Co to jest narzut w rzadkim mnożeniu macierzy

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.

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 = \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$

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.

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ę.