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

В 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) — число исходящих ссылок на этой странице, а — число страниц в интернете. Таким образом PR(p_i) выражает вероятность оказаться на странице p_i при случайном брожении по интернету, когда с вероятностью мы переходим на следующую страницу по случайно выбранной исходящей ссылке, и с вероятностью 1-d — закрываем текущую страницу и открываем случайно выбранную.

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

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

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

К счастью, на каждую страницу в интернете ведут совсем немного входящих ссылок — не миллиард и даже не миллион. На популярную статью в Википедии могут ссылаться десятки тысяч страниц, на эту статью на Хабре — хорошо если десятки. Иными словами, почти все коэффициенты в системе уравнений интернета — нули. Каждый ненулевой коэффициент подвергнется O(N) умножениям при подстановке содержащего его уравнения во все остальные. Если обозначить число ненулевых коэффициентов как , то всё решение потребует $O(N\cdot m)$ умножений; в худшем случае 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» src=«https://habrastorage.org/getpro/habr/upload_files/d41/ca8/f74/d41ca8f74a853cdb222309e31e06890b.svg» />, то множитель <img alt= не влияет на итоговую асимптотическую сложность решения системы уравнений; она получается равной асимптотической сложности умножения матриц. Само по себе умножение матриц — настолько часто встречающаяся практическая задача, что поиск для неё оптимального алгоритма интересовал всех и безотносительно решения систем уравнений: например, усовершенствование в 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% скидку на первый месяц аренды сервера любой конфигурации!