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

Матрица общего вида. Иллюстрация пользователя 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:0724 июля
Пуск ракеты «Союз-2» с Восточного

Стоп машина!

Россия откажется от «Ангары» и Восточного ради Байконура и «Союза-5»
Языческая сила
Картинка с викингом рассорила общину и довела до уголовного дела
«Кто нибудь раньше уже катался на самокате?» — «Это секретная информация»Дети дождя
Репортаж из летнего лагеря для подростков с аутизмом Центра «Антон тут рядом»
Фото: пресс-служба ресторана «Экспедиция»Фестиваль органов
Где в Москве вкусно готовят рожки да ножки
Наталья ПоклонскаяПлавающий график
Суровая рыбалка и охота за бабочками — как отдыхают депутаты и чиновники
Александр Евстифеев«Радоваться нечему. Но и ступор ни к чему»
И. о. главы Марий Эл Александр Евстифеев о том, как выжить республике-банкроту
Президент Польши Анджей Дуда с супругойСудный день
Из-за планов судебной реформы поляки перессорились между собой и с Брюсселем
Клан Хаккано
Что общего у афганской террористической группировки и героев фильма про мафию
Former Utah Gov. Jon Huntsman walks on a platform Tuesday, June 21, 2011, at Liberty State Park in Jersey City, N.J., after announcing his bid for the Republican presidential nomination, (AP Photo/Mel Evans)Многодетный мормон в Спасо-хаусе
Почему Трамп хочет назначить послом в России китаиста без знания русского языка
Древность и молодость современного Ирана
Республика через 38 лет после Исламской революции
Таиландские раболовы
Гигантские флоты с экипажами из рабов губят индонезийскую экономику
Автобус TEBНаживка для инвестора
Как технический прогресс и научные открытия рождают аферы века
Не лезь в бутылку
Помогут ли безалкогольные выходные в борьбе с пьянством
Не фондом единым
Власти решили защитить дольщиков от долгостроя
Перемена слагаемых
Как «АвтоВАЗ» планирует избавиться от лишних рук
Зато мы делаем ракеты
Почему не состоялось импортозамещение на рынке гражданского оружия
Возьмут под крыло
Для чего Росгвардии нужна собственная авиация
Похищение в особо крупном размере
Зачем неизвестные выкрали министра строительства Дагестана
Александр Шарапов и Андрей ПылевКрепкие ореховские
Убийца знаменитого киллера Саши Македонского дал признательные показания
Сверкая пятками
Как побег англичан от нацистов превратился в народный подвиг
Красная угроза
Почему в 1917 году американцев испугал пароход, полный большевиков
Пуск ракеты «Союз-2» с ВосточногоСтоп машина!
Россия откажется от «Ангары» и Восточного ради Байконура и «Союза-5»
Кто рисует машины, которые мы видим каждый день
Шеф-дизайнеры крупнейших автокомпаний, которых почти никто не знает
Заряд боди-позитива
Три причины стать владельцем электрического Smart Fortwo без крыши
Тест: угадай первые машины автодизайнеров
Знаете ли вы, с чего начинали главные автомобильные художники современности?
Величайшие машины СССР и России
10 отечественных автомобилей, которыми можно гордиться
«Я ничего не делаю, и мне это нравится»
Откровения москвички, которая сдает жилье и принципиально не работает
Зарыться в песок
Купить квартиру на море теперь можно за миллион рублей и дешевле
Входят и выходят
Самые известные, необычные и дорогие бордели мира
У вас упало
Что на самом деле происходит с ценами на квартиры в Москве