наука не стоит на месте
Nov. 29th, 2011 01:28 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva(это будет интересно только программистам/компьютерщикам, зато они-то визжать будут от восторга)
Скотт Ааронсон рассказал потрясающее. Как вы помните, уже 20 лет лучший алгоритм для умножения двух матриц n x n делает эту неблагодарную работу за время O(n2.376) - результат Копперсмита и Винограда. Так вот, появилась новая статья, в которой эта верхняя граница снижена - до O(n2.373)!!!
Все подробности в этой статье (в ее введении есть также полезный обзор всей истории алгоритмов умножения матриц). Я сегодня, подозреваю, уснуть не смогу от возбуждения...
Скотт Ааронсон рассказал потрясающее. Как вы помните, уже 20 лет лучший алгоритм для умножения двух матриц n x n делает эту неблагодарную работу за время O(n2.376) - результат Копперсмита и Винограда. Так вот, появилась новая статья, в которой эта верхняя граница снижена - до O(n2.373)!!!
Все подробности в этой статье (в ее введении есть также полезный обзор всей истории алгоритмов умножения матриц). Я сегодня, подозреваю, уснуть не смогу от возбуждения...
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2011-11-28 11:32 pm (UTC)no subject
Date: 2011-11-28 11:34 pm (UTC)no subject
Date: 2011-11-28 11:35 pm (UTC)no subject
Date: 2011-11-28 11:37 pm (UTC)Теперь (если игнорировать для простоты константные факторы) вы сможете их перемножить в два раза быстрее!!!
no subject
Date: 2011-11-28 11:37 pm (UTC)no subject
Date: 2011-11-28 11:40 pm (UTC)no subject
Date: 2011-11-28 11:44 pm (UTC)no subject
Date: 2011-11-28 11:45 pm (UTC)Не, не то, чтобы я все технически детали понимаю, но общую идею — вполне.
Понимаю, какой кайф теряю от неспособности прочесть pdf-ку.
Не, все, пойду хотя бы что-нибудь по математике выучу. :3
no subject
Date: 2011-11-28 11:47 pm (UTC)no subject
Date: 2011-11-28 11:47 pm (UTC)Умножение матриц это классический пример бессилия чисто алгоритмического решения перед реальным миром.
Оптимизация доступа в память, и вообще реалити чек, позволяет решать эту задачу на порядки быстрее, чем самый оптимизированный по вычислениям алгоритм.
no subject
Date: 2011-11-28 11:50 pm (UTC)no subject
Date: 2011-11-28 11:53 pm (UTC)no subject
Date: 2011-11-29 12:00 am (UTC)Почему? А математикам? :)
no subject
Date: 2011-11-29 12:01 am (UTC)no subject
Date: 2011-11-29 12:07 am (UTC)(10^100)^2.373 ~ 2*10^237
Что у нас там из суперкомпьютеров? Fujitsu K с 10 PFLOPs?
получается приблизно 6*10^213 лет.
Если нашей молоденькой вселенной ~10^10 лет, то нужно
а) 10^200 вселенных
или
бэ) 10^200 Fujitsu K.
Ну или более другой алгоритм. :-)
ЗЫ: Пожалуй я тоже не усну сегодня, буду считать суперкомпьютеры
no subject
Date: 2011-11-29 12:15 am (UTC)"We demonstrate the effectiveness of our new analysis by showing that the 8th tensor power of the CW algorithm [10] in fact gives ω < 2.3727. (It is likely that higher tensor powers can give tighter estimates, and this could be the subject of future work.)"
no subject
Date: 2011-11-29 12:16 am (UTC)no subject
Date: 2011-11-29 12:19 am (UTC)no subject
Date: 2011-11-29 12:19 am (UTC)no subject
Date: 2011-11-29 12:19 am (UTC)no subject
Date: 2011-11-29 12:20 am (UTC)no subject
Date: 2011-11-29 12:22 am (UTC)(сказал он глубокомысленно)
no subject
Date: 2011-11-29 12:23 am (UTC)no subject
Date: 2011-11-29 12:28 am (UTC)no subject
Date: 2011-11-29 12:28 am (UTC)