A FAST ALGORITHM FOR CALCULATING PARTICLE INTERACTIONS IN SMOOTH PARTICLE HYDRODYNAMIC SIMULATIONS

An algorithm is presented for the rapid calculation of kernel evaluations which occur in simulations using the smooth particle hydrodynamic (SPH) method. For a system of N particles, traditional methods require an amount of work of O(N2) to calculate the interaction of each particle with every other particle, unless sorting or linked-list schemes are used, in which case the amount of work is reduced to O(N). The algorithm described here has the same amount of work to evaluate particle interactions as the linked-list method, but unlike the linked-list scheme it readily vectorizes, making it considerably more practical for large-scale problems of current interest in climatology, plasma physics, fluid dynamics and celestial mechanics.