Improving Linked-Lists Using Tree Search Algorithms for Neighbor Finding in Variable-Resolution Smoothed Particle Hydrodynamics  

作　　者：Shahab Khorasanizade J.M.M.Sousa 

机构地区：[1]IDMEC,Instituto Superior T́ecnico,Universidade de Lisboa,Av.Rovisco Pais,1049-001 Lisboa,Portugal

出　　处：《Communications in Computational Physics》2019年第6期57-86,共30页计算物理通讯（英文）

基　　金：supported by Fundacao para a Ciencia e a Tecnologia(FCT),through IDMEC,under LAETA,project UID/EMS/50022/2013;The financial support via FCT grant SFRH/BSAB/114588/2016 is also acknowledged.

摘　　要：Improving linked-lists for neighbor finding with the use of tree search algorithms is proposed here,aiming to cope with highly non-uniform resolution simulations employing a meshless method.The new procedure,coined Quadtree Cells Grid,has been implemented in Smoothed Particle Hydrodynamics(SPH).The SPH scheme employed is adaptive,thus allowing for particle refinement in desired regions of the flow.Owing to the wide range of coexisting particle mass levels,standard linked-list neighbor search algorithms become ineffective.Hence,an alternative is found based on the use of hierarchical data structures,using quadtrees(in 2D problems).The present algorithm exploits the advantages of both linked-lists and quadtree meth-ods with the goal of increasing computational efficiency,when dealing with highly non-uniform particle distributions.Test cases involving two distinct flow problems have demonstrated that the computational cost of the current adaptive neighbor finding algorithm scales linearly with the total number of particles,thus retrieving this characteristic of linkedlists in uniform grid search.Nevertheless,the memory usage increased as a result of the more complex data structure.

关 键 词：Smoothed particle hydrodynamics linked-list QUADTREE neighbor finding variable resolution 

分 类 号：O29[理学—应用数学]