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

Матрица общего вида. Иллюстрация пользователя Lakeworks с сайта wikipedia.org

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

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

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

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

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

Обсудить
Джордж Гроувз и Федор Чудинов На британский флаг
Сможет ли Федор Чудинов увезти из Шеффилда титул чемпиона мира по боксу
«Дьяволы», покорившие Европу
«Манчестер Юнайтед» Жозе Моуринью впервые выиграл Лигу Европы
Ульяна Тригубчак«Пока не могу преодолеть стеснительность»
Девушка из группы поддержки «Салавата Юлаева» о самосовершенствовании и КХЛ
Бей, души, убивай
Социальные сети не просто следят за нашими чувствами, они управляют ими
Самоубийственные аресты
За борьбой с «группами смерти» может стоять конфликт в силовых структурах
Привет, жестокий мир
Боль, отчаяние и мужество в объективах самых талантливых молодых фотографов
Лучшее автомобильное видео мая
Две «Тойоты» врезаются друг в друга, британский спорткар соревнуется с самолетом и многое другое
Тест-драйв японского брата «Дастера»
Как Nissan Terrano стал еще ближе к Renault Duster
Чемпионы Формулы-1 в Инди-500
Те, кому «Королевских гонок» оказалось мало
15 машин на реактивной тяге
90-летняя история автомобилей с двигателями от самолетов и ракет
От нашего стола
Российские интерьеры, сводящие иностранцев с ума
Зависли на хате
Украинцы придумали дом, который может обойтись без российского газа
Москва за нами
Какие квартиры можно купить в пределах МКАД по цене до трех миллионов рублей
Сносное настроение
Демонтаж жилых домов в Москве: что нужно знать
Вышка светит
Как выглядит частный особняк, побивший мировой рекорд этажности