Алгоритм матричного векторного умножения с использованием минимального количества сложений

10

Рассмотрим следующую проблему:

Учитывая матрицу мы хотим оптимизировать количество сложений в алгоритме умножения для вычисления . $M$ $v \mapsto Mv$

Я нахожу эту проблему интересной из-за ее связи со сложностью умножения матриц (эта проблема является ограниченным вариантом умножения матриц).

Что известно об этой проблеме?

Есть ли интересные результаты, связывающие эту проблему со сложностью задачи умножения матриц?

Похоже, что ответом на проблему является поиск цепей только с дополнительными вентилями. Что если мы допустим ворота вычитания?

Я ищу сокращения между этой проблемой и другими проблемами.

Мотивировано

cc.complexity-theory reference-request circuit-complexity matrices arithmetic-circuits ВЗН
источник

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)$

9

Это, по сути, проблема, которая побудила Valiant ввести жесткость матрицы в сложность (насколько я понимаю историю).

Линейный контур - это алгебраический контур, единственными входами которого являются линейные входные ворота с двумя входами. Каждое линейное преобразование (матрица) может быть вычислено линейной схемой квадратичного размера, и вопрос в том, когда можно добиться большего успеха. Известно, что для случайной матрицы нельзя сделать значительно лучше.

Некоторые матрицы - такие как матрица преобразования Фурье, матрица низкого ранга или разреженная матрица - могут быть выполнены значительно лучше.

Достаточно жесткая матрица не может быть вычислена линейными цепями, которые имеют одновременно линейный размер и логарифмическую глубину (Valiant), но до настоящего времени не известны явные матрицы, для которых существует суперлинейная нижняя граница для размера линейных цепей.

Я не помню, чтобы результаты говорили о том, что трудно вычислить размер наименьшей линейной схемы для данной матрицы, но я не удивлюсь, если она будет NP-сложной.

Джошуа Грохов
источник

3

Это NP-жесткий, см. Cstheory.stackexchange.com/a/32272/225

Райан Уильямс

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$

Эти границы, по сути, являются наилучшими. Смотрите главу 6.3. в книге Шазель .

Сашо Николов
источник

Алгоритм матричного векторного умножения с использованием минимального количества сложений

Ответы: