Next: Rotation of coefficients Up: New FMM Previous: New FMM

## Formulation for the new FMM

Now we consider a source point located at (y1,y2,y3) and a target point at (x1,x2,x3) and denote a cell including a source point by Cs and a cell including a target point by Ct. Here we introduce the following integral representation:

 (22)

The integral in (23) converges under an assumption that the inequality x3 > y3 is valid. This is why we restrict the discussion to the case where Ct is located in +x3 direction of Cs for the present. Suppose that each of the cells Cs and Ct has a volume of d3. Then the double integral in (23) is evaluated with the following double sum:

 (23)

where is given by

is the error term and the numbers , M(k), Gaussian weights and nodes are given in Yarvin and Rokhlin[23]. One may determine these parameters considering the required accuracy.

Noting the following formulae:

and (24), one can evaluate the integral in (5) in the following manner:

where W1j(p,q) and W2(p,q) are the coefficients of the exponential expansion at O, defined as

 W1j(p,q)= (24) W2(p,q)=

and are operators defined as

These formulae (25) and (26) convert the multipole moments into the coefficients of the exponential expansion. The coefficients of the exponential expansion is translated according to the following formulae when the centre of the exponential expansion is shifted from O to :

 V1j(p,q)=W1j(p,q) (25)

where V1j(p,q) and V2(p,q) are the coefficients of the exponential expansion at and stand for the components of the vector .

We next need to convert the coefficients of the exponential expansion into the coefficients of the local expansion. Noting that the integral in (13) is evaluated with V1j(p,q) and V2(p,q)as follows:

and using (18) and the following formula:

one obtains the following formulae which converts the coefficients of the exponential expansion into the coefficient of the local expansion:

 (26)

The procedures in (25)-(30) correspond to the M2L translation expressed by (19) and (20) for the original FMM. Suppose that one truncates the infinite series in (10) taking p terms. Then the computational costs for (19) and (20) are obviously O(p4). Also, if one assumes

the computational costs for (25) and (26), (27) and (28) and (29) and (30) are O(p3), O(p2) and O(p3), respectively. Hence, the total cost for the procedures in (25)-(30) is O(p3). This is why the new FMM is faster than the original FMM.

Next: Rotation of coefficients Up: New FMM Previous: New FMM
Ken-ichi Yoshida
2001-03-26