Как новый алгоритм преодолевает ограничение скорости решения линейных уравнений

Сантош Вемпала и Ричард Пенг из Технологического института Джорджии, придумали новый, более быстрый способ решения некоторых систем линейных уравнений, «рабочую лошадку современных вычислений». Используя случайность, новый алгоритм предлагает принципиально новый — и более быстрый — способ выполнения одного из самых простых вычислений в математике и информатике.

Учащиеся начальной школы на уроках математики, вероятно, сталкиваются с учителями, которые предостерегают их от простого угадывания ответа при решении задачи. Но новое доказательство показывает, что на самом деле правильное предположение иногда бывает лучшим способом решения систем линейных уравнений (одно из фундаментальных вычислений в математике).

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

«Это одна из самых фундаментальных вычислительных задач, — сказал Марк Гисбрехт из Университета Ватерлоо. — Теперь у нас есть доказательство того, что мы можем вычислять быстрее».

Новый метод, предложенный Ричардом Пенгом и Сантошем Вемпала из Технологического института Джорджии, был опубликован в июле и представлен в январе на ежегодном симпозиуме ACM-SIAM по дискретным алгоритмам, где он получил награду за лучшую работу. 

Линейные системы включают в себя два или более уравнений с переменными, которые показывают различные способы отношения между элементами. Системы «линейны», так как единственная допустимая степень в точности равна 1, а графики решений уравнений образуют плоскости.

Типичный пример линейной системы — также, вероятно, знакомый студентам-математикам — включает в себя скотный двор, заполненный курами и свиньями. Сколько там кур и свиней, если известно, что имеется 10 голов и 30 ног? По мере изучения алгебры студенты знакомятся с определённой процедурой решения этой задачи: записать систему из двух алгебраических уравнений и решить её. 

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

«Линейные системы — рабочая лошадка современных вычислений», — считает Вемпала.

В новом доказательстве найден более быстрый способ решения большого класса линейных систем, обходя один из основных методов, обычно используемых в этом процессе. Этот метод, называемый матричным умножением, ранее установил жёсткое ограничение скорости вычисления линейных систем. Он по-прежнему используется в данной работе, но в дополнительной роли. Авторы связывают его с новым подходом, который, по сути, является формой обученного гадания.

«Вы можете угадать свой путь к решениям», — сказал Пенг. И ни один учитель не рассердится на вас за это.

Математика скотного двора

Чтобы получить представление о линейных системах и способах их решения, давайте вернёмся на скотный двор, но представим, что теперь это больше похоже на зверинец: куры, однорогие носороги и двурогие козы. Вы делаете быстрый подсчёт и определяете, что имеется 12 голов, 38 ног и 10 рогов. Можете ли вы выяснить, сколько там животных каждого вида?

Чтобы продолжить, назначьте переменную каждому виду животных (c — для кур, r — для носорогов, g — для коз) и напишите уравнение для каждого признака. Числа, или коэффициенты, перед каждой переменной отражают количественную характеристику признака, которым обладает каждое животное.

Теперь у вас есть три уравнения и три неизвестных.

Один из способов их решения — это преобразовать одно уравнение, выразив одну переменную через две другие. Например, 0c + 1r + 2g = 10 превращается в r = 10 – 2g. Подставьте это выражение вместо r в два других уравнения и продолжите эту процедуру, пока все переменные не будут определены в терминах всего одной переменной, для которой можно найти точное решение. Затем вы можете повторить этот процесс, используя найденную переменную, чтобы найти решение для следующей переменной.

Ещё один, более сложный, способ поиска решения — создать матрицу, элементами которой служат коэффициенты уравнений. Три уравнения превращаются в эту матрицу. 

Далее неизвестное количество кур, носорогов и коз мы представляем другой матрицей.

Наконец, мы представляем наблюдаемое количество голов, ног и рогов третьей матрицей.

Мы можем объединить эти три матрицы в единую линейную систему, где первая матрица, умноженная на матрицу с переменными элементами, равна третьей матрице — в этот момент мы можем найти решение для второй матрицы с помощью линейной алгебры. 

При преобразовании уравнений или использовании матричного подхода, в конечном счёте, для решения задачи выполняется одно и то же общее количество вычислительных шагов. Это число равно количеству переменных системы в кубе (n³). В этом случае у нас три переменных, так что решение занимает 3³ = 27 вычислительных шагов. Если бы у нас было четыре вида животных и четыре уравнения, для решения задачи потребовалось бы 4³ = 64 шага.

За последние 50 лет исследователи нашли способы более эффективного выполнения этой процедуры. Часто можно применять более короткие пути — способы повторного использования или комбинирования операций, которые позволяют решать линейные системы за меньшее количество шагов.

