[Dune-devel] Contribution to Dune

[Martin Rückl]

Dear Dune-Developers,
a good friend/colleague of mine, Malik Kirchner, has developed a quite 
fast alternative to the hierarchic search provided in the grid 
utilities. He is willing to share his work to your community, but little 
afraid to do so :-). I wonder if you would appreciate such a contribution.

The basic idea behind his implementation is based on a mapping from a 
k-d-tree ( http://en.wikipedia.org/wiki/K-d_tree) to grid vertices and 
their elements.
Independent of the underlying grid view (hierarchic or leaf), this tree 
structure needs to do only __very__ few transformations from global to 
local coordinates.
Compared to the HierarchicSearch he achieved a speedup of about 10-20 
for well balanced hierarchic grids with only one element on level 0. 
Operating on leaf views a speedup of >100 can be achieved.

Of course there are also (small :P) drawbacks compared to the hierarchic 
search:
1. The k-d-tree structure needs memory
2. The k-d-tree needs to be built (but only once;-))

We have successfully tested his code, and tried to keep the interface 
similar to the HierarchicSearch. We also added a PDELab 
GridFunctionToFunctionAdaptor making use of the k-d-tree search.
While we only tested things in sequential so far, i see no reason why it 
should not run in parallel as well, since it is solely operating on a 
grid view and does not require any communication (of course you cannot 
find the entity for a coordinate if the entity resides on another rank).

If you are interested in such a contribution, we are willing to spend 
some more effort making things "look like dune code" ;-)
If there are questions, feel free to ask!
If you want to have a look at the code you can find it on: 
https://gitorious.org/dune-evalview

Kind regards,
Martin Rueckl, Malik Kirchner
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.dune-project.org/pipermail/dune-devel/attachments/20131119/f8908d64/attachment.htm>