Najszybszy sposób na znalezienie par własnych małej macierzy niesymetrycznej na GPU we wspólnej pamięci

Mam problem, w którym muszę znaleźć wszystkie pozytywne (jak w wartości własnej dodatniej) pary własne małej (zwykle mniejszej niż 60 x 60) macierzy niesymetrycznej. Mogę przestać obliczać, kiedy wartość własna jest mniejsza niż pewien próg. Wiem, że wartości własne są prawdziwe. Jakieś sugestie dotyczące algorytmów, których mógłbym użyć, aby wycisnąć najlepszą wydajność? Muszę wykonać kilka tysięcy tych rozkładów, więc szybkość jest ważna.

Z góry dziękuję.

EDYCJA: Muszę to zrobić na GPU we wspólnej pamięci. Matryce również niekoniecznie mają taki sam rozmiar. W tej chwili nie znam żadnych bibliotek, które to robią. Docenione zostaną sugestie algorytmów, które dobrze pasowałyby do problemu.

performance eigensystem gpu Kantoku
źródło

Jeśli mam rację, masz jądro CUDA, które oblicza tysiące małych macierzy w pamięci współdzielonej i nie chcesz kopiować ich do pamięci globalnej. Przed próbą udzielenia odpowiedzi należy wyjaśnić kilka kwestii. W CUDA czas życia pamięci współdzielonej jest związany z czasem życia bloku: ile wątków masz dla każdej matrycy do rozkładu? Czy ekstremalna wydajność jest naprawdę ważna? (Jak przewidywane czasy ekstrakcji wartości własnych w porównaniu do czasów generowania macierzy?) Na podstawie jakiego argumentu wiesz, że system eigens jest prawdziwy? Czy system eigens może być wadliwy?

Stefano M

Cześć Stefano i dziękuję za komentarz. Na razie będę miał najbliższą wielokrotność rozmiaru osnowy do wymiaru matrycy, który chciałbym rozłożyć. Czasy generowania macierzy są bardzo różne i zdarzają się przypadki, w których czas generowania macierzy jest droższy, ale w wielu sytuacjach czas generowania macierzy jest krótszy niż rozkład. Wiem, że wartości własne są prawdziwe ze względu na sposób generowania macierzy. Wolałbym nie wchodzić w szczegóły tutaj, ponieważ umniejszyłoby to pierwotne pytanie. Wreszcie tak, system może być wadliwy.

Kantoku,

Odpowiedzi:

Bez częstych poszukiwań polecam zajrzeć do biblioteki MAGMA . Darmowy kod z ciągłym wsparciem. NVIDIA uznała MAGMA za „Przełom w rozwiązaniach dla problemów z wartością własną”.

Istnieje również biblioteka CULA , która jest ogólnie produktem komercyjnym, chociaż ostatnio została udostępniona bezpłatnie do użytku akademickiego (zobacz szczegóły tutaj ).

Alexander
źródło

Dziękuję za odpowiedź, Alexander. Przeglądałem już obie biblioteki i, o ile wiem, funkcje są wywoływane z hosta i pamięć musi znajdować się w pamięci globalnej. Uważam, że narzut byłby zbyt duży, aby uzasadnić użycie. Wszystkie te macierze są generowane we wspólnej pamięci, używane w jądrze, a następnie odrzucane. Chciałbym je tam zatrzymać bez konieczności ponownego wprowadzania ich do pamięci globalnej. Nawet gdybym je tam wypchnął, nadal byłby problem z wywoływaniem wielu funkcji jądra z hosta (choć w wielu strumieniach).

Kantoku,

@Kantoku, tak, te biblioteki są bardziej ogólne i przechowują całą macierz w pamięci globalnej. Jeśli twoje macierze znajdują się w pamięci współdzielonej, tylko jeden SM może na nich działać, prawda? Wdrożenie EVD powinno zatem być dość proste.

Alexander

Tak, wyobrażam to sobie, dlatego szukałem algorytmów odpowiednich dla danej sytuacji. Nie jestem zbyt obeznany z niesymetrycznym evd, więc szukałem sugestii.

Kantoku

@Kantoku (i Alexander). Niesymetryczne EVD są dalekie od prostoty, nawet w przypadku sekwencyjnym. Jest to nadal aktywny obszar badań.

Jack Poulson,

@JackPoulson Ach tak, masz rację, ale ja (i zakładam również, że Alexander) chciałem zastosować ustalony algorytm do problemu, biorąc pod uwagę wiele uproszczeń, które można wprowadzić, gdy weźmiemy pod uwagę wielkość i naturę rozważanej macierzy. Problem polega na tym: który algorytm.

Kantoku,

Używaj funkcji w LAPACK, jest mało prawdopodobne, że możesz je pokonać we własnej implementacji.

Wolfgang Bangerth
źródło

Cześć Wolfgang. Dzięki za odpowiedź, ale zamierzam to zaimplementować na GPU za pomocą CUDA i kilku tysięcy tych małych matryc (gdzie każdy blok obsługuje rozkład pojedynczej macierzy), a matryce niekoniecznie są tego samego rozmiaru, więc implementacja Wydaje mi się, że moim jedynym wyborem jest coś, co korzysta ze wspólnej pamięci. Wiesz, jaki algorytm najlepiej pasowałby do tego rodzaju matryc? PS Dzięki za ofertę. II wykłady, które wygłosiliście w KAUST w zeszłym semestrze. Podobało mi się :)

Kantoku

@Kantoku Powinieneś dodać te szczegóły w swoim pytaniu, w przeciwnym razie jest to mylące.

Alexander

@Alexander Zaktualizowałem pytanie o więcej szczegółów. Dzieki za sugestie!

Kantoku,

@Kantoku: GPU są trochę poza moim królestwem, ale jestem pewien, że istnieją już biblioteki, które robią to, co chcesz (i faktycznie widzę, że inne odpowiedzi już do nich prowadzą). Cieszę się, że lubisz moje zajęcia!

Wolfgang Bangerth,