Jaki jest najlepszy sposób określenia liczby niezerowych w rzadkim mnożeniu macierzy?

Zastanawiałem się, czy istnieje szybka i skuteczna metoda wcześniejszego znalezienia liczby niezerowych dla operacji rzadkiego mnożenia macierzy, zakładając, że obie macierze są w formacie CSC lub CSR.

Wiem, że jest jeden w pakiecie smmp, ale potrzebuję czegoś, co jest już zaimplementowane w C lub C ++.

Każda pomoc będzie mile widziana. Z góry dziękuję.

Możesz po prostu symulować iloczyn macierzowo-matrycowy, tworząc iloczyn dwóch wzorców sparsity - tzn. Wziąłeś pod uwagę wzór sparsity (który jest przechowywany w oddzielnych tablicach w formacie CSR) jako matrycę zawierającą zero lub jeden w każdy wpis. Wykonanie tego symulowanego produktu wymaga jedynie utworzenia ioperacja na tych zerach i zerach, a zatem jest znacznie szybsza niż rzeczywisty produkt macierz-macierz - w rzeczywistości wszystko, co musisz zrobić, to przejść przez rzędy i kolumny dwóch macierzy i sprawdzić, czy jest co najmniej jeden wpis w wiersz i kolumna, którą mnożymy, gdzie obie macierze są niezerowe. Jest to tania operacja - w każdym razie znacznie tańsza niż faktyczne mnożenie liczb zmiennoprzecinkowych w rzeczywistym produkcie, co wymaga nie tylko wykonywania arytmetyki zmiennoprzecinkowej (kosztowne), ale także odczytywania rzeczywistych liczb zmiennoprzecinkowych z pamięci ( nawet droższe, ale nie potrzebujesz tego przy pomnażaniu wzorca rzadkości, ponieważ niezerowe wartości macierzy są przechowywane osobno w CSR).

Właściwie napisałem oryginalny kod w Matlabie dla A * B, zarówno A, jak i B rzadki. Wstępne przydzielenie miejsca na wynik było rzeczywiście interesującą częścią. Zauważyliśmy to, na co wskazuje Godric - że znajomość liczby niezerowych w AB jest tak samo kosztowna jak obliczanie AB.

Pierwszą implementację rzadkiego Matlaba wykonaliśmy około 1990 r., Zanim opublikowano artykuł Edith Cohen, który dał pierwszy praktyczny, szybki sposób na dokładne oszacowanie wielkości AB. Zebraliśmy mniejszy estymator wielkości i jeśli zabraknie miejsca w połowie obliczeń, podwoimy alokację i skopiujemy częściowo obliczony wynik.

Nie wiem, co jest teraz w Matlabie.

Inną możliwością byłoby obliczenie AB jednej kolumny na raz. Każda kolumna może być tymczasowo przechowywana w rzadkim akumulatorze (wyjaśnienie ich znajduje się w rzadkim dokumencie Matlab), a miejsce przydzielone do przechowywania dokładnie znanego rozmiaru kolumny wynikowej. Wynik byłby w rozproszonej skompresowanej rzadkiej formie kolumny - każda kolumna w CSC, ale bez ciągłości międzykolumnowej - przy użyciu 2 wektorów numcoli długości (początek kolumny, długość kolumny) zamiast jednego jako metadanych. Jest to forma przechowywania, która może być warta obejrzenia; ma inną siłę - możesz wyhodować kolumnę bez ponownego przydziału całej matrycy.

W tym artykule opisano algorytm przybliżania wielkości wypadkowej z iloczynu macierzy dwóch rzadkich macierzy.

Problem ze znalezieniem dokładnej liczby niezerowych wpisów w rzadkim mnożeniu macierzy polega na tym, że każdy wynikowy wynik zależy od interakcji dwóch wektorów, z których oba prawdopodobnie zawierają co najmniej kilka niezerowych elementów. Dlatego, aby obliczyć liczbę, musisz ocenić operacje logiczne na parze wektorów dla każdego elementu w wyniku. Problem polega na tym, że wymaga wielu operacji podobnych do liczby operacji potrzebnych do obliczenia samego produktu macierzowego. W moich komentarzach wspomniałem o możliwości wykorzystania niektórych struktur w niezerowych elementach pierwotnych macierzy, jednak te same exploity mogłyby zostać wykorzystane do zmniejszenia pracy wykonanej również przy mnożeniu macierzy.

Lepiej byłoby użyć powyższego papieru do przeszacowania wymagań pamięci, wykonać pomnożenie, a następnie skrócić przydzieloną pamięć lub przenieść uzyskaną macierz do tablicy o odpowiednio większym rozmiarze. Ponadto rzadkie produkty matrycowe nie są rzadkim zjawiskiem i prawie gwarantowałbym, że problem ten został już wcześniej rozwiązany. Trochę zagłębiając się w niektóre biblioteki bibliotek macierzowych typu open source powinny prowadzić do algorytmów używanych do wstępnego przydzielania pamięci.

Czy w przypadku CSR lub CSC masz gwarancję, że tablica elementów macierzy nie ma już zer? W takim przypadku łatwo jest dowiedzieć się, ile jest elementów niezerowych, używając czegoś podobnego do:

int nnz = sizeof(My_Array)/sizeof(long int);

Jeśli jednak tak nie jest (wydaje się to zbyt łatwe), możesz spróbować zmniejszyć . Jeśli tablica elementów macierzy jest bardzo duża, może to być najbardziej efektywny sposób obliczenia liczby elementów niezerowych. Wiele równoległych bibliotek C / C ++, takich jak Thrust (biblioteka CUDA) lub OpenCL (do których nie potrzebujesz GPU), obsługuje redukcje warunkowe - dla każdego elementu dodaj wynik Condition(Element). Jeśli ustawisz warunek na Element != 0to, zsumujesz liczbę niezerowych elementów. Możesz także usunąć elementy o zerowej wartości z tablicy elementów, tablicy wskaźników wierszy / kolumn i dostosować wskaźniki kolumn / wierszy.

Najprostszym sposobem na wdrożenie CSR jest wypróbowanie

std::vector< std::map<int, complex<float>> > 

reprezentować macierz. W takim przypadku tak naprawdę nie będziesz się martwić liczbą niezerowych elementów, wszystko jest dostępne za pośrednictwem

std::map< int, complex<float> >::iterator

w każdym rzędzie. Najlepsza ..