DDA without void dipoles

[GoogleCodeExporter]

There exist ( http://dx.doi.org/10.1175/2009JAS3146.1 ) non-FFT based
version of DDA, which does not use void dipoles. Green's tensor is not
stored, but recomputed at each iteration. This DDA version generally
requires less memory (proportional to number of dipoles for any geometry)
but more computational time. For very sparse aggregates it becomes clearly
superior (when number of dipoles is not very large). 

It is worth thinking about it. Moreover, it can be a first step to
implement Fast Multipole Method, which further optimizes speed in such DDA
version.

This is also in line with recent ADDA command line option (-opt), which
allows one to choose between optimization for speed or memory. The new DDA
version can be used for extreme memory optimization.

Moreover, this can be considered as the ultimate version of multi-grid DDA
(issue 48) where each dipoles is considered as a separate grid. The
principal difference is that multi-grid assumes pre-computation of Green's
tensor, leading to larger memory requirements.

Original issue reported on code.google.com by yurkin on 7 Jun 2010 at 6:11

[GoogleCodeExporter]

Original comment by yurkin on 7 Jun 2010 at 6:12

• Added labels: Component-Logic

[GoogleCodeExporter]

Concerning the Fast Multipole Method (FMM), there are some important things to 
keep in mind. Application of FMM for the DDA is very poorly studied, however 
some insights can be obtained from literature on FMM applied to 
surface-integral equation (which now keeps the world record in simulated size 
of particles about 400 wavelengths).

There are two versions of FMM - single-level and multilevel, which scale as 
N^1.5 and N*logN respectively (N - number of dipoles). The standard FFT-DDA 
scales as N*logN (with a lower prefactor), so multilevel FMM seems to be a nice 
option for porous particles, etc. The problem is that multilevel FMM is very 
complex by itself, and almost impossible to effectively parallelize for larger 
than 16 or 32 cores. Single-level FMM can be effectively parallelized up to 
1024 cores and beyond, but its scaling is less favorable.

So for applications involving large particles and large computer clusters, the 
boundary between suitability of standard FFT-DDA and FMM (single-level 
remaining the only option) shifts to more porous particles. However, there are 
definitely some applications where even single-level FMM can be superior. 
Consider, e.g., a fractal aggregate with a large number of monomers n=O(R^Df), 
where R is outer radius, and Df is fractal dimension. Then standard FFT-DDA 
scales as O(R^3)=O[n^(3/Df)] and single-level FMM - as O(n^1.5). So for Df<2 
(which is often the case is real applications) FMM will be better.

Original comment by yurkin on 3 Dec 2010 at 4:53

[GoogleCodeExporter]

Development of sparse (non-FFT) implementation of the DDA was started (some 
time ago) by Jussi Leinonen on a branch 'sparse' - 
http://code.google.com/p/a-dda/source/browse/#svn/branches/sparse . See r1078 - 
r1080.

Original comment by yurkin on 4 Jun 2012 at 3:58

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

The sparse mode is now included as an experimental feature. See 
http://code.google.com/p/a-dda/wiki/UsingADDAInSparseMode for more information.

Original comment by jsleino...@gmail.com on 22 Nov 2012 at 10:38

[GoogleCodeExporter]

The wiki page, mentioned in previous comment was renamed to SparseMode.

The next big thing for the sparse mode is the GPU acceleration, using OpenCL. 
Since FFT is not used in sparse mode, the potential of acceleration is even 
greater than for the standard mode.

Original comment by yurkin on 31 Jan 2013 at 7:00

• Added labels: Priority-Medium
• Removed labels: Priority-Low

[GoogleCodeExporter]

Another interesting idea is to enable storing of interaction matrix (through a 
command line option). This will accelerate computations (at least for 
non-trivial interaction methods) at the expense of a lot of memory. This may be 
relevant in some cases. Moreover, it can be controlled by command line option 
'-opt {speed|mem}'.

Original comment by yurkin on 4 Feb 2013 at 6:02

• Added labels: Sparse

[GoogleCodeExporter]

Original comment by yurkin on 2 Jul 2014 at 8:41