Matrixvektormultiplikationsalgorithmus mit minimaler Anzahl von Additionen

10

Betrachten Sie das folgende Problem:

Bei einer gegebenen Matrix wollen wir die Anzahl der Additionen im Multiplikationsalgorithmus zur Berechnung von . $M$ $v \mapsto Mv$

Ich finde dieses Problem interessant, weil es mit der Komplexität der Matrixmultiplikation zusammenhängt (dieses Problem ist eine eingeschränkte Version der Matrixmultiplikation).

Was ist über dieses Problem bekannt?

Gibt es interessante Ergebnisse, die dieses Problem mit der Komplexität des Matrixmultiplikationsproblems in Verbindung bringen?

Die Antwort auf das Problem scheint darin zu bestehen, Schaltungen mit nur zusätzlichen Gattern zu finden. Was ist, wenn wir Subtraktionsgatter zulassen?

Ich suche nach Reduzierungen zwischen diesem Problem und anderen Problemen.

Motiviert von

cc.complexity-theory reference-request circuit-complexity matrices arithmetic-circuits vzn
quelle

Wenn

eine

0-1-Matrix ist, hängen bekannte Untergrenzen für die Anzahl der Additionen entscheidend davon ab, über welche Gruppe / Halbgruppe wir arbeiten. Wenn wir über die Halbgruppe

oder sogar

, ergibt die Bindung von Nechiporuk zusammen mit bekannten Konstruktionen eine explizite Untergrenze von etwa

. Wenn wir jedoch in der Gruppe sind

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),+)$ dann ist die Situation eher deprimierend: Die stärksten bekannten Untergrenzen haben nur die Form

. Mehr finden Sie hier .

ω (n)

$\omega(n)$

Stasys

9

Dies ist im Wesentlichen das Problem, das Valiant dazu motiviert hat, die Matrixsteifigkeit in die Komplexität einzuführen (soweit ich die Geschichte verstehe).

Eine lineare Schaltung ist eine algebraische Schaltung, deren einzige Gatter lineare Kombinationsgatter mit zwei Eingängen sind. Jede lineare Transformation (Matrix) kann durch eine lineare Schaltung quadratischer Größe berechnet werden, und die Frage ist, wann man es besser machen kann. Es ist bekannt, dass man für eine Zufallsmatrix nicht wesentlich besser abschneiden kann.

Einige Matrizen - wie die Fourier-Transformationsmatrix, eine Matrix mit niedrigem Rang oder eine Matrix mit geringer Dichte - können erheblich besser erstellt werden.

Eine ausreichend starre Matrix kann nicht durch lineare Schaltungen berechnet werden, die gleichzeitig lineare Größe und logarithmische Tiefe haben (Valiant), aber bis heute sind keine expliziten Matrizen bekannt, für die es eine superlineare Untergrenze für die Größe linearer Schaltungen gibt.

Ich kann mich nicht erinnern, Ergebnisse gesehen zu haben, die besagen, dass es schwierig ist, die Größe der kleinsten linearen Schaltung für eine bestimmte Matrix zu berechnen, aber ich wäre nicht überrascht, wenn sie NP-hart wäre.

Joshua Grochow
quelle

3

Es ist NP-schwer, siehe cstheory.stackexchange.com/a/32272/225

Ryan Williams

7

$M$

$\Omega(n (\log n/\log \log n)^{d-1})$ $M$ $n\times n$ $d$
$\Omega(n^{4/3})$ $M$ $n\times n$ $d$
$\tilde{\Omega}(n^{2-2/(d+1)})$ $M$ $n\times n$ $d$

Diese Grenzen sind alle im Wesentlichen die bestmöglichen. Siehe Kapitel 6.3. in Chazelles Buch .

Sasho Nikolov
quelle

Matrixvektormultiplikationsalgorithmus mit minimaler Anzahl von Additionen

Antworten: