Next: Rotation of coefficients
Up: New FMM
Previous: New FMM
Formulation for the new FMM
Now we consider a source point
located at
(y_{1},y_{2},y_{3}) and a target point
at
(x_{1},x_{2},x_{3}) and denote a cell including a source point by
C_{s} and a cell including a target point by C_{t}.
Here we introduce the following integral representation:
The integral in (23) converges under an assumption that the
inequality x_{3} > y_{3} is valid. This is why we restrict the discussion
to the case where C_{t} is located in +x_{3} direction of C_{s} for the
present. Suppose that each of the cells C_{s} and C_{t} has a volume of
d^{3}. Then the double integral in (23) is evaluated with
the following double sum:
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
W^{1}_{j}(p,q) and W^{2}(p,q) are the coefficients of the exponential
expansion at O, defined as
W^{1}_{j}(p,q)= 







(24) 
W^{2}(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
:
V^{1}_{j}(p,q)=W^{1}_{j}(p,q) 







(25) 





where
V^{1}_{j}(p,q) and V^{2}(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
V^{1}_{j}(p,q) and V^{2}(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:
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(p^{4}). Also, if one
assumes
the computational costs for (25) and (26), (27) and
(28) and (29) and (30) are O(p^{3}), O(p^{2}) and
O(p^{3}), respectively. Hence, the total cost for the procedures in
(25)(30) is O(p^{3}). This is why the new FMM is
faster than the original FMM.
Next: Rotation of coefficients
Up: New FMM
Previous: New FMM
Kenichi Yoshida
20010326