Fast Multipole Method

 

We implement a parallel Fast Multipole Methods (FMM) based on the tree data structures available from the domain decomposition. We use FMM to estimate efficiently the far-field conditions for the multigrid solver. Moreover, FMM may be used in the multigrid solver to avoid communication between sub-domains and, therefore, between processors.

Commonly used Fast Multipole Methods were introduced by Greengard and Rokhlin (1988).

 

We consider pairwise particle interactions in a potential field of the form

\Phi(x_i)= \sum_{n=1, n \neq i}^{N} \frac{q_n}{\| x_i-x_n \|}.

 

where x_1,...,x_n are particle locations and q_1,...,q_n are charges.

 

The multipole expansion of the potential \Phi(x) at the particle position x=(r,\theta,\phi) generated by the charges q_1,..,q_N located at x_1,...,x_N  is given by Greengard and Rokhlin (1988):

 

\Phi(x_i)= \sum_{n=0}^{\infty} \sum_{m=-n}^{n} \frac{M_n^m}{r^{n+1}} \cdot Y_n^m(\theta, \phi) ,

where M_n^m are coefficients depending on the particle position  x_1,...,x_N and charges  q_1,..,q_NY_n^m are spherical harmonics of degree n and order m.

 

The evaluation of the potential involves traversing of the tree data structure and the summation of the local multipole expansions satisfying the opening angle criteria (Barnes and Hut, 1986).

There exist several approaches to compute this summation on parallel architectures (Greengard and Grop, 1990 ; Kurzak and Pettitt, 2005).

The PPM library creates one global tree data structure based on all particles that is  accessible from all processors.

Each processor computes the multipole expansions for the leaf boxes in its sub domains. A pre-traversal determines the boxes that are needed for shifting the multipole expansion to the next higher tree level and creates an interaction list. In a communication step, the necessary multipole expansions are exchanged before they are shifted. The final traversal of the tree for a target point is based on the pre-traversal interaction to reduce the amount of communication. After sending these multipole expansions to the processor containing the target point, the final evaluation of the potential is performed without communication.

 

 

Profile Information

Application afterLoad: 0.000 seconds, 0.28 MB
Application afterInitialise: 0.013 seconds, 0.93 MB
Application afterRoute: 0.016 seconds, 1.23 MB
Application afterDispatch: 0.026 seconds, 1.84 MB
Application afterRender: 0.034 seconds, 2.01 MB

Memory Usage

2135656

12 queries logged

  1. SELECT *
      FROM jos_session
      WHERE session_id = 'aluvpo7rrj8oe0hcs2jc38j5q4'
  2. DELETE
      FROM jos_session
      WHERE ( time < '1632050986' )
  3. SELECT *
      FROM jos_session
      WHERE session_id = 'aluvpo7rrj8oe0hcs2jc38j5q4'
  4. INSERT INTO `jos_session` ( `session_id`,`time`,`username`,`gid`,`guest`,`client_id` )
      VALUES ( 'aluvpo7rrj8oe0hcs2jc38j5q4','1632051886','','0','1','0' )
  5. SELECT *
      FROM jos_components
      WHERE parent = 0
  6. SELECT folder AS type, element AS name, params
      FROM jos_plugins
      WHERE published >= 1
      AND access <= 0
      ORDER BY ordering
  7. SELECT m.*, c.`option` AS component
      FROM jos_menu AS m
      LEFT JOIN jos_components AS c
      ON m.componentid = c.id
      WHERE m.published = 1
      ORDER BY m.sublevel, m.parent, m.ordering
  8. SELECT template
      FROM jos_templates_menu
      WHERE client_id = 0
      AND (menuid = 0 OR menuid = 65)
      ORDER BY menuid DESC
      LIMIT 0, 1
  9. SELECT a.*, u.name AS author, u.usertype, cc.title AS category, s.title AS section, CASE WHEN CHAR_LENGTH(a.alias) THEN CONCAT_WS(":", a.id, a.alias) ELSE a.id END AS slug, CASE WHEN CHAR_LENGTH(cc.alias) THEN CONCAT_WS(":", cc.id, cc.alias) ELSE cc.id END AS catslug, g.name AS groups, s.published AS sec_pub, cc.published AS cat_pub, s.access AS sec_access, cc.access AS cat_access 
      FROM jos_content AS a
      LEFT JOIN jos_categories AS cc
      ON cc.id = a.catid
      LEFT JOIN jos_sections AS s
      ON s.id = cc.section
      AND s.scope = "content"
      LEFT JOIN jos_users AS u
      ON u.id = a.created_by
      LEFT JOIN jos_groups AS g
      ON a.access = g.id
      WHERE a.id = 60
      AND (  ( a.created_by = 0 )    OR  ( a.state = 1
      AND ( a.publish_up = '0000-00-00 00:00:00' OR a.publish_up <= '2021-09-19 11:44:46' )
      AND ( a.publish_down = '0000-00-00 00:00:00' OR a.publish_down >= '2021-09-19 11:44:46' )   )    OR  ( a.state = -1 )  )
  10. UPDATE jos_content
      SET hits = ( hits + 1 )
      WHERE id='60'
  11. SELECT id, title, module, position, content, showtitle, control, params
      FROM jos_modules AS m
      LEFT JOIN jos_modules_menu AS mm
      ON mm.moduleid = m.id
      WHERE m.published = 1
      AND m.access <= 0
      AND m.client_id = 0
      AND ( mm.menuid = 65 OR mm.menuid = 0 )
      ORDER BY position, ordering
  12. SELECT a.*, CASE WHEN CHAR_LENGTH(a.alias) THEN CONCAT_WS(":", a.id, a.alias) ELSE a.id END AS slug, CASE WHEN CHAR_LENGTH(cc.alias) THEN CONCAT_WS(":", cc.id, cc.alias) ELSE cc.id END AS catslug
      FROM jos_content AS a
      INNER JOIN jos_categories AS cc
      ON cc.id = a.catid
      INNER JOIN jos_sections AS s
      ON s.id = a.sectionid
      WHERE a.state = 1 
      AND a.access <= 0
      AND cc.access <= 0
      AND s.access <= 0
      AND (a.publish_up = '0000-00-00 00:00:00' OR a.publish_up <= '2021-09-19 11:44:46' ) 
      AND (a.publish_down = '0000-00-00 00:00:00' OR a.publish_down >= '2021-09-19 11:44:46' )
      AND cc.id = 1
      AND cc.section = s.id
      AND cc.published = 1
      AND s.published = 1
      ORDER BY a.ordering
      LIMIT 0, 4

Language Files Loaded

Untranslated Strings Diagnostic

None

Untranslated Strings Designer

None