Доказательство того, что умножение матриц происходит не за

39

Принято считать, что для всех ε>0 можно умножить две матрицы N×N за О(N2+ε) времени. Некоторое обсуждение здесь .

Я спросил некоторых людей, которые более знакомы с исследованием, думают ли они, что существует К>0 независимый от N такой, что существует алгоритм для умножения матриц, и они в подавляющем большинстве, похоже, имели Интуиция, что ответ «нет», но не может объяснить, почему. То есть они считают, что мы можем сделать это за время, но не за время.О(N2журналКN)О(N2,001)О(N2журнал100N)

Какие есть основания полагать, что при фиксированном алгоритма ?О(N2журналКN)К>0

Брайан
источник

Ответы:

29

Существует алгоритм для умножения матрицы N×N0,172 матрицу N0,172×N в арифметических операциях N2Полилог(N) . Основное тождество, использованное для этого, взято из статьи Копперсмита «Быстрое умножение прямоугольных матриц», но объяснение того, почему это приводит к N2Полилог(N) вместо N2+ε содержится в приложении к статье Уильямса «Новые алгоритмы». и нижние оценки для цепей с линейными пороговыми вентилями ".

Это работает только потому, что идентичность Копперсмита имеет некоторую дополнительную структуру, которой вы можете воспользоваться, и более поздние алгоритмы MM, похоже, не имеют такой структуры. Тем не менее, я не уверен, почему нельзя надеяться распространить этот подход на умножение матриц N×N×N

Джош Алман
источник
11

Ну, во-первых, я думаю, что все известные нам конструкции - и даже семейства потенциальных конструкций, которые предлагали люди (например, подходы Кон-Уманса, обобщения Копперсмита-Винограда) - "просто" создали бы семейство алгоритмов Aε работает во времени О(N2+ε) . Таким образом, чтобы иметь единственный алгоритм, который выполнялся в О(N2поLY(журналN)) , он должен был бы не просто быть сумасшедшим асимптотически лучше, чем существующие подходы, но и выглядеть действительно иначе.

Большое предостережение: я думаю. Я никогда не думал слишком много о том , сколько можно было бы изменить / добавить существующие подходы , чтобы они могли правдоподобно производить единый алгоритм работает во время О(N2поLY(журналN)) .

Джошуа Грохов
источник
3
Я не уверен, что наличие семьи не может привести к O (n ^ 2poly (log n)), поскольку, если бы можно было достаточно хорошо описать семью, можно было бы выбрать более и более эффективных членов семьи для большего n. Единственная причина, по которой это не является правдоподобным O (n ^ 2poly (log N)), заключается в том, что используемые константы, вероятно, будут очень большими, но не очевидно, что это обязательно так.
Иисус Навин
1
@JoshuaZ: в принципе это не так; на практике каждый член семейства, возникающий из этих подходов, создает алгоритм со временем выполнения , и идея большинства подходов заключается просто в том, что у вас есть такое семейство, что для любого ε > 0 , есть член семейства, приводящий к алгоритму с временем выполнения O ( n 2 + ε ) . О(N2+Икс)ε>0О(N2+ε)
Джошуа Грохов
1
@JoshuaZ Я полагаю, что другой, более странный способ потерпеть неудачу, был бы, если бы каким-то образом выбор / создание члена семьи заняло более O (n ^ 2 poly (log n)) времени - например, возможно, O (1 / e) код необходим реализовать алгоритм O (n ^ (2 + e)) или что-то. Разве это не было бы диким ??
Даниэль Вагнер
10

Джош Алман показал отличные результаты нижней границы ММ, который получил награду CCC 2019 за лучшую студенческую работу! http://drops.dagstuhl.de/opus/volltexte/2019/10834/pdf/LIPIcs-CCC-2019-12.pdf

Рупей Сюй
источник
6
О(N2поLY(LогN))
4
@JoshuaGrochow Спасибо за указание на эту проблему.
Рупей Сюй