Algoritma multiplikasi vektor matriks menggunakan penambahan minimal

10

Pertimbangkan masalah berikut:

Diberikan matriks kami ingin mengoptimalkan jumlah penambahan dalam algoritma multiplikasi untuk komputasi . $M$ $v \mapsto Mv$

Saya menemukan masalah ini menarik karena hubungannya dengan kompleksitas perkalian matriks (masalah ini adalah versi terbatas dari perkalian matriks).

Apa yang tahu tentang masalah ini?

Apakah ada hasil menarik yang mengaitkan masalah ini dengan kompleksitas masalah multiplikasi matriks?

Jawaban atas masalah tampaknya melibatkan menemukan sirkuit dengan hanya gerbang tambahan. Bagaimana jika kita mengizinkan gerbang pengurangan?

Saya mencari pengurangan antara masalah ini dan masalah lainnya.

Termotivasi oleh

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

Jika

adalah matriks

0-1, maka batas bawah yang diketahui pada jumlah penambahan sangat tergantung pada kelompok / semi-grup tempat kita bekerja. Jika kita mengerjakan semigroup

atau bahkan

, maka batas Nechiporuk, bersama dengan konstruksi yang diketahui, memberikan batas bawah eksplisit sekitar

. Jika, namun kami berada di grup

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),+)$ , maka situasinya agak menyedihkan: batas bawah terkuat yang diketahui hanya berupa

. Lebih banyak dapat ditemukan di sini .

ω (n)

$\omega(n)$

Stasys

9

Ini pada dasarnya adalah masalah yang memotivasi Valiant untuk memperkenalkan kekakuan matriks ke dalam kompleksitas (sejauh yang saya mengerti sejarah).

Sirkuit linear adalah sirkuit aljabar yang hanya gerbangnya adalah gerbang kombinasi linear dua input. Setiap transformasi linear (matriks) dapat dihitung dengan sirkuit linier dengan ukuran kuadrat, dan pertanyaannya adalah kapan kita bisa melakukan yang lebih baik. Diketahui bahwa untuk matriks acak kita tidak dapat melakukan lebih baik secara signifikan.

Beberapa matriks - seperti matriks transformasi Fourier, matriks peringkat rendah, atau matriks jarang - dapat dilakukan secara signifikan lebih baik.

Matriks yang cukup kaku tidak dapat dihitung oleh sirkuit linear yang secara simultan ukuran linear dan kedalaman log (Valiant), tetapi hingga hari ini tidak ada matriks eksplisit yang diketahui yang memiliki batas bawah super-linear pada ukuran sirkuit linear.

Saya tidak ingat melihat hasil yang mengatakan bahwa sulit untuk menghitung ukuran rangkaian linier terkecil untuk matriks yang diberikan, tetapi saya tidak akan terkejut jika itu NP-hard.

Joshua Grochow
sumber

3

Ini NP-hard, lihat 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$

Batas-batas ini pada dasarnya adalah yang terbaik. Lihat Bab 6.3. dalam buku Chazelle .

Sasho Nikolov
sumber

Algoritma multiplikasi vektor matriks menggunakan penambahan minimal

Jawaban: