On the estimations of efficiency and error of fast algorithm in vortex element method

The main computational complexity of vortex methods is concentrated in the calculation of the convective and diffusive velocities of all vortex elements. The analogue of the Barnes - Hut algorithm is considered as one of the most efficient ways to acceleration of the velocities computation in vortex element method. This method is based on the tree (hierarchical structure of regions) construction. When calculating the convective velocities this algorithm makes it possible to take into account the influence of vortex elements, which are located far enough from each other, approximately by using Taylor approximation of expression for convective velocity. The influence of vortex elements, which are close to each other is calculated directly using Biot -Savart law. There are two parameters of algorithm that affect the computational complexity of the algorithm and the problem solving accuracy: is the maximum tree level, is the parameter, which determines the radius of a near-field zone. When calculating diffusive velocities the influence of the vortex elements to each other decays exponentially with increasing distance between them. Therefore, constructed algorithm of diffusive velocities calculation allows finding vortex elements from near-field zone using tree structure and calculating diffusive velocities using only vortex elements from this zone. The estimations of computational complexity, which depends on algorithm parameters and number of vortex elements, are obtained for the algorithms for convective and diffusive velocities calculation. Also estimations for the errors of the vortex elements velocities computation, which depend on the algorithm parameters, are constructed. These estimates allow in practice to choice the optimal parameters of the whole algorithm and achieve the maximum possible acceleration of the computations for the given maximum error level.

Vortex element method, Biot - Savart law, viscous flow, diffusive velocity, Barnes - Hut algorithm, fast multipole method, computational complexity, error estimation

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. Y. Ogami, and T. Akamatsu, Viscous flow simulation using the discrete vortex model - the diffusion velocity method, Computers & Fluids, 19 (1991), pp. 433-441.

4. G. Ya. Dynnikova, Lagrange method for Navier - Stokes equations solving, Doklady Akademii Nauk, 399 (2004), pp. 42-46.

5. S. Guvernyuk, and G. Dynnikova, Modeling the flow 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() force-calculation algorithm, Nature, 324 (1986), pp. 446-449.

10. G. Ya. Dynnikova, Fast technique for solving the -body problem in flow simulation by vortex methods, Computational Mathematics and Mathematical Physics, 49 (2009), pp. 1389-1396.

11. A. I. Gircha, Fast Algorithm for -body Problem Solving with Regard to Numerical Method of Viscous Vortex Domains, Informatial technologies in Simulating and Control, 1 (2008), pp. 47-52.

12. V. S. Moreva, On the Ways of Computations Acceleration when Solving 2D Aerodynamic Problems by Using Vortex Element Method, Heralds of the Bauman Moscow State University. Natural Sciences. Sp. Issue `Applied Mathematics' (2011), pp. 83-95.

13. K. S. Kuzmina, I. K. Marchevsky, Estimation of computational complexity of the fast numerical algorithm for calculating vortex influence in the vortex element method, Science & Education (electronic journal), 10 (2013), pp. 399-414 (URL: http://technomag.bmstu.ru/en/doc/604030.html)

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.