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

Матрица общего вида. Иллюстрация пользователя 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), то есть сложность растет как количество элементов в квадратной матрице.

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

Обсудить
Обреченный на разрушение
Как живется людям на исчезающем острове в городской черте Архангельска
Вычищают до блеска
Путин проинспектировал уборку Арктики
Идите к ВОПу
Что изменится с превращением участковых терапевтов во врачей общей практики
Петр Лидов-Петровский: «Послужите! Людьми станете»
Стоит ли сегодня уклоняться от призыва в российскую армию
«Движуха, которой раньше не было»
Что стоит за протестной активностью юных россиян
Фарту масти
Как простые русские парни становятся легендами киберспорта
Распакуй — не распакуй
В Нью-Йорке представили два Samsung Galaxy S8
Красный — новый черный
Зачем люди скупают допотопные компьютеры и свитеры Apple
Замороженная стволовая клетка человека Внутренние бомбы
Как клеточный суицид помогает против рака и старости
Томми Эммануэль«Мысли о славе не дают свободно дышать»
Томми Эммануэль о бизнесе счастья, гитарах и пропаганде
Глубины глубинки
Редкие картины русского авангарда на выставке «До востребования. Часть II»
«Меня не напугать сильной, умной женщиной»
Режиссер «Большой маленькой лжи» Жан-Марк Валле о работе с Кидман и Уизерспун
«Клетка»Приятного аппетита
Как балерины Большого театра убили и съели всех мужчин труппы
Первый тест премиального «корейца» Genesis
Смог ли обновленный Genesis G80 догнать «немецкую тройку»? Спойлер: нет
Все конкуренты новому SsangYong Rexton
С кем будет бороться за покупателей новый корейский внедорожник
«Мерседес», который предсказал будущее
Забытые концепт-кары: Mercedes-Benz Auto 2000
50 оттенков Блока
Вспоминаем раскраски всех автомобилей Кена Блока
Талант расправил плечи
Лучшие архитектурные проекты 2017 года: от города в пустыне до термальных ванн
Адская машина
Ученые и урбанисты придумали, что делать с заполонившими города автомобилями
«Если у тебя нет любовника, квартире взяться неоткуда»
Исповедь россиянки, ставшей ипотечницей в 20 лет
Тариф «Хватит»
За услуги ЖКХ можно платить в разы меньше