Как стать автором
Обновить

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

Время на прочтение 2 мин
Количество просмотров 8K
Новости из мира науки: матрицы размера теперь умеют умножать за . Другими словами, доказано, что , где  — экспонента умножения матриц. Доказала это совсем недавно Вирджиния Василевска-Вильямс, улучшив тем самым оценку , полученную Копперсмитом и Виноградом в 1987 году. Я напишу про важность этого алгоритма совсем немножко. Тем, кому интересно узнать побольше, предлагается почитать посты Скотта Ааронсона, Ричарда Липтона и Билла Гасарша.

Итак, многие теоретические верхние оценки на время работы алгоритмов используют экспоненту умножения матриц. В частности, много алгоритмов на графах эксплуатируют данную идею: если A — матрица смежности графа, то  — количество (не обязательно простых!) путей длины k между вершинами i и j. Эта простая идея позволяет за время проверить, есть ли в графе треугольник (3-клика): нужно возвести матрицу смежности в куб (для этого потребуется два умножения матриц) и посмотреть на диагональ. Отметим, что речь здесь именно о теоретических оценках, поскольку продвинутые алгоритмы умножения матриц хоть и обгоняют асимптотически простой кубический алгоритм, но на практике дают ускорение только на огромных размерах матриц.

Ещё несколько примеров:

  • Расстояния между всеми парами вершин (all-pairs shortest path).
    Кратчайшие пути между всеми парами вершин в невзвешенном графе можно найти за время . Для этого возводим матрицу смежности в степень n (отсюда и вылезает o(1) в степени), попутно подсчитывая кратчайшие пути. Узнать подробности, а также много других подобных элегантных алгоритмов можно из
    отличнейшей презентации Ури Цвика.
  • Задача максимальной 2-выполнимости (MAX-2-SAT).
    Единственный известный алгоритм для этой задачи, который работает быстрее, чем полный перебор (), тоже основан на умножении матриц. Его время работы равно и он использует экспоненциальную память. В двух словах идея такая: по входной формуле строим огромный граф (на вершинах) и с помощью быстрого умножения матриц проверяем, есть ли в нём треугольник. Примечательно, что придумал его муж Вирджинии — Раян Вильямс.
  • Гамильтонов путь (Hamiltonian cycle).
    Ещё есть такой забавный пример, в котором не так важно, за сколько мы умеем умножать матрицы, но всё же. Алгоритм для поиска гамильтонова пути за время и полиномиальную память (отметим, что известный алгоритм Хелда-Карпа для этой задачи основан на динамическом программировании и требует экспоненциальной памяти): он вычисляет число путей длины n-1 на всех подмножествах вершин графа с помощью обозначенного выше трюка; после этого формула включений-исключений позволяет просуммировать найденные числа так, чтобы осталось лишь число простых путей длины n-1 (а это и есть гамильтоновы пути).
Теги:
Хабы:
+73
Комментарии 42
Комментарии Комментарии 42

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн