VD Net

2 декабря 2011, 15:07

Уменьшена экспонента умножения матриц

На дороге к числу 2 выстроена ещё одна плитка: теперь для матриц размерности NxN существует алгоритм умножения матриц, требующий O(N^2.373) операций. Новая оценка была доказана математиком Вирджинией Василевской-Вильямс, предыдущая же, разработанная Копперсмитом и Виноградом в 1987 году, держалась непоколебимой более 20 лет.

Практической значимости, к сожалению, пока не слишком много, т.к. даже алгоритм Копперсмита-Винограда (O(N^2.376)) может применяться только для матриц огромной размерности, памяти современных компьютеров для хранения которых не хватит, иначе алгоритм не приносит никакого выигрыша. Более подробно об открытии можно прочитать по ссылке.
VD42
Копирование и использование материалов сайта разрешается только при указании активной прямой ссылки без rel=nofollow на страницу с копируемым материалом. Если какие-то условия не выполнены или не могут быть выполнены, то разрешение можно получить по электронной почте vladislav.kochemaev@gmail.com с указанием цели использования. При копировании материалов сайта вы автоматически соглашаетесь с этими условиями.