<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Dear Dune-Developers,<br>
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. <br>
<br>
The basic idea behind his implementation is based on a mapping from
a k-d-tree (
<meta http-equiv="content-type" content="text/html;
charset=ISO-8859-1">
<a href="http://en.wikipedia.org/wiki/K-d_tree">http://en.wikipedia.org/wiki/K-d_tree</a>)
to grid vertices and their elements.<br>
Independent of the underlying grid view (hierarchic or leaf), this
tree structure needs to do only __very__ few transformations from
global to local coordinates.<br>
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.<br>
<br>
Of course there are also (small :P) drawbacks compared to the
hierarchic search:<br>
1. The k-d-tree structure needs memory<br>
2. The k-d-tree needs to be built (but only once;-)) <br>
<br>
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.<br>
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). <br>
<br>
If you are interested in such a contribution, we are willing to
spend some more effort making things "look like dune code" ;-)<br>
If there are questions, feel free to ask!<br>
If you want to have a look at the code you can find it on:
<meta http-equiv="content-type" content="text/html;
charset=ISO-8859-1">
<a href="https://gitorious.org/dune-evalview">https://gitorious.org/dune-evalview</a><br>
<br>
Kind regards,<br>
Martin Rueckl, Malik Kirchner<br>
</body>
</html>