Об оценках вычислительной сложности и погрешности быстрого алгоритма в методе вихревых элементов

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

метод вихревых элементов, закон Био - Савара, вязкая жидкость, диффузионная скорость, алгоритм Барнса - Хата, быстрый мультипольный метод, вычислительная сложность, оценка погрешности

1. A.J. Chorin, Numerical study of slightly viscous flow, J. Fluid. Mech., 57 (1973), pp. 785–796.

2. P. Degond, and S. Mas-Gallic, The weighted particle method for convection-diffusion equations. Part I: The case of an isotropic viscosity, Math. Comp., 53 (1989), pp. 485–507.

3. Ogami Y., Akamatsu T. Viscous flow simulation using the discrete vortex model — the diffusion velocity method // Computers and Fluids. 1991. V. 19, N 3/4. P. 433–441.

4. Дынникова Г.Я. Лагранжев подход к решению нестационарных уравнений Навье – Стокса // Доклады Академии наук. 2004. Т. 399, №1. С. 42–46.

5. S. Guvernyuk, and G. Dynnikova, Modeling the ow past an oscillating airfoil by the method of viscous vortex domains, Fluid Dynamics, 42 (2007), pp. 1–11.

6. I. K. Lifanov, and S. M. Belotserkovskii, Methods of Discrete Vortices. CRC Press, 1993.

7. S. N. Kempka, M. W. Glass, J. S. Peery, and J. H. Strickland, Accuracy Considerations for Implementing Velocity Boundary Conditions in Vorticity Formulations. SANDIA Report SAND96-0583, 1996.

8. K. S. Kuzmina, and I. K. Marchevsky The Modified Numerical Scheme for 2D Flow-Structure Interaction Simulation Using Meshless Vortex Element Method, in Proc. IV Int. Conference on Particle-based Methods — Fundamentals and Applications (PARTICLES-2015), Barcelona (2015), pp. 680–691.

9. J. Barnes, and P. Hut, A hierarchical O(N log⁡N) force-calculation algorithm, Nature, 324 (1986), pp. 446–449.

10. Дынникова Г.Я. Использование быстрого метода решения «задачи N тел» при вихревом моделировании течений // Журнал вычислительной математики и математической физики. 2009. Т. 49, № 8. С. 1458–1465.

11. Гирча А.И. Быстрый алгоритм решения «задачи N тел» в контексте численного методя вязких вихревых доменов // Информационные технологии моделирования и управления. 2008. № 1. С. 47–52.

12. Морева В.С. Способы ускорения вычислений в методе вихревых элементов // Вестн. Моск. гос. техн. ун-та им. Н.Э. Баумана. Сер.: Естественные науки. Спец. выпуск «Прикладная математика». 2011. С. 83–95.

13. Кузьмина К.С., Марчевский И.К. Оценка трудоемкости быстрого метода расчета вихревого влияния в методе вихревых элементов // Наука и образование: электрон. науч.-техн. изд. 2013. № 10. С. 399–414.

14. A. Grama, V. Sarin, and A. Sameh, Improving Error Bounds for Multipole-Based Treecodes, SIAM J. Sci. Comp., 21 (2000), pp. 1790–1803.

15. J. K. Salmon, and M. S. Warren, Skeletons from the treecode closet, J. Comput. Phys., 111 (1994), pp. 136–155.