Multi-grid DDA

[GoogleCodeExporter]

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

[GoogleCodeExporter]

the estimate of reduction of memory usage by using several grids has to be made
assuming several configurations for distant particles.

Original comment by vita...@gmail.com on 21 Apr 2009 at 10:14

[GoogleCodeExporter]

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