Об алгоритмах умножения матриц

[Руст]

Мне кажется все нормально. Дело в том, что здесь
$\phi(x,z)=\frac{1}{m}\sum_{i=1}^m f(x,\omega^{-i})g(\omega^i,z)$
только на вид $n^3$ операций. На самом деле это совпадает с действительной частью
одного члена умножения из $Q(\omega)[x,z]$.
Я не специалист в этих делах. Хотелось узнать, были ли такие попытки.
Если нет то, попробую аккуратно расписать.

[Xaositect]

Руст в сообщении #892862 писал(а):

Я не специалист в этих делах. Хотелось узнать, были ли такие попытки.
Если нет то, попробую аккуратно расписать.

Распишите. Пока я могу сказать, что для вычисления $n$ значений $\varphi(x_1, z),\dots,\varphi(x_n, z)$ необходимо $n^2$ умножений. Как можно склеивать эти вычисления для разных $z$, я не вижу.

Попытки какие-то похожие наверняка были, в частности, несколько людей рассматривали матрицы как многочлены от двух матриц $X, Y$, но там несколько другие проблемы, там некоммутативность $X$ и $Y$ вылезает.

[patzer2097]

Xaositect, спасибо за подробный ответ! Я из Вашего поста и посмотрев указанные работы сделал три вывода.
(1) Многие из самых серьезных экспертов скептически относятся к последним результатам про $\omega$.
(2) Работы Стотерса, Ждановича и Вассилевски-Уильямс не содержат особенно много новых идей - в них просто постепенно улучшается решение некоторой задачи оптимизации, возникающей из работы Копперсмита-Винограда.
(3) Работы, представляемые на STOC, могут содержать серьезные ошибки.

[Lia]

Оффтоп отделен в «Цитата: было или приписано?»

[Руст]

Сегодня я на семинаре кафедры (теоритической информатики мех-мата МГУ) делал обзорный доклад по быстрым умножениям.
Когда приступил к своему алгоритму с $O(n^{2+\epsilon})$ и сказал, что он основывается на умножении цветных многочленов (цветных алгебр)
меня остановили и время семинара уже закончилась. В следующий вторник в 16-45 ауд. 13-10 расскажу о своем алгоритме.

[g______d]

Нашел текст, очень похожий на вышеописанное (возможно, это указанный результат и есть)

http://shamolin2.imec.msu.ru/art-211-2.pdf

Я только не понял -- в итоге умножаются матрицы за $O(n^{2+\varepsilon})$ или нет? Там как-то мутно это описано, да и журнал странный, у половины статей один соавтор.

[Руст]

Нет, это неправильная статья. Подход, сводящий к умножению квазикоммутативных многочленов правильный, однако не сводится ни к какой свертке.
Я тогда забыл, что передал Шамолину черновой вариант и узнал об этом, когда уже неправильная черновая работа пошла в печать.
На самом деле все вычисляется по хитрее. Решил опубликовать только после работающей программы.

[Xaositect]

Руст, это ведь Ваше умножение тут: http://sitito.cs.msu.ru/index.php/SITIT ... e/view/513 ?
Опять совершенно непонятно, какой у Вас получился алгоритм с $N \log N$. Для $2 \times 2$ вижу Штрассена, а дальше рекурся для того, чтобы вычислять $f^{i_1 \dots i_k}$ и непонятно, как дальше их использовать. Можете привести частный случай Вашего алгоритма для матриц $4 \times 4$?

[Sonic86]

Тут AlphaZero еще немного ускорило умножение матриц. Наверное надо дать ей логин и пароль на dxdy.ru, чтобы почаще нам писала :)
основная статья: https://www.nature.com/articles/s41586-022-05172-4
текст полегче: https://www.deepmind.com/blog/discoveri ... lphatensor