В 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% скидку на первый месяц аренды сервера любой конфигурации!