Zautomatyzowana optymalizacja mnożenia wektora macierzy 0-1


22

Pytanie:

Czy istnieje ustalona procedura lub teoria generowania kodu, która skutecznie stosuje mnożenie macierzy-wektora, gdy matryca jest gęsta i wypełniona tylko zerami i zerami? Najlepiej byłoby, gdyby zoptymalizowany kod systematycznie wykorzystywał wcześniej obliczone informacje w celu ograniczenia powielania pracy.

Innymi słowy, mam macierz M i chcę wykonać pewne wstępne obliczenia na podstawie , które sprawią, że obliczenie będzie możliwie najbardziej wydajne, gdy później otrzymam wektor .MMvv

przeciwkoM jest prostokątną gęstą macierzą binarną znaną w „czasie kompilacji”, natomiast jest nieznanym wektorem rzeczywistym znanym tylko w „czasie wykonywania”.v

Przykład 1: (okno przesuwne)

Pozwól, że użyję łatwego, małego przykładu, aby zilustrować mój punkt widzenia. Rozważmy macierz, Załóżmy, że zastosujemy tę macierz do wektora aby uzyskać . Następnie wpisy wyniku to:

M=[11111111111111111111].
vw=Mv
w1=v1+v2+v3+v4+v5w2=v2+v3+v4+v5+v6w3=v3+v4+v5+v6+v7w4=v4+v5+v6+v7+v8

Wykonanie standardowego mnożenia macierzy i wektora spowoduje obliczenie dokładnie w ten sposób. Jednak wiele z tych prac jest zbędnych. Możemy wykonać to samo obliczenie macierzy przy mniejszym koszcie, śledząc „sumę bieżącą” i dodając / odejmując, aby uzyskać następną liczbę:

w1=v1+v2+v3+v4+v5w2=w1+v6v1w3=w2+v7v2w4=w3+v8v3

Przykład 2: (struktura hierarchiczna)

W poprzednim przykładzie możemy po prostu śledzić bieżącą sumę. Jednak zwykle trzeba stworzyć i przechowywać drzewo wyników pośrednich. Na przykład rozważmy Można efektywnie obliczyć przy użyciu drzewa wyników pośrednich:

M=[111111111111111111111111]
w=Mv
  1. Oblicz i i dodaj je, aby uzyskać .w5w7w3
  2. Oblicz i i dodaj je, aby otrzymać .w4w6w2
  3. Dodaj i aby uzyskaćw 3 w 1w2w3w1

Struktura w powyższych przykładach jest łatwa do zauważenia, ale w przypadku rzeczywistych macierzy, którymi jestem zainteresowany, struktura nie jest taka prosta.

Przykład 3: (niska ranga)

Aby wyjaśnić pewne zamieszanie, matryce na ogół nie są rzadkie. W szczególności metoda rozwiązująca ten problem musi być w stanie znaleźć wydajne metody stosowania macierzy, w których duże bloki są wypełnione jednymi. Rozważmy na przykład

M=[111111111111111111111111].

Macierz ta może być rozłożona jako różnica dwóch macierzy rangi 1,

M=[111111111111111111111111111111][111111]

więc jego działanie na wektorze można efektywnie obliczyć, w 1w:=Mv

w1=v1+v2+v3+v4+v5+v6w2=w1w3=w2v5v6w4=w3w5=w4.

Motywacja:

Pracuję nad metodą numeryczną do przetwarzania obrazów i istnieje kilka dużych gęstych matryc o różnych strukturach, które są ustalone na zawsze. Później te macierze będą musiały zostać zastosowane do wielu nieznanych wektorów które będą zależeć od danych wejściowych użytkownika. W tej chwili używam ołówka i papieru, aby wymyślić skuteczny kod dla każdej matrycy, ale zastanawiam się, czy proces można zautomatyzować.v i01vi

Edycja: (postscript)

Wszystkie dotychczasowe odpowiedzi (z 15 września 2015 r.) Są interesujące, ale żadna z nich nie odpowiada tak zadowalająco, jak się spodziewałem. Prawdopodobnie okazuje się, że jest to trudne pytanie badawcze i nikt nie zna dobrej odpowiedzi.

Od upływu czasu nagradzam nagrodę za odpowiedź EvilJS, ponieważ odpowiada ona na właściwe pytanie. Chciałbym jednak, aby odpowiedź zawierała bardziej jasne i szczegółowe wyjaśnienia.

Odpowiedź tranisstora tworzy związek między tym pytaniem a problemem Online Moolean Matrix-Vector Multiplication (OMv), ale związek nie jest dokładnie tym, o co pyta to pytanie. W szczególności poniższe założenie nie pasuje (moje śmiałe podkreślenie),

Załóżmy teraz, że dla wszystkich i wszystkich macierzy n × n M nn0n×nMA n , M v M v O ( n 2 - ε ) ε > 0 znamy algorytm , że dla wszystkich wektorów oblicza w czasie naprawdę subkwadratowym, tj. W czasie dla niektórych .An,MvMvO(n2ε)ε>0

To, czy istnieją algorytmy subkwadratowe dla wszystkich macierzy, jest ortogonalne wobec pytania o znalezienie algorytmu dla konkretnej macierzy, który jest tak szybki, jak to możliwe. Większość matryc 0-1 wygląda jak losowy szum i (jeśli miałbym zgadywać) prawdopodobnie nie ma algorytmów subkwadratowych. Jednak fakt, że istnieją naprawdę złe matryce, nie przeszkadza mi w znalezieniu szybkiego algorytmu na dobrej matrycy, na przykład macierzy „przesuwanego okna”.

Odpowiedzi vzn, pierwsza odpowiedź , druga odpowiedź są interesujące (i moim zdaniem nie zasługują na tak wiele ocen), ale nie odnoszą się do pytania z powodów omówionych w komentarzach tam.


1
Jeśli macierz ma taką postać, TDMA to macierz pasmowa, algorytm Thomasa. Jeszcze 0-1, ale ta funkcja powinna zostać wykorzystana.
Zły

@EvilJS matryca jest po prostu pasmowana dla konkretnego przykładu. Zasadniczo nie będzie pasmowane. Dodałem kolejny przykład, który nie jest związany.
Nick Alger

Masz wiele stałych macierzy N x M, które są wektorami binarnymi, rzeczywistymi i chcesz wstępnie obliczyć optymalną ścieżkę wykonania na etapie przetwarzania wstępnego dla każdej instancji? Wynikiem takiej operacji jest kod z zakodowanymi operacjami na matrycę i czy chcesz to zrobić? Przez instancję mam na myśli macierz. Tylko sprawdzam.
Zło

@EvilJS To pytanie dotyczy sytuacji, w której istnieje jedna znana macierz binarna , która zostanie później zastosowana do wielu nieznanych wektorów rzeczywistych . Opierając się tylko na , chcemy wstępnie obliczyć kod, który zastosuje tak skutecznie, jak to możliwe, aby później, gdy otrzymamy , moglibyśmy obliczyć tak szybko, jak to możliwe. W konkretnej aplikacji, która motywuje to pytanie, mam garść macierzy binarnych takich jak ta (w rzeczywistości 12), które są ustalone na zawsze, podczas gdy wektory są nieprzewidywalne i zależą od danych wejściowych użytkownika programu. v i M M v i M v i v iMviMMviMvivi
Nick Alger,

1
Na polu dwóch elementów problem obliczenia minimalnego obwodu bramki XOR, który symuluje daną transformację liniową, jest trudny NP. Zobacz cstheory.stackexchange.com/a/32272/225
Ryan Williams

Odpowiedzi:


5

