# Stanford CME 342 - Fast methods for N-body problem II (24 pages)

Previewing pages*1, 2, 23, 24*of 24 page document

**View the full content.**## Fast methods for N-body problem II

Previewing pages
*1, 2, 23, 24*
of
actual document.

**View the full content.**View Full Document

## Fast methods for N-body problem II

0 0 37 views

- Pages:
- 24
- School:
- Stanford University
- Course:
- Cme 342 - Parallel Methods in Numerical Analysis

**Unformatted text preview:**

CME342 AA220 CS238 Parallel Methods in Numerical Analysis Fast methods for N body problem II May 23 2005 Lecture 24 Particle simulations t 0 while t t final for i 1 to n n number of particles compute f i force on particle i for i 1 to n move particle i under force f i for time dt using F ma compute interesting properties of particles energy etc t t dt end while force Fexternal F neighbor F farfield O N O N O N 2 Using a classical approach this will require O N 2 operations but with a clever divide and conquer approach we can solve the problem in O N logN or O N operations Fast hierarchical methods Use of adaptive quadtree or octree to subdivide the space Barnes Hut algorithm can solve the problem in O N logN not very accurate use the center of mass and total mass Fast Multipole method can solve the problem in O N accurate use more information than BH more difficult to implement Adaptive quad tree All our algorithms begin by constructing a tree to hold all the particles Adaptive Quad Oct Tree only subdivides space where particles are located Child nodes enumerated counterclockwise from SW corner empty ones excluded Fast Multipole method A fast algorithm for particle simulation Greengard and Rokhlin J Comp Phys V 73 1987 many later papers Differences from Barnes Hut FMM computes the potential at every point not just the force FMM uses more information in each box than the CM and TM so it is both more accurate and more expensive To compensate FMM accesses a fixed set of boxes at every level independent of D r BH uses fixed information CM and TM in every box but boxes increases with accuracy FMM uses a fixed boxes but the amount of information per box increases with accuracy Fast Multipole method Use the potential instead of the force FMM uses two kinds of expansions Outer expansions represent potential outside node due to particles inside analogous to CM TM Inner expansions represent potential inside a node due to particles outside Computing these for every leaf node is the computational goal of FMM Outer expansion p 1 j 1 z M1 log z z1 z z j j 1 1 Outer n M 1 2 r zn Stores data for evaluating potential z outside node n due to particles inside n Will be computed for each node in QuadTree Cost of evaluating z is O p independent of the number of particles inside n Outer expansion needed to compute the potential away from n due to particles inside n We also want to compute potential inside n due to particles away from n Inner expansion p z c i 0 i z zc i Inner n 1 2 r zn Stores data for evaluating potential z inside node n due to particles outside n Computing this for every leaf node is the computational goal of FMM Converting Outer Expansions We want to compute Outer n cheaply from Outer c for all children of n How to combine outer expansions around different points First step make them expansions around same point n1 is a subsquare of n2 zk center nk for k 1 2 Outer n1 expansion accurate outside blue dashed square so also accurate outside black dashed square So there is an Outer n2 expansion with different ak and center z2 which represents the same potential as Outer n1 outside the black dashed box Converting outer expansions p 1 j 1 z M1 log z z1 z z j j 1 1 Given Solve for M2 and 2 in p 2 j 1 z 2 z M2 log z z2 z z j j 1 2 Get M2 M1 and each 2 is a linear combination of the 1 multiply r vector of 1 values by a fixed r by r matrix to get 2 M2 12 r2 Outer shift Outer n1 z2 desired Outer n2 Converting inner expansions How to combine inner expansions around different points First step make them expansions around same point n1 is a subsquare of n2 zk center nk for k 1 2 Inner n2 expansion accurate inside black dashed square so also accurate inside blue dashed square So there is an Inner n1 expansion with different k and center z1 which represents the same potential as Inside n2 inside the blue dashed box Converting Inner Expansions p z 1 Given i 0 i z z1 i Solve for 2 such that p i 0 2 i i z z2 p i 0 1 i z z1 i Each 2 is a linear combination of the 1 multiply p vector of 1 values by a fixed p by p matrix to get 2 12 r2 Inner shift Inner n1 z2 desired Inner n2 Converting Outer to Inner We need to show how to convert Outer n3 to Inner n4 when n4 is far enough from n3 Inner n4 0 1 r z4 Outer n3 M 1 2 r z3 p M log z z 3 3 j 1 p 3 j 4 i z z3 j i 1 z z 4 i Once again is a weighted sum Inner n4 Convert Outer n3 center n4 Top Level Description of FMM 1 Build the QuadTree 2 Call Build Outer root to compute outer expansions of each node n in the QuadTree Traverse QuadTree from bottom to top combining outer expansions of children to get out outer expansion of parent 3 Call Build Inner root to compute inner expansions of each node n in the QuadTree Traverse QuadTree from top to bottom converting outer to inner expansions and combining them 4 For each leaf node n add contributions of nearest particles directly into Inner n final Inner n is desired output expansion for potential at each point due to all particles Compute Outer n for each node Compute Outer n for each node of the QuadTree outer Build Outer root function M a1 ar zn Build Outer n compute outer expansion of node n if n if a leaf it contains 1 or a few particles compute and return Outer n M a1 ar zn directly from its definition as a sum else post order traversal process parent after all children Outer n 0 for all children c k of n k 1 2 3 4 Outer c k Build Outer c k Outer n Outer n Outer shift Outer c k center n just add component by component endfor return Outer n end if Cost O nodes in QuadTree O N same as for Barnes Hut Compute Inner from other expansions We will use Inner shift and Convert to build each Inner n by combing expansions from other nodes Which other nodes As few as necessary to compute the potential accurately Inner shift Inner parent n center n will account for potential from particles far enough away from parent red nodes below Convert Outer i center n will account for potential from particles in boxes at same level in Interaction Set Interaction set Interaction Set nodes i that are children of a …

View Full Document