Разделяй и властвуй: новый способ понижения сложности вычислительных задач

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

Группа исследователей Инженерной школы Университета Вашингтона в Сент-Луисе (штат Миссури) разработала новый алгоритм решения линейных обратных задач с миллионами уравнений и переменных путём разбиения их на мелкие задачи, каждая из которых может быть решена на стандартных машинах.

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

Линейными обратными проблемами называют попытки на основе данных наблюдений найти модель, которая их объясняет. Свой фреймворк Parallel Residual Projection (PRP) для решения этого типа задач, авторы задумали когда участвовали в совершенно другой работе, помогая биологу в изучении структуры сетей нейронов, отвечающих за цикл «сон-бодрствование».

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

Это исследование, выполненное в лаборатории профессора Шин Ли (Jr-Shin Li) с факультета электро- и системотехники, представлено в статье, вышедшей 30 июля в журнале Scientific Reports.