adda
adda copied to clipboard
adda-team
Multi-grid DDA
Implement multi-grid DDA, according to the ideas of Vitezslav Karasek, for
simulation of clusters of particles, which are at considerable distances
from each other.
Original issue reported on code.google.com by yurkin on 24 Dec 2008 at 7:34
the estimate of reduction of memory usage by using several grids has to be made
assuming several configurations for distant particles.
Original comment by [email protected] on 21 Apr 2009 at 10:14
I've made a quick estimate for memory and computational time, assuming m
particles,
each on its own cubical grid with n dipoles. If one wants to embed it into one
grid,
it will require N dipoles. Presumably N >> nm.
The interaction matrix is symmetric with m*m blocks. Each of the blocks is
stored as
its Fourier transform requiring 8n complex numbers. Total: 4nm(m+1) instead of
8N for
a single-grid DDA.
Matrix-vector product complexity: 1) Fourier transform of dipole polarizations
forward and backward - 2Xnm*log(nm), where X - constant depending on a
particular FFT
implementation. 2) Element-wise multiplication of Fourier transforms of blocks
of
interaction matrix (computed once during the initialization) by Fourier
transforms of
dipole polarizations - Y*8n*m^2, where Y - approximate time for multiplication
and
addition.
Total: 2nm[X*log(nm)+4Ym] instead of 2N[X*logN+4Y] for a single-grid DDA
From this we can see that if N > n*m^2 (i.e. porosity - nm/N - is smaller than
1/m),
then multi-grid is clearly preferential. However, even when this is not true,
multi-grid may be faster at the expense of larger memory footprint (depending on
constants X and Y).
I also foresee one difficulty in implementation of multi-grid DDA, that is
problems
with parallelizing (ensuring at least primitive load balancing).
Original comment by yurkin on 22 Apr 2009 at 5:42
The relevant references are:
- V. Karasek, O. Brzobohaty, and P. Zemanek, “Longitudinal optical binding of several spherical particles studied by the coupled dipole method,” J. Opt. A 11, 034009 (2009).
- V. Karasek, K. Dholakia, and P. Zemanek, “Analysis of optical binding in one dimension,” Appl. Phys. B 84, 149–156 (2006).
Another acceleration method for such problems is using multi-level fast-multipole algorithm to compute interaction between different particles (and keep FFT for internal calculations), see De Zaeytijd J., Bogaert I., and Franchois A. An efficient hybrid MLFMA–FFT solver for the volume integral equation in case of sparse 3D inhomogeneous dielectric scatterers, J. Comput. Phys. 227, 7052–7068 (2008).