[Dune] Question on parallel computation

[Aleksejs Fomins]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Dear Bernd,

So, the naive algorithm is
1) Determine all neighbours in serial mode using pairwise checking. Complexity O( n(n+1) / 2) for n elements
2) Determine all averages on the master process
2.1) All numbers get communicated to master via comm.gather
2.2) Master calculates all averages.  Complexity O(n * n_neighbor_within_radius)
2.3) Master communicates all averages to their owners via comm.scatter

My thoughts on optimization of above algorithm
1) If the radius is small compared to size of the mesh, the mesh can be placed into an OCTree. This way, first the octants get compared, and if they do not intersect, then the element pairs within them do not get checked. The complexity will be reduced to approximately O(n * n_neighbor_within_radius / 2)

2) The computation of the averages on master process can be optimized by dynamical programming. Since the sets of radius-neighbours are going to significantly overlap, then, instead of storing the set of all neighbours for each element, it makes sense to store the change of neighbours between this element and some other element close to it, perhaps one of its real neighbours, thus making sort of a tree. The complexity is going to be O(n * K), where K will be approximately (n_neighbor_within_radius)^{2/3}.

3) A different approach would be to send to each element only the values it needs to compute its own average. Then your friend is the new mpi routine MPI_Neighbor_allgather, which allows to specify in parallel the graph of communication, and then each process sends data only to its recepients. Then the computation is cheap, and this type of mpi communication is definitely scalable to very large processor number unlike the standard gather one. Unfortunately, it is still not implemented in Dune, but I have written a wrapper for one of these routines, you can have it if you want to

Greetings,
Aleksejs


On 22/04/15 15:08, Bernd Flemisch wrote:
> Dear Dune,
> 
> I want to calculate a number a_e for each element e that is the average of other numbers x_n associated with elements n that lie within a certain radius r of e:
> 
> a_e = avg ( all x_n with n such that dist(e, n) < r )
> 
> Maybe some of you already had a similar problem: How can I achieve this in MPI-parallel on a Dune grid without overlap, with maximal use of the existing Dune infrastructure?
> 
> I can think of determining all the interacting elements n for each element e sequentially on the macro grid before that is balanced over the processes. Based on that pattern, I want to calculate frequently the a_e's.
> 
> Thank you for your thoughts. Kind regards
> Bernd
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQIcBAEBAgAGBQJVN69hAAoJEDkNM7UOEwMZx7UP/1a4zbeSUbAWb/O8+IHC8fr2
LMHTCjWcF9S8OyVx57JRxjwhJTdKOlsjGh/qHyrAb1b0OT20itM6sr020UMtWGto
hdVwfq8xut1FUc9KfHregZD11UxOrM6TV3GNbz7VYAm78h2TPXC50LFdu8egswqJ
aVss5y2fpqVM4TZ9yD52O6Cz87/xAwYgVDHBNXe7fEiWOor5YXAxniuB8EgotgM4
yXPbZLkjhMJg0rzQMgvvokXr0dzoSnEMu2ir16eUN3cng41yCmTmS18cvd2cD6E2
7m4LJOYvjpCTG3VtVlj4fDxEoBM+YMrgbbNfqeikNX41zRx56h1kpDuW2nhMIJSF
F1/1psDLIAA5AOpjzAZIkQ3sW+MGilstvU7Aa2X16teWoVEzYrC/gY0481QYHGsf
LsFzYhuEURiNxLfsJUVSYBJrAZjpY0+RlqOEulmnt4x0cUdIrkDRwD2aUmkw5ote
RHfkHhEZcj+JTxPEo93lGKWhmmQ2Nh81kmadl4Ov7pWYwDJmrQmr6UL3Kad4/HuB
9fO+YtzjiKtJIBJYDF5axt7APv2sJ277RnmBu1E51gz+kNbKLa9uiU9N8spajGdj
rPK0luOaLEsLfJY5L40+/Yd1gpWFfqy2rr4saZ1seii9QSPg259otp15UVTXn4Mv
+QiaRZ/yfDWgfqB+IUHi
=mxDK
-----END PGP SIGNATURE-----