9
$\begingroup$

I am interested in local AMR on unstructured meshes. Currently, I'm working with the OpenFOAM library - it supports completely unstructured local AMR:

  • cell refinement criteria determine a list of cells that are cut
  • selected cells are refined: entire mesh is re-constructed
  • a map is created from the old mesh to a new one
  • connectivity is recomputed (face-cells, edge-faces, etc)
  • fields are mapped onto the new mesh

Since the data structures involved are basically C++ vectors, the mesh gets inflated, copied.

I need to learn about alternative approaches that can be built upon a mesh that uses static data structures. One of them is the parallel Octree Forrest local AMR, present in p4est and Dendro.

Can someone point me to a recent review paper on local adaptive AMR strategies for unstructured mesh?

Experience based advice would be even better: which local AMR engine is the optimal choice for fixed data structure based unstructured mesh?

I need an overview before reading about balancing inter-tree communication on the first page of a paper. :)

Improve this question
$\endgroup$
  • $\begingroup$ What exactly do you mean with "static data structures"? During mesh refinement, of course the number of cells increases, and so some data structure definitely has to grow (your "inflated, copied"). I'm just not quite sure what exactly your question is, I'm afraid. $\endgroup$ – Wolfgang Bangerth Jun 21 '12 at 6:37
  • $\begingroup$ Well, if the mesh is based on std::vector like data structures, then adding even a single cell, will cause creation of new std::vector (with increased size for the new cell, its points and faces), and copying the old unrefined data to the new structures. With Octree Forrest, if I understand it correctly, I will not expand the data structures that define my mesh, the Octree Forrest will hold all the necessary information for refinement, and the octree is a dynamic data structure in the sense that changing a single cell does not copy the whole tree and expand it for a single element. $\endgroup$ – tmaric Jun 21 '12 at 7:55
  • $\begingroup$ Another note: since I'm into two phase flows, even for highly dispersed flow (a lot of bubbles), I will have maybe up to 25% of the total cell count that needs to be refined, which means that for a completely unstructured local AMR, every time I refine, I copy the whole mesh just for those 25% of the cells that are active in refinement. $\endgroup$ – tmaric Jun 21 '12 at 8:03
  • 2
    $\begingroup$ If you use a static data structure, there really isn't an efficient way of adding new data without laboriously copying the old data onto an new vector. An insertion/deletion operation then would cost an $\Theta(n)$ operation, where $n$ is the length of the vector. As far as I'm aware, it can only be done efficiently if you use a dynamic data structure (tree, graph, etc.) which roughly uses $\Theta(1)$ operations. $\endgroup$ – Paul♦ Jun 21 '12 at 15:45
  • 2
    $\begingroup$ I don't know what other libraries use but in deal.II we have a combination of static and dynamic data structures: we have a std::vector for each level of the hierarchic mesh. If cells are coarsened away, we mark the elements of the vector as unused. If cells are refined, the children are put into the std::vector of the next level, first into unused elements, then appended at the end. When reallocation is necessary because elements are added, then we first count how many new elements we will need during refinement and do a single allocation. In this scheme, the cost of alloc/copy is negligible. $\endgroup$ – Wolfgang Bangerth Jun 26 '12 at 13:43
4
$\begingroup$

From the comments above, I understand that you want to avoid to copy the vector when you add more cells. The easiest approach is to reserve space for the maximum number of cells that you might want to have: 

std::vector<YourCellType> myVectorOfCells;
vectorOfCells.reserve(maxNoCells);

Your vector has allocated space for creating maxNoCells cells but no cells have been created yet. You can now add maxNoCells to your vector, each operation in O(1) time, without the vector copying itself. However, the C++ Standard requires the push_back operation to be amortized O(1) time. If you add more than maxNoCells, the vector will copy itself, reserving space for k-times as many cells as it previously had (typical implementations choose a k between 1.4 and 2), so that you can keep adding cells to the vector in O(1) time. This resizing operation is not O(1).

An AMR strategy begs for a dynamic data structure, like a linked-list of cells that supports insertion/deletion in O(1). A linked-list is, however, much slower than a vector because traversing it requires to randomly jump in memory from cell to cell, generating a lot of cache misses: in modern processors it is faster to swap $n/2$ elements of a vector in order to insert an element than traverse $n/2$ elements of a linked list. So in practice, vectors are the way to go: they are customizable (you can supply them your own allocator), your cells are aligned in memory, you have random acces in O(1) time... as far as you reserve memory first, you can add elements in O(1) time too! As Prof. Bangerth mentioned above, hierarchical data structures like trees also use vectors internally for storing their data.

However, I think it is better practice to allocate memory at the beginning of the simulation. You have to know how many cells you can possibly need in order to check if you have enough memory available. You do not want your simulation in 200.000 processors having to reallocate your data structure or running out of memory and having to swap to disk. In case that happens my opinion is that your program should fail loudly because of an user input error.

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you! :) I will check for the functionality of th reserve operation for the dynamic vector data structure in OpenFOAM... I think that the operation now runs based on the mesh data that is read from the disk, filling up the data structure to the end. $\endgroup$ – tmaric Jul 31 '12 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.