Матричное умножение. Медленное достижение мифической цели

[maxzhurkin]

Если это не так, то мы застряли в мире, который не соответствует нашим мечтам

У меня для автора (да, я знаю, что это перевод) плохая новость: математика достаточно фундаментальна, чтобы все другие миры в этом вопросе точно так же не соответствовали чьим-то (текст, вроде как, от имени математика, так что, видимо, математиков) мечтам

[grub-itler]

Учительница видит, что Вовочка не слушает урок и решает привлечь его внимание:
— Вовочка, сколько будет два плюс два?
Ноль эмоций.
— Вовочка, сколько будет два плюс два?!
— Мариванна, мне бы ваши проблемы.

[KvanTTT]

Штрассен придумал сложный набор соотношений, которые позволили заменить одно из этих восьми умножений 14 дополнительными сложениями

А это разве не замедление на современных процах, где умножение практически такое же быстрое как и сложение?

[0serg]

Для больших матриц — нет, т.к. там идут операции с подматрицами а умножение двух матриц 1000x1000 — это значительно медленнее чем 14 сложений матриц 1000x1000.

Грубо говоря мы n^3 заменяем на 14*n^2.8. Для небольших n это действительно медленнее, но для достаточно больших n (в существующей практике — где-то для n > 4k) Штрассен будет быстрее. Естественно никто не доводит Штрассена до отдельных элементов, делается несколько разбиений на подматрицы, после чего когда матрицы становятся достаточно маленькими в дело вступает обычный n^3 алгоритм

[darkAlert]

Не раскрыта тема чем отличается матричное умножение от тензорного, и почему переход к нему ускорил вычисления

[Racheengel]

Хм, вот тут https://en.m.wikipedia.org/wiki/Matrix_multiplication_algorithm#:~:text=Directly%20applying%20the%20mathematical%20definition,)%20in%20big%20O%20notation) утверждают, что можно умножить матрицы за 3n-1. То есть для n=3 уже получается быстрее, чем n в квадрате.

[Daemonis]

На каждом из 3n-1 шагов выполняется n*n умножений.

[Daddy_Cool]

Давно слежу за скоростью матричного умножения. Это ж прям спорт какой-то. Как улучшение результатов в беге на 100м. Прикол в том, что если алгоритм Штрассена еще можно использовать, то последние становятся эффективными при размере матриц 10е10000-40000.
На каком-то форуме видел вопль, типа: «А! Люди! Дайте мне алгоритм Вильямс-Василевски! У меня на компе много памяти!»