Почему важно, что системы линейных уравнений решаются быстрее, чем множатся матрицы +57


AliExpress RU&CIS

В 1998, когда Google только появился, его киллер-фичей был патентованный алгоритм PageRank для сортировки результатов поиска по популярности. Описанный стэнфордскими аспирантами Брином и Пейджем в научной статье, он сводится к очень простой идее:

PR(p_i) = \frac{1-d}{N} + d \sum_{p_j \in M(p_i)} \frac{PR (p_j)}{L(p_j)}

где M(p_i) множество входящих ссылок на страницу p_i, L(p_i) число исходящих ссылок на этой странице, а N число страниц в интернете. Таким образом PR(p_i) выражает вероятность оказаться на странице p_i при случайном брожении по интернету, когда с вероятностью d мы переходим на следующую страницу по случайно выбранной исходящей ссылке, и с вероятностью 1-d закрываем текущую страницу и открываем случайно выбранную.

Разработав PageRank и основав Google, Брин и Пейдж бросили аспирантуру дальнейшие математические изыскания им уже не были интересны. Однако вычисление PageRank ставит нетривиальную математическую задачу: у нас есть система из N линейных уравнений с N неизвестными. В 1998 N исчислялся в миллионах, сегодня в миллиардах. Как решать систему уравнений с десятком миллиардов неизвестных?

Все мы учили в школе алгоритм исключения неизвестных по одной: подставим выражение для PR(p_N) во все остальные уравнения, получим систему из N-1 уравнений с N-1 неизвестными, и так далее. Этот метод решения системы уравнений прост как пробка, но у него есть пара проблем:

Во-первых, подстановка одного выражения в одно уравнение это O(N) умножений рациональных чисел. Значит, полное исключение одной неизвестной это O(N^2) умножений, а всё решение целиком это O(N^3) умножений. Когда N исчисляется в миллиардах, то O(N^3) последовательных умножений займут дольше, чем остаётся существовать нашей планете до того, как Солнце расширится и поглотит её. Дольше где-то в десять тысяч раз.

К счастью, на каждую страницу в интернете ведут совсем немного входящих ссылок не миллиард и даже не миллион. На популярную статью в Википедии могут ссылаться десятки тысяч страниц, на эту статью на Хабре хорошо если десятки. Иными словами, почти все коэффициенты в системе уравнений интернета нули. Каждый ненулевой коэффициент подвергнется O(N) умножениям при подстановке содержащего его уравнения во все остальные. Если обозначить число ненулевых коэффициентов как m, то всё решение потребует O(N\cdot m) умножений; в худшем случае m=O(N^2), но в случае интернета m=o(N^2), и для всех умножений хватит десятка-другого тысяч лет компьютерного времени. Если построить распределённую систему из миллиона-другого серверов, как у Google, то система уравнений интернета решится за неделю. До распространения криптовалют можно было с уверенностью сказать, что большая часть вычислительных ресурсов планеты идёт на решение систем уравнений.

Во-вторых, решение последнего уравнения будет результатом цепочки из O(N\cdot m) умножений и сложений рациональных чисел. Нам либо потребуется O(N\cdot m) битов для точного представления этого результата (и каждого из промежуточных), либо результат каждой операции придётся округлять до O(1) значащих битов. Накапливающиеся так ошибки округления способны исказить решение системы уравнений до неузнаваемости. Google может довольствоваться неточными значениями PageRank, но математикам нужны хоть какие-то гарантии точности например, что в найденных значениях неизвестных будет по стольку же верных битов, как в коэффициентах системы.

Из школьного метода решения системы уравнений большего не выжать. Первокурсников учат более продвинутому матричному методу: систему PageRank можно записать в виде

\begin{bmatrix} 1 & -d\frac{M(p_2,p_1)}{L(p_2)} & \cdots & -d\frac{M(p_N,p_1)}{L(p_N)} \\ -d\frac{M(p_1,p_2)}{L(p_1)} & 1 & \cdots & -d\frac{M(p_N,p_2)}{L(p_N)} \\ \vdots & \vdots & \ddots & \vdots \\ -d\frac{M(p_1,p_N)}{L(p_1)} & -d\frac{M(p_2,p_N)}{L(p_2)} & \cdots & 1 \end{bmatrix}\cdot \begin{bmatrix} PR(p_1) \\ PR(p_2) \\ \vdots \\ PR(p_N) \end{bmatrix}=\frac{1-d}{N} \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}

или в ещё более общем виде: A\cdot x=b, и тогда вектор неизвестных выражается как x=A^{-1}\cdot b. Иными словами, решение системы уравнений сводится к обращению матрицы коэффициентов и умножению обратной матрицы на вектор свободных членов.

Сам по себе матричный метод не даёт по сравнению со школьным ни большей скорости, ни большей точности: для обращения матриц тем способом, которому учат студентов, требуются всё те же O(N^3) умножений коэффициентов. За рамками вузовской программы, однако, существуют более эффективные методы: с 2005 известен вероятностный, а с 2019 детерминированный алгоритм точного решения системы уравнений за O(\log^2 N) перемножений матриц N\times N, и открытым остаётся вопрос об оптимальном алгоритме перемножения матриц. Лобовой способ («строка на столбец») требует O(N^3) умножений; алгоритм Штрассена (1969) O(N^{2.807}); алгоритм Копперсмита—Винограда (1987) O(N^{2.376}); его усовершенствования (последнее в 2020) до O(N^{2.373}). Поскольку \log N=o(N^s) для любого s>0, то множитель O(\log^2 N) не влияет на итоговую асимптотическую сложность решения системы уравнений; она получается равной асимптотической сложности умножения матриц. Само по себе умножение матриц настолько часто встречающаяся практическая задача, что поиск для неё оптимального алгоритма интересовал всех и безотносительно решения систем уравнений: например, усовершенствование в 2020 позволило уменьшить степень асимптотической сложности меньше чем на 0.00001, и всё равно считается важным достижением. Равенство сложности решения системы уравнений, т.е. обращения матрицы, со сложностью умножения матриц принималось как данность: оптимизация решения одной из этих задач казалась равносильной оптимизации решения второй.

Для практических целей алгоритм КопперсмитаВинограда, и тем более его усовершенствованные варианты, неприменимы: такие алгоритмы прозвали «галактическими», потому что вся Земля слишком мала для хранения матриц таких размеров, на которых эти алгоритмы дадут выигрыш в скорости по сравнению с более простыми. На практике самым важным оказывается частный случай, когда перемножаемые или обращаемые матрицы разрежены почти все их элементы равны нулю, как и в матрице PageRank. Алгоритм умножения разреженных матриц, опубликованный в 2005, требует O(m^{0.7}N^{1.2}+N^{2+o(1)}) операций, и обгоняет КопперсмитаВинограда при m=o(N^{1.6}); а вот для обращения разреженных матриц не было известно более эффективных алгоритмов, чем для произвольных. Отчасти это связано с тем, что матрица, обратная разреженной, сама не будет разреженной, и на практике её будет просто негде сохранить.

Недавно на Хабре была опубликована заметка (с байками про рога и копыта, но без объяснения технической стороны вопроса) о том, что оба названных «психологических барьера» сломлены Сантошем Вемпалой и Ричардом Пенгом парой математиков из Технологического института Джорджии, чья работа на ACM-SIAM Symposium on Discrete Algorithms в январе 2021 была признана лучшей из 637 поданных. Для системы уравнений с m=O(N) их алгоритм находит точное решение за O(N^{2.332}) операций, опережая степень асимптотической сложности умножения матриц на 0.04. Как мы помним, «школьный» метод исключения неизвестных по одной при условии m=O(N) приходит к ответу за O(N^2) операций, но не гарантирует точность найденных значений неизвестных. В основе нового алгоритма вероятностный подход: значения неизвестных «угадываются», оценивается величина ошибки, и «угадывание» повторяется более прицельно. Таким образом, оценка сложности в O(N^{2.332}) относится к «наиболее вероятным» случаям, а не к худшим. Другое новшество в алгоритме то, что на каждой итерации оцениваются сразу несколько случайных «догадок», что позволяет сократить общее число итераций и тем самым сдержать рост размера точных результатов.

Нужно понимать, что алгоритм Вемпалы и Пенга на одном из этапов пользуется алгоритмом КопперсмитаВинограда для умножения матриц и поэтому новый алгоритм ещё более «галактический». Важность алгоритма Вемпалы и Пенга совсем не в практической применимости, а в доказательстве того, что сложность решения систем уравнений не ограничена сложностью умножения матриц, а значит, новые эффективные алгоритмы для решения разреженных систем уравнений стоит искать в других направлениях и они гарантированно найдутся. Но ни новый алгоритм, ни другие математические достижения последнего полувека никак не повлияли на практически применимые способы решения систем уравнений: Google и все остальные так и продолжат пользоваться простым, быстрым и неточным итеративным способом.


