# Tag Info

## Hot answers tagged partitioning

3

For your first question, constructing the adjacency graph of the "partitions" (what you call "cell groups"): Let's say you have an array $p_K$ in which you store for each cell $K$ which partition $p$ it belongs to. Also assume that you have a (sparse) array $a_{KL}$ whose entries are true if cells $K$ and $L$ are neighbors ("adjacent&...

3

If different nodes have different costs, for example because different rows of your matrix have different numbers of nonzero entries, then you need to attach weights to each node of your graph. Graph partitioning algorithms such as METIS allow you to do this, creating partitions where it is not the number of nodes that are about equal between partitions, but ...

3

The most common way to write finite element software is to make a non-overlapping partition of elements with interface vertex ownership resolved using some rule (or via hypergraph partitioning, which is more expensive). To create a globally-assembled stiffness matrix, this involves communication of entries to the process that owns the vertex. Residual ...

3

Can you construct a graph G that describes the adjacency relationship between blocks and have METIS partition that? E.g. each vertex in G represents an ni/nj/nk block, and each edge in G represents a plane between two such blocks? (where METIS is allowed to cut) I do something similar (but for high order FEM), having METIS partition on the graph induced by ...

3

Partitioning by elements leads to minor simplifications in assembly at the expense of poor load balancing in the solver, inability to use many popular solution methods, and more communication to apply the operator. The most common reason to use an element partition is simply because the code to handle overlap or to communicate contributions into off-process ...

2

Both are valid techniques with their own tradeoffs. PETSc, in particular, has a history as a linear algebra library, and given that, it makes sense for it to assign rows distinctly to processors. For finite element methods, which have element matrix formation, and often some sort of matrix assembly, it often makes sense to assign elements to uniquely to ...

2

Your intuition is correct -- a bisection method cuts the (hyper)graph in two, and recursive bisection repeatedly applies this strategy until the desired number of cuts have been made. Direct partitioning on the other hand tries to immediately divide up the graph. Part of the divide between the two is historical. Some of the earliest successful heuristics ...

1

Consider the following visualization as an example. It visualizes two binary trees: $T_S$ and $T_V$ for the surface mesh of the sphere and volume mesh of the sphere, respectively. At the 0th level, there is only one node in each tree: $S_1^{(0)}$ and $V_1^{(0)}$. The superscript in the brackets denotes the level in the tree and the subscript denotes the ...

1

You need to look up the VTK file format here: https://vtk.org/wp-content/uploads/2015/04/file-formats.pdf It's not very difficult, you'd just write a single cell for each node of your quad tree. The results will look like the pictures you see here or here or here -- all use VTK file format to visualize meshes.

1

For a simple (yet not optimal, see below) mesh partitioning algorithm, you can do: 1) sort all the cells of the mesh using Hilbert sort 2) partition the sorted list of cells into chunks of the desired size Spatial Hilbert sorting is implemented in my GEOGRAM library [1,2] and in CGAL [3]. It is reasonably easy to implement, using the std::nth_element() ...

1

Check out: Nijboer, B. R. A., & De Wette, F. W. (1957). On the calculation of lattice sums. Physica, 23(1-5), 309–321. doi:10.1016/S0031-8914(57)92124-9 There they make the case for using a splitting based on the incomplete Gamma function. That splitting generalizes the choice of the error function to arbitrary dimensions.

1

I was having an issue with Metis_PartMeshDual where if my number of processors was greater than (number of elements)/2 I would get processors that were given no elements. I believe this is what the OP means by a partition getting an "empty subdomain". I found that the line options[METIS_OPTION_PTYPE] = METIS_PTYPE_RB; made it so that for all cases ...

Only top voted, non community-wiki answers of a minimum length are eligible