archives

Greengard's N-body Algorithm is not order N


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Aluru, Srinivas (1993) Greengard's N-body Algorithm is not order N. Technical Report TR93-29, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

Greengard's N-Body Algorithm is Not Order N
Srinivas Aluru
Ames Laboratory, Iowa State University, Ames, IA 50011.
Abstract:
Greengard's N-body algorithm claims to compute the pairwise interactions in a
system of N particles in O(N) time for a fixed precision. In this paper,
we show that the choice of precision is not independent of N and has a
lower bound of log N. We use this result to show that Greengard's algorithm
is not O(N).

Subjects:All uncategorized technical reports
ID code:00000063
Deposited by:Staff Account on 30 December 1993



Contact site administrator at: ssg@cs.iastate.edu