Наши серверы можно использовать для любых вычислений.

Зарегистрируйтесь по ссылке выше или кликнув на баннер и получите 10% скидку на первый месяц аренды сервера любой конфигурации!




Комментарии (11):

  1. ComodoHacker
    /#22936526

    Спасибо, что выбираете для своего блога качественный контент, а не кликбейт!

  2. Vsevo10d
    /#22937108

    К счастью, на каждую страницу в интернете ведут совсем немного входящих ссылок — не миллиард и даже не миллион. На популярную статью в Википедии могут ссылаться десятки тысяч страниц, на эту статью на Хабре — хорошо если десятки. Иными словами, почти все коэффициенты в системе уравнений интернета — нули. Каждый ненулевой коэффициент подвергнется O(N) умножениям при подстановке содержащего его уравнения во все остальные.


    Значит ли это, что в предельном случае (нереально огромного числа ссылок на ресурс) случайно наткнуться на него в Интернете будет быстрее, чем его нагуглить??

    • vectorplus
      /#22938758

      Предельный случай это если на каждой странице в интернете будет ссылка. Но тогда вероятность будет d*1/L(p), где d это вероятность того, что юзер кликнет по ссылке, L(p) это количество ссылок на странице p. То есть сильно меньше единицы.
      Стопроцентная вероятность будет только если каждая страница в интернете будет содержать только одну ссылку, и это будет ссылка на страницу р. При этом должна отсутствовать возможность закрыть браузер или набрать другой адрес.

  3. malkovsky
    /#22937380 / +1

    Важность алгоритма Вемпалы и Пенга совсем не в практической применимости, а в доказательстве того, что сложность решения систем уравнений не ограничена сложностью умножения матриц

    С чего такой вывод? В статье улучшение только частного случая (в абстракте более точно указана привязка количества ненулевых элементов к числу обусловленности).
    Но ни новый алгоритм, ни другие математические достижения последнего полувека никак не повлияли на практически применимые способы решения систем уравнений: Google и все остальные так и продолжат пользоваться простым, быстрым и неточным итеративным способом.

    Мое сугубо субъективное мнение: вы написали статью по теме, в которой не понимаете почти ничего. «Простой, быстрый и неточный итеративный способ» изучен в математике не меньше, чем алгоритмы умножения матриц. Да даже хотя бы в аннотации к статье, которую вы пересказываете, заявлено, что используется блочный метод Крылова, который, не поверите, основывается на итеративном методе. Полагать, что гугл никак не улучшил у себя метод простой итерации было бы довольно наивно.
    Все мы учили в школе алгоритм исключения неизвестных по одной
    Это между прочим именной метод

    • Ag47
      /#22937576 / +3

      У вас ссылка на метод решения системы неравенств. Если говорить, про уравнения, то это метод Гаусса

      • malkovsky
        /#22937866

        Метод, который упомянут в статье — «взять переменную, выразить из одного из уравнений и подставить в другие». Метод Гаусса — приведение к треугольному виду.

        UPD. Технически это наверно эквивалентно, но я первый раз вижу, чтобы это подавалось с такой стороны

    • vildeste
      /#22938276

      В статье улучшение только частного случая (в абстракте более точно указана привязка количества ненулевых элементов к числу обусловленности).

      В посте ровно это и написано: «Для системы уравнений с их алгоритм находит точное решение за операций, опережая степень асимптотической сложности умножения матриц на 0.04.»

      Это между прочим именной метод

      У нас в школе, когда его учат, точно не упоминают ни Гаусса, ни Фурье, ни Моцкина.
      Может быть, в англоязычных школах кого-то из них упоминают, но сомневаюсь.

  4. z0ic
    /#22938280

    Может они по дереву проходят начиная со страниц с нулевым числом входящих ссылок. Таким образом можно делать перерасчёт только в сегментах с изменёнными входными данными. В мире САПР тоже была дилемма система или дерево, все выбрали дерево оставив систему только для простейшей двухмерной геометрии.

    • vildeste
      /#22938296

      Это не дерево: циклы из ссылок встречаются практически на каждом сайте.

      • funca
        /#22938542

        Может анализируют не весь кластер целиком, а разбивают на сегменты? Можно предположить например, что русскоязычный контент и скажем, хинди, вряд-ли имеют много пересечений. Да и с точки зрения пользовательского опыта у них не стоит задачи сделать абсолютный рейтинг, а всего-лишь отсортировать выдачу.