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

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

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

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

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

    Комментарии 42

      +38
      Ну наконец-то!
        +33
        Черт, вы правы! Всегда этих 0.003 мешались под ногами и тормозило всё из-за них…
          +2
          То есть у Вас есть реализация алгоритма Копперсмита-Винограда? =)
            0
            Где-то завалялась, нужно поискать =D
              +33
              Ага, каждое утро для разминки пишу её… 15 приседаний, 10 отжиманий и дважды — реализацию алгоритма Копперсмита-Винограда.
              +3
              Теперь заживём!
                +58
                Вы, наверное, считаете этот ваш комментарий очень остроумным.

                Но, чтобы читатели чуть поглубже поняли о чём речь, я поясню, почему эти 0.003, натурально, огромный прогресс. Результатов по этому вопросу не было 20 лет. Сама задача оценки экспоненты матричного умножения по уровню вовлечённости напоминает теорему Ферма. Все верят, что в итоге в качестве оценки будет получена константа 2. Жаль, пока никто не может этого доказать.

                Наверное каждый третий математик, который имеет отношение к вычислительной алгебре, когда-то брался за эту задачу. Есть математики, которые положили жизнь на решение этой задачи, и не смогли получить новой оценки.

                Сама же экспонента матричного умножения по уровню значимости — мировая константа. А задача по её получению — одна из центральных задач вычислительной алгебры.

                Вот уже около полувека (с тех пор, как эта проблема встала) идёт нешуточная борьба за эту оценку. И когда по этой проблеме после такого большого перерыва получили новый результат — это очень и очень значительная новость!
                  +12
                  Шутка не всегда означает сарказм. Иногда это просто добрый юмор. :-)
                    +16
                    Конечно не всегда, но я подозреваю, что в этом конкретном случае добрая часть уважаемых посетителей хабрахабра в силу того, что они не специалисты в этой области, не понимают значения этих 0.003.

                    Поспешил разъяснить.
                      –5
                      Да-да-да! Это подобно тому, что соотношение массы гравитационной к Массе инерционной придвинули бы к 1 еще на один разряд. Или степень радиуса расстояния между зарядами в знаменателе закона Кулона придвинули бы к 2 еще на один разряд.
                        0
                        И здорово, что разъяснили, да. Мне бы самому стоило.

                        Кстати, по поводу математиков, положивших жизнь. Есть репорт Джеймса Ива. Он два года назад опубликовал свои промежуточные результаты с оценкой n^{2+o(1)}. И вскоре после этого умер. В самом репорте есть комментарий Дональда Кнута, который пишет, что в каком-то месте не понял.
                    +5
                    Вы тоже слишком переоцениваете данное событие. На практике даже алгоритм Копперсмита-Винограда не используется (используют алгоритм Штрассена). А знаете почему? Потому что он не практичен! Я даже не смог найти ссылки на реализацию етого алгоритма и это при том что про него знают уже 33 года.
                      +1
                      24, а не 33, ниже я приводил верную дату.

                      Насколько я помню, алгоритма Копершмита-Винограда как такового не существует. Ими теоретически, без предъявления алгоритма в явном виде, показана их оценка.

                      С точки зрения практика вы, безусловно, правы. Впрочем, эта точка зрения подходит также для литературоведа или доярки. Я к тому, что то, что именно вам не полезен этот результат, совершенно не значит, что он не значителен.

                      С точки зрения теоретической математики (которая чаще всего со временем даёт практическую пользу) это серьезный прорыв.

                      Из чисто банальных соображений, это показало математикам, что проблема сдвинута с мёртвой точки. В науке так часто бывает, что такая вот сдвижка с мёртвой точки провоцирует серию результатов самых разных учёных.
                        +3
                        Насколько я помню, алгоритма Копершмита-Винограда как такового не существует. Ими теоретически, без предъявления алгоритма в явном виде, показана их оценка.
                        Нет, здесь вы неправы, они привели явный алгоритм в оригинальной публикации. Он непрактичен, да, но существует.
                          0
                          Возможно, вы правы. Я очень давно и очень по диагонали просматривал эту публикацию. И тогда у меня сложилось мнение, не исключено, что поверхностное, что извлечь алгоритм в явном виде не удастся.
                          0
                          А я не говорил что результат не полезен. Только что вы его переоцениваете. Я сам закончил вычислительную математику, сейчас работаю с вычислительной геометрии. Плохо быть чистым теоретиком или практиком, толковий математик должен сочетать качества обоих.
                          И да не вся теоретическая математика со временем дает пользу (только малая часть). В большинстве случаев теория строится для предоставления аппарата способного решать практические (востребованные) задачи.
                          При умножении двух матриц что вас интересует кроме сложности (и даже больше)? Точность результата! Стандартний метод (N^3) и метод Штрассена имеют очень хорошую численную устойчивость, они используют только умножение, вычитание и добавление элементов матрицы. Как только вы начинаете вычислять статистики, делить (возможно на маленькие числа) и делать более сложные операции вы теряете численную устойчивость. Кроме того большим плюсом алгоритма Штрассена является возможность паралельного вичисления субматриц.
                        +1
                        На самом деле ни грамма не сомневаюсь в значимости этого события для науки.
                        И шутка не в том, что открытие бесполезно, а в том, каким оно кажется обычному человеку
                    0
                    Казалось бы, этот вопрос должен быть решен уже давно…

                    Правда, не очень понятно, насколько выгодно его использовать из-за константы впереди. Судя по формулам, она должна быть не маленькой.
                      +5
                      А почему Вам так кажется?

                      Да, известно, что эти улучшенные алгоритмы становится осмысленным использовать лишь на огромных матрицах. Говорят, что Боинг использует алгоритм Штрассена.
                        0
                        мне кажется все его используют, потому что в таком виде он входит в основные библиотеки для линейки. :)
                        –1
                        Да не только контанта имеет значение. Если умножать матрицы методом Штрассена или обычно (за N^3) вам не нужно вычислять какие то статистики, собственние значения матрицы и тому подобное. И если вам важна точность (как в примере с Боинг), то ви не будете использовать чисельно нестабильные алгоритми.
                        0
                        А почему Вам так кажется?

                        Да, известно, что эти улучшенные алгоритмы становится осмысленным использовать лишь на огромных матрицах. Говорят, что Боинг использует алгоритм Штрассена.
                          +14
                          Я шокирован! Думал, этого ещё долго произойдёт, всё-таки 20 лет без прогресса.

                          Я проглядел мельком её статью. Выходит, результат достигнут не с помощью подхода Кона и Уманса с вложением операции умножения матриц в операцию умножения групповой алгебры, а с помощью тензорного подхода.

                          Не знаете, результат уже проверили специалисты? Может быть там всё-таки ошибка…

                          P.S. Занимаетесь этой задачей?
                            0
                            Нет, я не занимаюсь. =)

                            Как я понимаю, результат пока не опубликован. Насколько он проверен, не знаю. Но знаю, что Вирджи фигню не стала бы выкладывать. Наверное, Раян прочитал всё-таки. =)
                            +1
                            полученную Копперсмитом и Виноградом в 1978 году

                            Всё-таки в 1987, а не в 1978 году
                            +5
                            Вот за это я люблю математику :3
                            Топикстартеру маленькое замечание: поверьте, «ω» и «≤» — не настолько редко встречающиеся в шрифтах символы, чтобы вставлять их при помощи картинок.
                              +3
                              Я полагаю, топикстартер просто логично предпочитает набирать все формулы в LaTeX, потому что его рендерер — идеальный. Статья на Хабре не должна быть тому исключением.
                                0
                                Мне казалось, что в идеальном рендерере нижняя черта должна быть не горизонтальной, а параллельна средней, примерно как вот в этом символе ⋜, если его перевернуть.
                                Я понимаю, когда в неспециализированном тексте по техническим ограничениям некоторые элементы выглядят не совсем так как положено в математике. Но в латехе-то должно быть.
                                  +1
                                  Символ с нижней чертой, параллельной средней, — это традиция русской математической школы.
                                  Символ с горизонтальной нижней чертой — это традиция западной математической школы.
                                  Очевидно, онлайн-рендерер LaTeX`а использует дефолтные настройки и рендерит по западной традиции. Чтобы переключить его на русские настройки, можно, например, использовать russcorr. Или что-нибудь другое.

                                  Как пример других значимых отличий русской и западной систем записи — нижний/верхний частичный предел. У нас он записывается как lim с чертой снизу/сверху, а во всем мире — как «lim inf»/«lim sup».
                                  0
                                  Да, я люблю латех. Меня всё же не хватило на то, чтобы, например, и n делать картинкой, но всё же. =)
                                0
                                один из немногих случаев на хабре, когда заходишь под кат ради прочтения комментов :)
                                  +2
                                  по-моему крайне распространенный случай
                                • НЛО прилетело и опубликовало эту надпись здесь
                                    0
                                    image
                                    И это все сделала женщина? Мое глубочайшее уважение.
                                      +2
                                      Поверьте, то что вы привели сделала какая-нибудь система компьютерной алгебры.
                                        +3
                                        И эту картинку сумел вставить в пост человек с ником на букву «L»? Я поражен до глубины души!
                                          –1
                                          Всего лишь два тролля?! Мне показалось, что на мой неаккуратно написанный коммент их найдется куда больше.
                                          0
                                          На сколько % быстрее станет перемножение матрица 5000x5000?
                                            0
                                            На 2.588%, если коэффициент одинаковый.

                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                          Самое читаемое