I detta arbete jämförs tre algoritmer för det tredimensionella N-kroppsproblemet, Barnes-Hut-algoritmen, Greengard's Fast Multipole Method (FMM) och Parallel Multipole Tree Algorithm (PMTA) för att avgöra vilken av algoritmerna som fungerar bäst i praktiken. Även om FMM har en bättre asymptotic körtid (O(N) i stället för O(N log N) för enhetliga fördelningar), algoritmen är mer komplicerad och det är inte omedelbart klart över vilka värden av N det utför bättre i praktiken. Vi studerade beroendet av noggrannhet på de variabla parametrarna, p och, och sedan jämförde oating punkt operation räknas av de tre algoritmer på liknande nivåer av noggrannhet, för både laddade och oladdade slumpmässiga fördelningar. Vid en hög grad av noggrannhet (RMS-terror 10?5 ), FMM gjorde det minsta antalet operationer för N > 10 4, förutsatt att både laddade och oladdade fördelningar av poäng. På en lägre nivå av noggrannhet, (RMS-terror 10?3 ) för oladdade distributioner, FMM inte överträffa Barnes-Hut även för N > 10 8. För laddning av partiklar var både FMM och PMTA jämförbara med låg noggrannhet. Algoritmerna genomfördes i det parallella språket Nesl.
Möjliga algoritmer för att lösa N-kroppsproblemet är Burnes-Hut (BH), Fast Multipole Method (FMM) och Parallel Multipole Tree Algorithm (PMTA) REF.
A Practical Comparison of N-Body Algorithms
{'venue': 'In Parallel Algorithms, Series in Discrete Mathematics and Theoretical Computer Science', 'journal': None, 'mag_field_of_study': ['Computer Science']}