Algorytm mnożenia wektora macierzy przy użyciu minimalnej liczby dodatków

10

Rozważ następujący problem:

Biorąc pod uwagę macierz , chcemy zoptymalizować liczbę dodatków w algorytmie mnożenia do obliczania . $M$ $v \mapsto Mv$

Uważam ten problem za interesujący ze względu na jego związek ze złożonością mnożenia macierzy (ten problem jest ograniczoną wersją mnożenia macierzy).

Co wiadomo o tym problemie?

Czy są jakieś interesujące wyniki wiążące ten problem ze złożonością problemu mnożenia macierzy?

Odpowiedź na problem wydaje się polegać na znalezieniu obwodów z dodatkowymi bramkami. Co jeśli pozwolimy odjąć bramki?

Szukam redukcji między tym problemem a innymi problemami.

Umotywowany

cc.complexity-theory reference-request circuit-complexity matrices arithmetic-circuits vzn
źródło

Jeśli jest macierzą 0-1, to znane dolne granice liczby dodatków zależą przede wszystkim od grupy, nad którą pracujemy. Jeśli pracujemy nad półgrupą lub nawet , wówczas granica Nechiporuka wraz ze znanymi konstrukcjami daje wyraźną dolną granicę około . Jeśli jednak jesteśmy w grupie , sytuacja jest raczej przygnębiająca: najsilniejsze znane dolne granice mają jedynie postać . Więcej można znaleźć tutaj .

M

$M$

n \times n

$n\times n$

(N, +)

$(N,+)$

({0, 1}, \lor)

$(\{0,1\},\lor)$

n^{2 - o (1)}

$n^{2-o(1)}$

(G F (2), +)

$(GF(2),+)$

ω (n)

$\omega(n)$

Stasys,

9

Zasadniczo jest to problem, który zmotywował Valiant do wprowadzenia sztywności macierzy do złożoności (o ile rozumiem historię).

Obwód liniowy to obwód algebraiczny, którego jedynymi bramkami są dwuwejściowe liniowe bramki kombinowane. Każda transformacja liniowa (macierz) może być obliczona za pomocą obwodu liniowego o kwadratowym rozmiarze, a pytanie brzmi, kiedy można lepiej. Wiadomo, że dla macierzy losowej nie da się znacznie lepiej.

Niektóre macierze - takie jak macierz transformacji Fouriera, macierz niskiej rangi lub macierz rzadka - można wykonać znacznie lepiej.

Wystarczająco sztywna matryca nie może być obliczona przez obwody liniowe, które są jednocześnie wielkością liniową i głębokością logarytmiczną (Valiant), ale do dziś nie są znane wyraźne macierze, dla których istnieje superliniowa dolna granica wielkości obwodów liniowych.

Nie przypominam sobie wyników, które mówią, że trudno jest obliczyć rozmiar najmniejszego obwodu liniowego dla danej macierzy, ale nie zdziwiłbym się, gdyby był to NP-trudny.

Joshua Grochow
źródło

3

To jest trudne NP, patrz cstheory.stackexchange.com/a/32272/225

Ryan Williams

7

Jeśli nie zezwalasz na odejmowanie, oznacza to, że jesteś w ustawieniach półgrupowych / monotonicznych i istnieją wąskie dolne granice znane z wielu naturalnych macierzy pochodzących z geometrii obliczeniowej. (Zainteresowanie geometrią obliczeniową polega na tym, że zliczanie zakresów można zakodować jako mnożenie macierzy-wektora). Na przykład znane są następujące dolne granice wielkości monotonicznych obwodów liniowych: $M$

$\Omega(n (\log n/\log \log n)^{d-1})$ dla padania matrycy pudeł osi wyrównany w wymiarach; $M$ $n\times n$ $d$
$\Omega(n^{4/3})$ dla an macierzy padania linii i punktów w wymiarach ; $M$ $n\times n$ $d$
$\tilde{\Omega}(n^{2-2/(d+1)})$ dla an macierzy przypadków uproszczeń w wymiarach . $M$ $n\times n$ $d$

Te granice są zasadniczo najlepsze z możliwych. Rozdział 6.3. w książce Chazelle .

Sasho Nikolov
źródło

Algorytm mnożenia wektora macierzy przy użyciu minimalnej liczby dodatków

Odpowiedzi: