[Dune] ANN and parameters

[Dragan Vidovic]

Dear Andreas,

What would be the key in std::map? I read my mesh from a Tetgen ele
file. The order in which mappers refer to elements is not the order
which was appears in the ele file. The node numbers were changed, but
even if I reconstruct the original node numbers and their order within
a tetrahedron, the order of tetrahedra is different. I don't know
where is this order changed, for me this is a random permutation and
this is why I need the nearest neighbor search. The only way for me to
refer to the parameters is trough the centroid coordinates. Another
option is to reconstruct the original nodes order, but I think this is
harder. I noticed that the centroid that the mapper gives (from
Alugrid) differs from the one that dgfparser computes so much that I
think that Alugrid computes it with single precision. Maybe the key
for std::map can be rounded centroid coordinates, although this is
touchy - the threshold may prove to be inadequate for some purpose,
especially since we already lost some precision due to that single
precision issue. I don't know how std::map is implemented internally,
so I don't know how much performance is gained by using ANN instead. I
expect that the difference is huge for a mesh with a few hundred
thousand cells, because I don't expect that std::map was optimized
with three-dimensional vectors as keys in mind. The linear search was
taking longer than I was willing to wait (I killed it after half an
hour maybe), and the new version sets up the mesh and reorders the
parameters using ANN in a few seconds altogether. I guess that
std::map would be somewhere in between.

I also think it would be better to store the parameters in user space,
but then it should not be stored in GridPtr. In dgfparser/test/main.cc
parameters are in memory three times from some point on: once as
elParams (protected in DuneGridFormatParser), once in elParam
(protected in GridPtr), and once in eldat in main.cc. The node
coordinates and the cell-node incidence vectors are also kept in GDF
and in the grid implementation at the same time. So it is not just one
duplicated array. Whether or not this is acceptable depends on the
size of the problem that I want to solve, but it is certainly not
highly optimized (I know, it's an university code). But even more
importantly, the call to grid.parameters in main.cc really takes so
much time that for me waiting was not an option. Not surprisingly - it
takes quadratic time.

To reorder parameters one must know both orders: the one which exists
in DGF or in Tetgen ele file, and the one which a mapper returns. The
user does not know the first one unless he reads the DGF file. So only
DGF (or GridFactory if you like) can reorder the parameters, using ANN
or std::map if ANN is not available, and the best way would be to do
it in the grid construction process so that ideally gridPtr would have
only local arrays, leaving the data either to the grid implementation
(coordinates and the incidence arrays) or to the user (parameters).

Regards,

Dragan


On Thu, Nov 19, 2009 at 6:04 PM, Andreas Dedner
<dedner at mathematik.uni-freiburg.de> wrote:
> Dear Dragan,
> thank you for your input; your approach is definitly the best way
> to go. After having a look at your patch Martin and I decided that
> improving the default behavior (when ANN is not available) is not
> so difficult - in fact I was sure we were using a std::map anyway and
> was surprised to see that this was not the case...
> Perhaps you could tell us how much more performance you can gain with
> ANN compared to using a simple std::map?
> At the moment I would suggest not to commit your patch since the
> question of how data can be passed through the grid creation process is
> something we will be discussing on Monday at our meeting. Perhaps
> we will decide that the GridFactory should supply some functionality
> and then DGF does not have to do the work.
> Thanks again for your patch
> Andreas
> PS:
>  > Several issues still exist. First, if the grid is modified, elParam is
>>
>> not valid any more for the purpose of the elParameters method, and
>> should be interpolated by a piecewise constant interpolation in a
>> similar manner user arrays are treated. My code does not refine the
>> grid so I leave this unfinished. The old parameters method can still
>> be used after the refinement but it is very slow (and it should
>> probably be declared const).
>
> My idea always was that the parameters should be retrieved by the user
> from the GridPtr and stored in a seperated data structure. If I have
> implemented DOF vectors which can be prolonged/restricted I can use
> those for storing the element/vertex parameters. Have a look at the
> dgfparser/test/main.cc file. If the GridPtr is used in the manner
> shown there then the memory overhead is acceptable I think (o.k. at some
> point the parameters are in memory two times...)
>
>
>> Fourth, I use LeafMultipleCodimMultipleGeomTypeMapper in the GridPtr
>> construction process, while I guess the grid has only one level, so
>> maybe some other mapper would be more efficient? It seems to work fine
>> as it is.
>
> I think it Level<0> index set is the best choice here - but (see above)
> if the user copies the parameters out of the GridPtr then he can decide
> on how to store the data.
>
>