В конечном счёте всё сводится к тому, что решение любой линейной системы можно свести к матричному умножению, которое на данный момент, по крайней мере теоретически, можно выполнить за n^2,37286 шагов.

В различных технических применениях требуется решать линейные системы еще быстрее — потенциально за n² шагов. Мы используем матричное умножение, потому что это лучший доступный инструмент, но это не означает, что своего открытия не ожидает ещё лучший инструмент. 

«Нет никаких причин для того, чтобы эта проблема решения линейных систем зависела от улучшений матричного умножения», — сообщил Вемпала.

Угадывание решений

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

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

«При решении реальных научных вычислительных задач люди проявляют очень хорошую интуицию, относительно того, какими должны быть ответы», — сказал Пенг.

Итеративные методы полезны в конкретных случаях, когда интуиция может оказать некоторую поддержку. Они также полезны в более общем случае, когда линейная система, которую вы пытаетесь решить, имеет большое количество переменных, коэффициенты при которых равны нулю.

Эта особенность присутствует — и полезна — в примере со скотным двором, где самый простой признак, используемый при решении, — рога. Почему? Поскольку у цыплят нет рогов, член в уравнении, соответствующий цыплятам, исчезает, и задача с тремя видами животных сводится к задаче фактически для двух переменных. Убрав рога из расчётов, вы можете с помощью полученной информации быстро решить уравнения для ног и голов. 

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

«Это работает только в случае достаточно разреженных матриц», — сказал Уильямс.

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

Согласованная случайность

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

«Именно параллелизм отвечает за волшебство», — отметил Гисбрехт. 

Может показаться очевидной польза сортировки нескольких одновременных догадок, но это усложняет работу стратегии. Эффективность нового алгоритма во многом зависит от умения делать первоначальные догадки, порождающие итеративный процесс, и разумно объединять плоды параллельных догадок в один окончательный ответ.

Если вернуться к примеру скотного двора, алгоритм может сделать три первоначальных догадки, где каждая догадка — это матрица 3 на 1, определяющая количество кур, носорогов и коз. Алгоритм проверяет, насколько далека от истины каждая догадка, а затем делает новые догадки, продолжая параллельные потоки догадок.

Ключ к конечному успеху алгоритма заключается в том, что три первоначальные догадки он делает случайным образом. Случайность может показаться не очень хорошей основой для догадок, но как универсальный метод она имеет свои преимущества, особенно при решении огромных задач. А именно благодаря случайности вы не будете непроизвольно смещать свой поиск в сторону одной части задачи, потенциально пренебрегая областью, в которой находится фактическое решение. 

«Я должен убедиться, что все мои догадки достаточно случайны, чтобы охватывать все возможные комбинации, — сказал Пенг. — Это ужасный способ делать догадки, который в конечном счёте становится предпочтительным методом, поскольку задача становится очень большой».

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

«Существует согласованная случайность», — сказал Вемпала.

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

«Также покрыта вся область между двумя [догадками]», — сказал Вемпала.

Эта функция поиска гарантирует, что алгоритм где-то обнаружит решение. Но сама по себе она не определяет, что такое решение в действительности. Для этого — чтобы фактически взять решение в свои руки — Пенг и Вемпала должны доказать кое-что ещё.

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

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

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

По теме:

1. Mathematicians Discover the Perfect Way to Multiply

2. On Your Mark, Get Set, Multiply

3. A New Approach to Multiplication Opens the Door to Better Quantum Computers

«Нам пришлось контролировать, насколько велико появляющееся число, когда мы делаем эту догадку и координацию», — сказал Пенг. 

Пенг и Вемпала доказывают, что их алгоритм может найти решение любой разреженной линейной системы за n^2,332 шагов. Этот результат превосходит показатель степени для лучшего алгоритма матричного умножения (n^2,37286) примерно на четыре сотых. Это небольшое улучшение матричного умножения в ближайшее время не будет иметь значения для практических применений, но как доказательство правильности концепции оно представляет собой целую пропасть: оно показывает, что есть качественно лучший способ решения линейных систем.

«С философской точки зрения, мы раньше не знали, есть ли способ вычислений, более быстрый, чем матричное умножение», — сказал Вемпала. Но теперь мы знаем.

А если вам хочется подтянуть свои знания алгоритмов или математики — то будем рады видеть вас в числе наших студентов на курсах "Алгоритмы и структуры данных" и "Математика для Data Science". Возможно, именно вы создадите алгоритм, который поставит новый рекорд скорости вычислений.

Узнайте, как прокачаться в других специальностях или освоить их с нуля:

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering