Universität zu Köln

Hachul, Stefan and Jünger, Michael (2006). A Provably Fast Multipole Method. Working Paper.

Preview

PDF zaik2006-518.pdf Download (2MB) | Preview

Abstract

The evaluation of potential or force fields in systems of N particles whose interactions are Coulombic or gravitational is very important for several applications in natural science, applied mathematics, and computer science. A naive direct calculation of the interactions needs Theta(N^2) time per time step which is inappropriate for large systems.Therefore, fast hierarchical algorithms (called tree codes) are used that approximate the pairwise interactions in the systems. We present a new multipole-based tree code that runs in O(N) time in the best case and in O(N log N) time in the worst case. This is an improvement in comparison with existing tree codes: Few of them run in Theta(N log N) time. Others are O(N) or O(N log N) in the best case but quadratic or even unbounded in the worst case. Our practical experiments indicate that the new multipole method is faster than several popular hierarchical N -body simulation algorithms for both uniform and highly non-uniform particle distributions.

Item Type:	Preprints, Working Papers or Reports (Working Paper)
Creators:	Creators Email ORCID ORCID Put Code Hachul, Stefan UNSPECIFIED UNSPECIFIED UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548964
Date:	2006
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54896