Математики преодолели барьер Копперсмита-Винограда

Вирджиния Уильямс из Стэнфордского университета предложила алгоритм умножения квадратных матриц с самой лучшей на данный момент асимптотикой сложности (pdf). Прежний рекордсмен, алгоритм Копперсмита-Винограда, был предложен в 1987 году, а оценка его сложности получила прозвище одноименного барьера.

Традиционно для анализа сложности используются асимптотические оценки. Фактически, они говорят о том, с какой скоростью растет количество вычислительных операций при росте параметров алгоритма (в данном случае параметр один - размер квадратной матрицы n). Алгоритм умножения "по определению", то есть по строкам и столбцам, имеет сложность O(n3) то есть его сложность растет примерно как константа, помноженная на степенную функцию с показателем 3.

В 80-х годах прошлого века Дон Копперсмит и Шнуэль Виноград предложили алгоритм вычисления умножения матриц со сложностью O(n2,39). Затем они заметили, что разбиение матрицы перед умножением на подматрицы и применение алгоритма к ним позволяет довести сложность до рекордных O(n2,376). Этот результат был получен разбиением n на два. Дальнейшие разбиения, однако (на три, четыре и так далее) не принесли улучшения.

В рамках новой работы Уильямс удалось усовершенствовать оригинальную оценку Копперсмита и Винограда. В результате ей удалось показать, что при разбиении n на 8 частей, асимптотика сложности оказывается равной O(n2,3727). Несмотря на то, что улучшение получено только в третьем знаке, по словам специалистов, работа представляет интерес, поскольку барьер Копперсмита-Винограда продержался 24 года. Многие ученые полагают, что существует алгоритм с асимптотической оценкой O(n2), то есть сложность растет как количество элементов в квадратной матрице.

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

Наука и техника00:0116 февраля
Луис Глазман «Битва при Ситке»

Обойдемся

Эти индейцы воевали с русскими до 2004 года. Они вынудили Россию продать Аляску
Звери с Чумного озера
Щелковская ОПГ не знала пощады и отправляла жертв на корм рыбам
Земля и доля
Подмосковные крестьяне бьются с Грудининым за свои гектары
Огонь, вода и бандитские трупы
На работе он стреляет в боевиков, а по выходным людей спасает
Темные времена
Лихие 90-е: спецпроект «Ленты.ру»
Чисто по-русски
Российские хоккеисты ходили по краю, но выиграли Олимпиаду
Закольцевали: российские олимпийцы остались без флага
Россия выполнила все условия МОК, но этого пока недостаточно
Евгения Медведева«Не могу справиться без родителей»
Евгения Медведева — о рекордах и жизни после Олимпиады
Помашите ручкой
Олимпиада заканчивается. Россияне все еще берут медали
Abandoned Howey MansionИ тишина
Прекрасные заброшенные уголки мира
В комнате пыток
Сколько стоит самое дешевое и страшное жилье в Москве
Он же памятник
Угадай полководца: хитрый военный тест «Ленты.ру»
Соседи из ада
Интеллигентные жильцы превратили жизнь москвички в кошмар