Сети окружают нас повсюду. Они соединяют компьютеры в интернете, передают электричество, описывают транспортные маршруты и помогают распределять заказы между водителями или вычислительные задачи между серверами.
Чем больше такая сеть, тем сложнее выполнять связанные с ней расчеты. Если система содержит миллионы или даже миллиарды соединений, обычные методы могут требовать слишком много времени и памяти. Инженеры ищут способы сделать такие вычисления быстрее.
Один из подходов связан с так называемыми лапласовскими уравнениями. Они используются для описания различных сетевых процессов, в том числе распределения потоков и электричества.
Проблема возникает при упрощении сети. Исследователи удаляют узлы один за другим, но после каждого удаления между оставшимися узлами появляются новые связи. Их количество быстро растет, поэтому вычисления становятся все тяжелее.
Метод Approximate Cholesky предлагает не учитывать абсолютно все новые соединения. Вместо этого алгоритм выбирает небольшую случайную выборку. По словам исследователей, ее достаточно, чтобы получить почти тот же результат, что и при полном расчете, но затратить значительно меньше ресурсов.
Оставшиеся ошибки можно исправлять постепенно. Система проверяет решение и уточняет его до тех пор, пока не будет достигнута нужная точность.
В новой работе ученые превратили этот математический подход в работающий программный прототип. В тестах он оказался примерно в пять раз быстрее прежних решений и смог справиться с некоторыми задачами, на которых существующее программное обеспечение не работало.
При этом случайность здесь не мешает вычислениям, а, наоборот, помогает их ускорить. Алгоритм отбрасывает часть информации, которая несущественна для итогового результата, и сохраняет главное.
Исследователи продолжают развивать метод в открытом проекте, их цель — создать надежное программное обеспечение для научных расчетов на суперкомпьютерах. Работа показывает, как сложная математическая идея постепенно превращается в практический инструмент для анализа сетей, которые раньше было слишком трудно обрабатывать.
Читайте также:
ИИ научился по сигналам мозга понимать, что человек имел в виду
Атом одновременно падал и оставался на месте — физики проверили границу квантового мира