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 . $M$ $Mv$ $v$

$M$ 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 = [\begin{matrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{matrix}] .

$M = \begin{bmatrix}1 & 1 & 1 & 1 & 1\\ & 1 & 1 & 1 & 1 & 1 \\ & & 1 & 1 & 1 & 1 & 1\\ & & & 1 & 1 & 1 & 1 & 1\end{bmatrix}.$

v

$v$

w = M v

$w = Mv$

\begin{aligned} w_{1} & = v_{1} + v_{2} + v_{3} + v_{4} + v_{5} \\ w_{2} & = v_{2} + v_{3} + v_{4} + v_{5} + v_{6} \\ w_{3} & = v_{3} + v_{4} + v_{5} + v_{6} + v_{7} \\ w_{4} & = v_{4} + v_{5} + v_{6} + v_{7} + v_{8} \end{aligned}

$\begin{align} w_1 &= v_1 + v_2 + v_3 + v_4 + v_5\\ w_2 &= v_2 + v_3 + v_4 + v_5 + v_6\\ w_3 &= v_3 + v_4 + v_5 + v_6 + v_7\\ w_4 &= v_4 + v_5 + v_6 + v_7 + v_8 \end{align}$

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

\begin{aligned} w_{1} & = v_{1} + v_{2} + v_{3} + v_{4} + v_{5} \\ w_{2} & = w_{1} + v_{6} - v_{1} \\ w_{3} & = w_{2} + v_{7} - v_{2} \\ w_{4} & = w_{3} + v_{8} - v_{3} \end{aligned}

$\begin{align} w_1 &= v_1 + v_2 + v_3 + v_4 + v_5\\ w_2 &= w_1 + v_6 - v_1\\ w_3 &= w_2 + v_7 - v_2\\ w_4 &= w_3 + v_8 - v_3 \end{align}$

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 = [\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 \\ 1 & 1 \\ 1 & 1 \\ 1 & 1 \end{matrix}]

$M = \begin{bmatrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 \\ & & & & 1 & 1 & 1 & 1\\ 1 & 1 \\ & & & & 1 & 1 \\ & & 1 & 1 \\ & & & & & & 1 & 1\end{bmatrix}$

w = M v

$w = Mv$

Oblicz i i dodaj je, aby uzyskać . $w_5$ $w_7$ $w_3$
Oblicz i i dodaj je, aby otrzymać . $w_4$ $w_6$ $w_2$
Dodaj i aby uzyskać $w_2$ $w_3$ $w_1$

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 = [\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix}] .

$M = \begin{bmatrix}1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & & \\ 1 & 1 & 1 & 1 & & \\ 1 & 1 & 1 & 1 & & \end{bmatrix}.$

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

M = [\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \end{matrix}] - [\begin{matrix} 1 & 1 \\ 1 & 1 \\ 1 & 1 \end{matrix}]

$M = \begin{bmatrix}1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1\end{bmatrix} - \begin{bmatrix}& & & & & \\ & & & & & \\ & & & & 1 & 1 \\ & & & & 1 & 1 \\ & & & & 1 & 1\end{bmatrix}$

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

\begin{aligned} w_{1} & = v_{1} + v_{2} + v_{3} + v_{4} + v_{5} + v_{6} \\ w_{2} & = w_{1} \\ w_{3} & = w_{2} - v_{5} - v_{6} \\ w_{4} & = w_{3} \\ w_{5} & = w_{4} . \end{aligned}

$\begin{align} w_1 &= v_1 + v_2 + v_3 + v_4 + v_5 + v_6 \\ w_2 &= w_1 \\ w_3 &= w_2 - v_5 - v_6 \\ w_4 &= w_3 \\ w_5 &= w_4. \end{align}$

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ć. $0-1$ $v_i$

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 \leq n_0$ $n \times n$ $M$ znamy algorytm , że dla wszystkich wektorów oblicza w czasie naprawdę subkwadratowym, tj. W czasie dla niektórych . $A_{n,M}$ $v$ $Mv$ $O(n^{2 - \varepsilon})$ $\varepsilon > 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.

linear-algebra matrices program-optimization

— Nick Alger
źródło

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.

M

$M$

v_{i}

$v_i$

M

$M$

M

$M$

v_{i}

$v_i$

M v_{i}

$M v_i$

v_{i}

$v_i$

— 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

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ź:

\begin{aligned} w_{1} & = v_{1} + v_{2} + v_{3} + v_{4} + v_{5} \\ w_{2} & = w_{1} + v_{6} - v_{1} \\ w_{3} & = w_{2} + v_{7} - v_{2} \\ w_{4} & = w_{3} + v_{8} - v_{3} \end{aligned}

$\begin{align} w_1 &= v_1 + v_2 + v_3 + v_4 + v_5 \\ w_2 &= w_1 + v_6 - v_1 \\ w_3 &= w_2 + v_7 - v_2 \\ w_4 &= w_3 + v_8 - v_3 \end{align}$

\begin{aligned} t m p_{1} & = v_{2} + v_{3} + v_{4} + v_{5} \\ w_{1} & = v_{1} + t m p_{1} \\ w_{2} & = t m p_{1} + v_{6} \\ w_{3} & = w_{2} + v_{7} - v_{2} \\ w_{4} & = w_{3} + v_{8} - v_{3} \end{aligned}

$\begin{align} tmp_1 &= v_2 + v_3 + v_4 + v_5 \\ w_1 &= v_1 + tmp_1 \\ w_2 &= tmp_1 + v_6 \\ w_3 &= w_2 + v_7 - v_2 \\ w_4 &= w_3 + v_8 - v_3 \end{align}$
Który daje 9 operacji , definiując je jako + lub - wynosi 1, a = wynosi 0.

\begin{aligned} w_{1} & = v_{1} + v_{2} + v_{3} + v_{4} + v_{5} + v_{6} \\ w_{2} & = w_{1} \\ w_{3} & = w_{2} - v_{5} - v_{6} \\ w_{4} & = w_{3} \\ w_{5} & = w_{4} . \end{aligned}

$\begin{align} w_1 &= v_1 + v_2 + v_3 + v_4 + v_5 + v_6 \\ w_2 &= w_1 \\ w_3 &= w_2 - v_5 - v_6 \\ w_4 &= w_3 \\ w_5 &= w_4. \end{align}$

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.

\begin{aligned} t m p_{1} & = v_{1} + v_{2} + v_{3} + v_{4} \\ t m p_{2} & = v_{5} + v_{6} \\ w_{1} & = t m p_{1} + t m p_{2} \\ w_{2} & = w_{1} \\ w_{3} & = w_{2} - t m p_{2} \\ w_{4} & = w_{3} \\ w_{5} & = w_{4} . \end{aligned}

$\begin{align} tmp_1 &= v_1 + v_2 + v_3 + v_4 \\ tmp_2 &= v_5 + v_6 \\ w_1 &= tmp_1 + tmp_2 \\ w_2 &= w_1 \\ w_3 &= w_2 - tmp_2 \\ w_4 &= w_3 \\ w_5 &= w_4. \end{align}$

— Zło
źródło

(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 i binarnych wektorów kolumn , musimy obliczyć zanim nadejdzie . $n \times n$ $M$ $n$ $v_1, \dots, v_n$ $M v_i$ $v_{i+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 i wektorami boolowskimi jest „łatwiejszy”, ponieważ stanowi szczególny przypadek. $m \times n$ $n \times 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ż . (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 dla ). $O(n^3)$ $O(n^3)$ $O(n^{3 - \varepsilon})$ $\varepsilon > 0$

Wiadomo, że algorytm Williamsa rozwiązuje ten problem w czasie . Więcej informacji znajduje się w [2]. $O(n^3 / \log^2 n)$

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 , aby problem OMv (przypuszczenie) nie miał zastosowania? Przekonamy się, że tak nie jest, chyba że hipoteza OMv zawiedzie. $M$ $M$

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 i wszystkich macierzy znamy algorytm , że dla wszystkich wektorów oblicza w czasie naprawdę subkwadratowym, tj. w czasie dla niektórych $n_0 \in \mathbb{N}$ $n \leq n_0$ $n \times n$ $M$ $A_{n,M}$ $v$ $Mv$ $O(n^{2 - \varepsilon})$ $\varepsilon > 0$ . (Zauważ, że pozwala to na indywidualny algorytm dla każdej matrycy do rozmiaru ) $n_0 \times n_0$

Teraz rozwiążemy OMv w naprawdę podokubicim czasie:
Biorąc pod uwagę macierz binarną o rozmiarze , gdzie dla niektórych i , stosujemy strategię dziel i zwyciężaj. Dzielimy na cztery podmaciesze o rozmiarach . Jeśli $M$ $n \times n$ $n = 2^k$ $k$ $n > n_0$ $M$ $M_1, M_2, M_3, M_4$ $2^{k-1} \times 2^{k-1}$ , następnie używamy algorytmu , w przeciwnym razie powracamy. (Ponieważ to pewna stała liczba, możemy wybrać prawidłowy algorytm w stałym czasie). $2^{k-1} \leq n_0$ $A_{2^{k-1},M_i}$ $n_0$

Zauważ, że będziemy potrzebować co najwyżej kroków rekurencji. Również dla wektorów , będziemy obliczeń. Zatem do przetworzenia wszystkich multiplikacji macierz-wektor potrzebujemy całkowitego czasu obliczeń . $O(\log n)$ $n$ $v_1, \dots, v_n$ $n$ $O(n^{3 - \varepsilon} \log n)$

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 ). Zatem przypuszczenie OMv byłoby błędne. $\tilde \varepsilon > 0$ $\tilde \varepsilon < \varepsilon$ $O(n^{3 - \tilde \varepsilon})$

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

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.

— tranisstor
źródło

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.

— vzn
źródło

1

O (n)

$O(n)$

O (n^{2})

$O(n^2)$

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.

Rozkład oparty na partycjonowaniu hypergraphowym dla równoległego mnożenia wektorów rzadkich macierzy / Umit Catalyurek i Cevdet Aykanat

— vzn
źródło

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