Jeśli to możliwe, spróbuj wykorzystać pasmową trójosiową naturę matrycy.
W przeciwnym razie, jeśli matryca zawiera tylko stałą liczbę różnych wartości (co z pewnością jest binarne), powinieneś wypróbować algorytm Mailmana (autor: Edo Liberty, Steven W. Zucker W raporcie technicznym uniwersytetu Yale nr 1402): zoptymalizowany w stosunku do skończonego słownika
Wspólna eliminacja podwyrażeń jest znana od pewnego czasu, jak wielokrotne stałe zwielokrotnianie, ale zejście do poziomu bramki jest opcją - stosowane tutaj wzorce mogą być użyte osobno jako rozwiązanie lub połączone z innymi metodami, artykuł na ten temat „Poprawianie wspólnej eliminacji podwyrażeń” Algorytm z nową metodą obliczania opóźnienia na poziomie bramy ”autorstwa Ning Wu, Xiaoqiang Zhanga, Yunfei Ye i Lidonga Lan opublikowanych w„ Proceedings of the World Congress on Engineering and Computer Science 2013 Vol II WCECS 2013, 23–25 października 2013 r., San Francisco, USA „ Poziom bramy CSE

Istnieje również prymitywna, ale działająca metoda, aby wygenerować macierz symboliczną ze stałymi, wektor ze zmiennymi i podłączyć go do statycznego pojedynczego przypisania (SSA) z kompilatorów, który automatyzuje proces ręcznego pisania macierzy.

nowy prototyp algorytmu
Co zrobiłeś z sumą bieżącą: Daje 10 operacji i przy moim początkowym pomyśle korzystania z Thomasa jest to równoważne. Na razie piszę i testuję nowy algorytm, również środowiska wykonawcze są nieprzyjemne , ale pierwszy wynik testu dał mi zaskakującą odpowiedź:

w1=v1+v2+v3+v4+v5w2=w1+v6v1w3=w2+v7v2w4=w3+v8v3


tmp1=v2+v3+v4+v5w1=v1+tmp1w2=tmp1+v6w3=w2+v7v2w4=w3+v8v3

Który daje 9 operacji , definiując je jako + lub - wynosi 1, a = wynosi 0.

w1=v1+v2+v3+v4+v5+v6w2=w1w3=w2v5v6w4=w3w5=w4.

Daje to 7 operacji , wynik mojego algorytmu dał: Co daje 6 operacji Na razie mogę powiedzieć, że używam odległości Hamminga, i | operacje bitowe, liczenie zastosowań i tworzenie czegoś takiego jak Cocke – Younger – Kasami (CYK) - „algorytm analizujący dla gramatyki bezkontekstowej, nazwany na cześć jego wynalazców, Johna Cocke'a, Daniela Youngera i Tadao Kasami. Wykorzystuje oddolną analizę i dynamikę programowanie." - z Wikipedii To ta sama technika, której używam do budowania bloków zmiennych.

tmp1=v1+v2+v3+v4tmp2=v5+v6w1=tmp1+tmp2w2=w1w3=w2tmp2w4=w3w5=w4.


(re rev5) proszę podać „wiecznie zieloną metodę”. co to jest SSA? Algorytm dynamiczny CYK?
vzn

Przyznałem nagrodę za tę odpowiedź i wyjaśniłem, dlaczego w edycji mojego pierwotnego pytania.
Nick Alger,

8

Jest to związane z otwartym pytaniem badawczym, znanym jako „problem online mnożenia macierzy i wektorów (OMv)”. Problem ten brzmi następująco (patrz [1]): Biorąc pod uwagę binarną macierz M i n binarnych wektorów kolumn v 1 , , v n , musimy obliczyć M v i zanim nadejdzie v i + 1 .n×nMnv1,,vnMvivi+1

Zauważ, że problem z pytania jest nieco bardziej ogólny: pozwala na macierze i wektory o wartościach rzeczywistych. Zauważ, że problem z macierzami n × n i wektorami boolowskimi jest „łatwiejszy”, ponieważ stanowi szczególny przypadek.m×nn×n

