наука не стоит на месте

[avva]

(это будет интересно только программистам/компьютерщикам, зато они-то визжать будут от восторга)

Скотт Ааронсон рассказал потрясающее. Как вы помните, уже 20 лет лучший алгоритм для умножения двух матриц n x n делает эту неблагодарную работу за время O(n^2.376) - результат Копперсмита и Винограда. Так вот, появилась новая статья, в которой эта верхняя граница снижена - до O(n^2.373)!!!

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

Comments

[braindancer.livejournal.com]

А насколько часто в реальной жизни встречаются задачи с перемножением матриц 10¹⁰⁰?

[spamsink.livejournal.com]

Перемножение матриц 1000х1000 ускоряется на 2%. Очень даже неплохо.

[avva.livejournal.com]

напоминает анекдот про "на эти два процента я и живу".

[spamsink.livejournal.com]

Именно!

[braindancer.livejournal.com]

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

[racoonbear.livejournal.com]

[(Anonymous)]

а что там с константами?

[french-man.livejournal.com]

Кстати, да. Хотя на практике такие алгоритмы обычно работают лучше, чем в теоретически доказанном худшем случае.

[ygam.livejournal.com]

Это ты не учел константные факторы.

[spamsink.livejournal.com]

Насколько я понял, это тот же CW алгоритм, но painstakingly просчитанный для восьмикратной рекурсии базового алгоритма вместо двухкратной, а в свое время кратность 3 улучшения не дала, и анализ был заброшен. По идее константный фактор должен быть такой же.

[ygam.livejournal.com]

Да; я был невнимателен.

[maravan.livejournal.com]

интересно, сколько тысяч серверов сможет теперь высвободить Гугл.