Modification of the IDW method for numerical simulation of aerodynamics problems on large grids

Работа посвящена вопросам численного моделирования задач обтекания подвижных тел. В качестве базового подхода для расчёта выбран численный метод, основанный на методе конечных объёмов. Приводятся уравнения Навье-Стокса, описывающие течение вязкого сжимаемого газа, и схемы дискретизации. Движение границ, как правило, влечёт за собой изменение контрольных объёмов, поэтому возникает необходимость в использовании методов изменения расчётной сетки. В работе детально рассматривается IDW метод деформирования расчётных сеток. Вычислительная сложность базового метода эквивалента оценке $O\left( n_i n_b\right)$ ($n_i$ и $n_b$ – количество внутренних вершин и вершин на поверхности), что вызывает трудности использования в промышленно ориентированных задачах. Ключевым элементом ускорения процедуры изменения расчётной сетки является применение метода быстрых мультиполей. Иерархические структуры данных совместно с методами теории графов позволили снизить сложность алгоритма до $O\left(n_i log(n_b)\right)$ и обеспечить качественное деформирование расчётной сетки. Дополнительно предложен метод распределения вычислительной нагрузки, что вкупе повысило скорость работы алгоритма до 80{%} на характерных задачах авиационной промышленности.