Najwyraźniej naiwny algorytm dla Online Boolean Matrix-Vector Multiplication (który wykorzystuje tylko standardowe mnożenie macierzy-wektorów) zajmuje czas . Istnieje przypuszczenie (patrz np. [1]), że nie można tego zrobić naprawdę szybciej niż O ( n 3 ) . (Bardziej szczegółowo, ta hipoteza wygląda następująco: Nie istnieje tak naprawdę podklubowy algorytm, który rozwiązuje Online Mnożenie Boolean Matrix-Vector Multiplication, tj. Nie ma algorytmu z czasem działania O ( n 3 - ε ) dla ε > 0 ).O(n3)O(n3)O(n3ε)ε>0

Wiadomo, że algorytm Williamsa rozwiązuje ten problem w czasie . Więcej informacji znajduje się w [2].O(n3/log2n)

Byłby to przełom w dziedzinie warunkowych dolnych granic, gdyby można było udowodnić lub obalić powyższą hipotezę.

[1] Ujednolicanie i wzmacnianie twardości dla problemów dynamicznych za pomocą internetowego przypuszczenia mnożenia macierzy i wektorów. autorzy: Henzinger, Krinninger, Nanongkai i Saranurak
[ http://eprints.cs.univie.ac.at/4351/1/OMv_conjecture.pdf ]

[2] Mnożenie wektora macierzowego w czasie subkwadratowym: (wymagane jest wstępne przetwarzanie). autor: Williams
[ http://dl.acm.org/citation.cfm?id=1283383.1283490 ]

Aktualizacja

Jedno z pytań w komentarzach było następujące: Znamy w czasie kompilacji. Czy nie możemy dostosować naszego algorytmu do M , aby problem OMv (przypuszczenie) nie miał zastosowania? Przekonamy się, że tak nie jest, chyba że hipoteza OMv zawiedzie.MM

Pomysł dowodowy jest prosty: Załóżmy, że możemy podać szybkie algorytmy dla wszystkich macierzy do pewnego określonego rozmiaru (np. Rozróżnienie wszystkich możliwych przypadków). Po tym pewnym rozmiarze używamy podziału i podboju.

Oto szczegóły:
Napraw niektóre , które (bez utraty ogólności) są potęgą 2 i większą niż 2. Teraz załóżmy, że dla wszystkich n n 0 i wszystkich n × n macierzy M znamy algorytm A n , M , że dla wszystkich wektorów v oblicza M v w czasie naprawdę subkwadratowym, tj. w czasie O ( n 2 - ε ) dla niektórych ε > 0n0Nnn0n×nMAn,MvMvO(n2ε)ε>0. (Zauważ, że pozwala to na indywidualny algorytm dla każdej matrycy do rozmiaru )n0×n0

Teraz rozwiążemy OMv w naprawdę podokubicim czasie:
Biorąc pod uwagę macierz binarną o rozmiarze n × n , gdzie n = 2 k dla niektórych k i n > n 0 , stosujemy strategię dziel i zwyciężaj. Dzielimy M na cztery podmaciesze M 1 , M 2 , M 3 , M 4 o rozmiarach 2 k - 1 × 2 k - 1 . Jeśli 2 k - 1Mn×nn=2kkn>n0MM1,M2,M3,M42k1×2k1 , następnie używamy algorytmu A 2 k - 1 , M i , w przeciwnym razie powracamy. (Ponieważ n 0 to pewna stała liczba, możemy wybrać prawidłowy algorytm w stałym czasie).2k1n0A2k1,Min0

Zauważ, że będziemy potrzebować co najwyżej kroków rekurencji. Również dla n wektorów v 1 , , v n , będziemy n obliczeń. Zatem do przetworzenia wszystkich multiplikacji macierz-wektor potrzebujemy całkowitego czasu obliczeń O ( n 3 - ε log n ) .O(logn)nv1,,vnnO(n3εlogn)

Dobrze wiadomo, że logarytm rośnie wolniej niż jakikolwiek wielomian (w szczególności wolniej niż jakikolwiek pierwiastek). Naprawiając niektóre pomocą ˜ ε < ε , widzimy, że nasze całkowite obliczenia działają w czasie naprawdę subububowym (w szczególności w czasie O ( n 3 - ˜ ε ) ). Zatem przypuszczenie OMv byłoby błędne.ε~>0ε~<εO(n3ε~)

(Jeśli ma rozmiar m × n oraz m i n nie są potęgami 2, wówczas nadal obowiązują granice czasów pracy, ponieważ możemy po prostu zwiększyć n i m do następnych potęg 2).Mm×nmnnm

Wniosek: Jeśli możesz użyć rozróżnienia wielkości liter na macierzach wejściowych w celu uzyskania szybkich algorytmów, możesz poprawić hipotezę OMv.


Jak wskazali autor i vzn, tak nie jest, wektor nie jest binarny, matryca nie jest konieczna N x N, a autor chce wstępnie obliczyć operacje i nie ma potrzeby przetwarzania online. Oparte na domysłach nie wystarczy. Oba dokumenty nie mają znaczenia dla pytania. W tym przypadku chodzi o wstępne obliczenie stałej macierzy w celu zapewnienia minimalnej liczby operacji. Możliwe będą różne podejścia do pełnych, pasmowych, symetrycznych przypadków.
Zło

@EvilJS: Jeśli dopuścisz dowolną macierz M x N i wektory o wartościach rzeczywistych, problem stanie się trudniejszy niż ten, który podałem w odpowiedzi (tj. Online Boolean Matrix-Vector Multiplication będzie szczególnym przypadkiem). Gdybyś mógł naprawdę rozwiązać bardziej ogólny problem naprawdę szybciej niż O (n ^ 3), poprawiłbyś również przypuszczenie (co byłoby dobrą wiadomością!). Ponadto autor w komentarzu do pytania, że ​​wektory są początkowo nieznane. Jeśli wcześniej znasz wszystkie wektory, możesz po prostu użyć szybkiego mnożenia macierzy (np. Wersja algorytmu Strassena).
tranisstor

Właśnie wskazałem autorom przypadek „prawdziwy wektor”. Spójrz na macierz Thomasa - tylko specjalny przypadek macierzy w O (n). Nie sugeruję ogólnego przypadku. A jeśli macierz jest stała, a wektory są znane, odpowiedź kodem stałym nie implementuje Strassena; (
Evil

@EvilJS: Nie jestem pewien, czy całkowicie rozumiem, co próbujesz powiedzieć. Oczywiście w przypadku specjalnych typów matryc, takich jak macierz Thomasa, można uzyskać znaczne przyspieszenie, ale ogólnie jest to trudniejsze. Może powinienem również wskazać, że problem, który wprowadziłem, uwzględnia etap wstępnego przetwarzania (zanim pojawi się jakikolwiek wektor). Jeśli możesz mi powiedzieć, jak systematycznie „na stałe kodować” swój algorytm dla dowolnej matrycy, którą ci podam, możesz także ulepszyć hipotezę (ponieważ możesz zaimplementować ten etap twardego kodowania jako etap wstępnego przetwarzania algorytmu).
tranisstor

zgodził się, że to działa; jednak wydaje się, że drugi odnośnik autorstwa Williamsa nie uwzględnia w szczególności macierzy binarnych. fyi ma tu
dniu

-2

jest to zasadniczo CS na poziomie badawczym, problem badany jest w co najmniej dwóch postaciach, jednym z mnożenia rzadkich macierzy (przykładowo przytoczona praca), a także badany jest szczególny przypadek „binarnych rzadkich macierzy”. W 2 nd przypadek jest znany być związane z optymalizacją programów liniową. minimalne programy mogą być również podobne do DAG z dwoma rodzajami „bramek”, dodawania i mnożenia, więc niektóre literatury minimalizacji obwodów mogą się z tym łączyć i być może oprogramowanie „z półki” może być dostosowane do tego celu. tutaj jest odniesienie do drugiego przypadku, a także to samo pytanie o cstheory z pewnymi podstawowymi wstępnymi badaniami empirycznymi.


1
O(n)O(n2)

referencje są włączone, jak wskazują tytuły, rzadkie macierze . może masz inną definicję niż w dokumentach? jeśli jesteś wrażliwy na dokładną definicję rzadkości (większość jest z grubsza skorelowana / prawie wymienna), należy to podać w pytaniu.
vzn

1
Matryce, które mnie interesują, to gęste matryce. Nawiasem mówiąc, choć nie sądzę, aby to w pełni odnosiło się do mojego pytania, doceniam odpowiedź.
Nick Alger,

ok przepraszam! pomylił się, nie zdawałem sobie sprawy z dokładnego pytania. pobieżnie wyglądam, twój przykład # 2 ma mniej niż ½ wypełnienia i wyglądał na „rzadki” dla mnie i doszedł do wniosku, że niektóre z tych rzadkich teorii byłyby co najmniej w pewnym stopniu przydatne. w zasadzie im bardziej gęsta matryca, tym mniej operacji można zoptymalizować, więc prawdopodobnie większość teorii na temat tego rodzaju optymalizacji jest zorientowana na rzadkie macierze.
vzn

-3

nie jestem pewien, czy problem ten został dokładnie zbadany, ale te badania są powiązane i wydają się rozsądnym początkiem / początkiem. patrzy na rozkład hipergraphowy dla rzadkiego mnożenia macierzy. macierze binarne są szczególnym przypadkiem tego podejścia. takie podejście znajdzie bardziej optymalne strategie niż „prosta” metoda mnożenia. dalsze optymalizacje (w tym zakresie) mogą być możliwe na podstawie właściwości macierzy binarnej.


2
Nie rozumiem, co to ma wspólnego z pytaniem. Ten artykuł dotyczy dzielenia mnożenia macierzy na system rozproszony w celu obliczeń równoległych, aby zminimalizować ilość komunikacji między procesorami. Co to ma wspólnego z tym pytaniem? Pytanie wydaje się nie wspominać o obliczeniach równoległych lub komunikacji między procesorami. Zachęcam do edycji odpowiedzi, aby połączenie było bardziej wyraźne.
DW

afaik ma ten sam problem i minimalizacja obliczeń równoległych minimalizuje również implementację tych samych obliczeń przez pojedynczy procesor. pytający przynajmniej nie wykluczył realizacji równoległych.
vzn

1
Dziękuję za link. Jednak jestem sceptyczny wobec metody tego problemu, ponieważ nie wykorzystuje ona faktu, że wpisy macierzy zawierają tylko zera i jedynki, podczas gdy ta właściwość jest, o ile wiem, bardzo ważna. Na przykład algorytm „działającej sumy” w pierwszym przykładzie będzie działał tylko wtedy, gdy wszystkie niezerowe wpisy w danej kolumnie macierzy mają tę samą wartość.
Nick Alger

NA twoja obserwacja / sprzeciw jest uwzględniony w odpowiedzi. dalsza optymalizacja jest prawdopodobnie możliwa przy użyciu właściwości 0/1; metoda ta wydaje się minimalizować całkowitą liczbę operacji dodawania / mnożenia pod pozorem równoległości. operacje dodawania / mnożenia można również postrzegać jako „bramki” w DAG, a technika minimalizuje bramki. znaczna złożoność pracy ujawnia niektóre głębsze / istotne złożoności tego procesu optymalizacji. jak podano, odpowiedź nie ma na celu rozstrzygnięcia tego trudnego problemu, a jedynie „lepsze niż nic”.
vzn
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.