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

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

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

Обсудить
Наука и техника00:0117 ноября

Пробила дно

Планета-пришелец расколола Землю и сдвинула континенты
Наука и техника00:0115 ноября
Голодающие дети в Бузулуке (Самарская губерния), 1921-1922 гг.

«Обезумевшие родители отбирали еду у детей»

Советская власть бросила миллионы умирать от голода, но их спасли американцы
Моя семья
Легендарный маньяк и его культ кровавых убийц держали в страхе всю Америку
Чарльз МэнсонКонец маньяка: Чарльз Мэнсон умер в тюрьме
Легендарный убийца не дождался великой межрасовой войны
Порошок, приходи
Жадные мексиканцы потеряли доход от марихуаны и завалили Америку героином
Кровавая ривьера
Франция отстреливает врагов по всему миру, пока никто не видит
«Девочку из России тут никто не ждет»
История сибирячки, перебравшейся в Нидерланды
Во всем виноват буй
Она мечтала о круизе с секс-рабынями, но потерялась в море с боевой подругой
«Не надо меня спасать»
Звездный путешественник нашел тайное племя головорезов, ввязался в войну и выжил
Эмилио Эстевес в роли Билли КидаМалыш на миллион
Легендарный головорез Дикого Запада передал привет из прошлого
Самые большие шины в мире
Огромные покрышки, которые подойдут даже машине Годзиллы
5 причин, почему мы ненавидим кроссоверы
Объясняем в картинках, почему самые популярные машины в мире никуда не годятся
Audi Q5 против SQ5
Пять причин купить Audi SQ5 вместо обычной Q5 (и одна против)
Кто делает самые эпатажные британские машины
«Рэйнджи», «Астоны» и «Роллс-Ройсы»: лучшие творения ателье Kahn Design
Ловушка для планктона
Тест: Какой офис идеально вам подходит
«Моя бывшая живет на помойке»
Москвич сделал из жены бомжа, и ему не стыдно
Белый друг
Самые необычные туалеты мира
Это Англия, детка!
Идеальный дом можно выиграть за две тысячи рублей
Берите две
Пять стран, где ипотеку дают под смешной процент