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

[avva]

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

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

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

Comments

[melkore.livejournal.com]

а можно как-нибудь разжевать простым смертным в чём суть прорыва, дабы все могли разделить радость? )

[avva.livejournal.com]

Ну смотрите. Представьте себе, что у вас есть две квадратные матрицы, скажем каждая из них размером 10¹⁰⁰ на 10¹⁰⁰.

Теперь (если игнорировать для простоты константные факторы) вы сможете их перемножить в два раза быстрее!!!

[shadow-ru.livejournal.com]

По-моему avva просто смеётся.

[http://users.livejournal.com/sorcerer_/]

Я что-то пропустил и умножение матриц уже меньше перестало зависеть от паттерна доступа в память и больше - от количества вычислений?

[avva.livejournal.com]

То мухи, а то котлеты.

[aixie.livejournal.com]

Блин. Круто. Реально круто.

Не, не то, чтобы я все технически детали понимаю, но общую идею — вполне.

Понимаю, какой кайф теряю от неспособности прочесть pdf-ку.
Не, все, пойду хотя бы что-нибудь по математике выучу. :3

[http://users.livejournal.com/_iga/]

на криптостойкости это отразится?

[avva.livejournal.com]

Нет.

[spartanus.livejournal.com]

это будет интересно только программистам/компьютерщикам

Почему? А математикам? :)

[avva.livejournal.com]

Боюсь, что они сочтут этот результат слишком прикладным :)

[cema.livejournal.com]

Смешно, да.

[ygam.livejournal.com]

А про алгоритм Фюрера для умножения целых чисел ты знаешь?

http://www.cse.psu.edu/~furer/Papers/mult.pdf

[kolbusa.livejournal.com]

Бегло просмотрел. Ни слова про численную устойчивость метода! Дополнительные проблемы есть уже у Штрассена.

[dennis.livejournal.com]

Математику в статье разгрести нелегко...
У кого-нибудь уже есть исходники на каком-нибудь ЯП, посмотреть дабы?

[huzhepidarasa.livejournal.com]

Алгоритм Коперсмита-Винограда разве используется практически? Он скорее математикам интересен.

[migmit.livejournal.com]

Охрененно, повод выпить.

[eterevsky.livejournal.com]

[skylump.livejournal.com]

ДА!!!

[pepel.livejournal.com]

Прости, полнейший офф, и я вообще не в теме, но я так люблю твои посты в этом стиле:)

[avva.livejournal.com]

Спасибо :)

[pennanth.livejournal.com]

Следует ли понимать, что госпоже Василевки-Уильямс удалось уменьшить "О" большое до "О" большого меньших размеров? Тогда назревает тост - за уменьшение "О" большого до "о" малого!

Ну, я программист... А где повод для визга-то?

[(Anonymous)]

Чтобы хоть как-то заметить разницу, матрицы должны быть такими огромными, какие ни один из знакомых мне программистов, физиков и даже математиков реально умножать не пытался. Могу ошибаться - но за себя говорю точно. Если матрицу возможно хотя бы СОХРАНИТЬ на PC (даже не в памяти, а хотя бы на среднего размера диске), то разница в scaling factor - меньше 5%. Причем не понятно, какой там prefactor, то есть может быть новый алгоритм окажется в 10 раз медленнее!

Хочешь быстрее - делай матрицу sparse, не выходит - пиши на ассемблере.

А сие - интересно лишь гуглу и пентагону, да и то по эффективности сравнимо с экономией туалетной бумаги...

Re: Ну, я программист... А где повод для визга-то?

[dvornikstepanof.livejournal.com]

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

[1benrinnes.livejournal.com]

http://www.siam.org/pdf/news/174.pdf

[(Anonymous)]

Здравствуйте, простите за оффтоп.
Мы тут спорим насчет правильности решения одной задачи. Задача про три шкатулки. Вот она вместе с зачтённым ответом на сайте брейнгеймс: http://img191.imageshack.us/img191/1816/99050108.png

В частности волнует ответ "не знаю", мне кажется, во всех подобных задачах такое не допускается. И вообще насколько осмысленен вопрос "Переместится ли конфета влево, если ее переложить", ведь его можно трактовать как "Верно ли, что конфета всегда будет перемещаться влево, если ее переложить". Потому что первый вопрос не слишком формализован и мало чем отличается от вопроса "существуют ли инопланетяне". Как думаете?