Доказательства того, что умножение матриц может быть сделано в квадратичное время?

Широко распространено мнение, что , оптимальный показатель для умножения матриц, фактически равен 2. Мой вопрос прост:$\omega$

Какие у нас есть основания полагать, что ?$\omega = 2$

Мне известны быстрые алгоритмы, такие как Coppersmith-Winograd, но я не знаю, почему их можно считать доказательством для .$\omega = 2$

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

Я хотел бы добавить к комментарию Марка Рейтблатта и ответ Амира Шпильки. Во-первых, одна из гипотез, выдвинутых Коном, Клейнбергом, Сегеди и Умансом, не является теоретико-групповой, но является чисто комбинаторной (Conj. 3.4 в их статье FOCS '05 ). Эта гипотеза говорит о том, что «сильная пропускная способность USP равна ». Копперсмит и Виноград, продемонстрировав свой лучший в настоящее время алгоритм для умножения матриц, показали, что емкость USP - это то же число (хотя они не сформулировали это совсем так). Хотя между сильными USP и USP есть разница, это является некоторым свидетельством того, что их гипотеза, по крайней мере, правдоподобна.$\frac{3}{2^{2/3}}$$\frac{3}{2^{2/3}}$

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

Во-вторых, я согласен с Амиром Шпилькой в ​​том, что последовательность прошлых алгоритмов выглядит несколько нерегулярно. Однако одна из приятных вещей в теоретико-групповом подходе заключается в том, что в этом подходе можно сформулировать почти все (не все) предыдущие алгоритмы. Хотя различные теоретико-групповые конструкции в [CKSU] могут показаться внешне немного случайными, в контексте теоретико-групповой структуры они кажутся значительно более естественными и менее специальными (по крайней мере для меня), чем многие из предыдущие алгоритмы.

Я не знаю о других, но могу сказать вам, почему я склонен полагать, что . Когда вы читаете историю и разработку быстрых алгоритмов умножения матриц, я думаю, что трудно не почувствовать, что все, что нам нужно, это просто немного лучший базовый алгоритм, из которого, даже используя известные методы, будет следовать , По сути, все современные алгоритмы (включая теоретико-групповые) начинаются с некоторой «простой» конструкции, которая затем усиливается. Эти конструкции умны, но они дают читателю какое-то «специальное» чувство. Я не вижу причин полагать, что мы не можем придумать лучшие простые конструкции.$\omega=2$$\omega=2$

Есть аналогия, которую я использую, чтобы оправдать предположение, что для меня. Я понимаю, что это довольно эвристично, но, тем не менее, это помогло мне, например, в понимании некоторых интуиций, лежащих в основе Cohn et al. бумага.$\omega = 2$

Свертка и умножение матриц аналогичны. Если и являются матрицу с размерностью матрицы и , то . Если и - векторы длины и , то . В обоих случаях конечным результатом является вектор, состоящий из сумм произведений, но реляционная структура во входных данных различна. Для свертки мы можем использовать БПФ для вычисления ответа за время вместо тривиального . Аналогично можно ожидать$A$$B$$n$$n$$C = AB$$C(i,j) = \sum_{k=1}^n A(i,k) B(k,j)$$A$$B$$n$$C = A*B$$C(i) = \sum_{k=1}^n A(k)B(i-k)$$\tilde{O}(n)$$O(n^2)$$\tilde{O}(n^2)$ алгоритм времени для умножения матриц. Вопрос в том, что является аналогом преобразования Фурье, которое может помочь для умножения матриц?

Скорее всего, это . Наличие кажется фантастическим, поскольку ведение бухгалтерского учета с постоянным коэффициентом не похоже на масштаб.$O(n^{2} log(n^2))$$\omega = 2$