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.

Andrew Spott
źródło

Odpowiedzi:

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=(δ1β1δ2β2δn1βn1γ1γ2γn1δn),

AO(n)A2AA2A2

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(r2n2)

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 2 , 1000 2 ) 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