4
$\begingroup$

Metis is purpose-built for partitioning graphs and unstructured meshes one uses in finite element/volume methods, and it works great for this.

I have a 3D structured multi-block topology, where each $ni\times nj\times nk$ block can only be partitioned along planes, as opposed to an unstructured topology where the partitions can be drawn anywhere.

Is there any simple way to partition this kind of topology with metis?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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 a volume mesh (mesh tetrahedra => graph vertices, mesh triangles => graph edges). In reality each mesh element represents a larger collection of unknowns, analogous to how each of your blocks presumably represents a collection of ni/nj/nk unknowns.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Constructing a graph where each vertex is a block is no problem; I do that for the load-balancing later for distributing the blocks to processors. I was a bit unclear; I don't want to allow only cutting between the blocks, but actually allow cutting blocks themselves along a plane -- e.g. a large $ni \times nj \times nk$ block could be partitioned into 2 $ni \times nj/2 \times nk$ blocks, or 4 $ni/2 \times nj \times nk/2$ blocks -- but not allowing arbitrary partitions like you do with unstructured grids. It has to be along a plane. $\endgroup$
    – Aurelius
    Aug 1, 2013 at 14:42
  • $\begingroup$ How would you feel about splitting each block into 8 pieces, then METISing that with this algorithm? (i.e. same thing as you're already doing, just finer granularity) Hard to see the underlying objective. Out of curiousity, are you looking to partition the grid, or generate a nested dissection ordering to factor some sparse matrix whose nonzero pattern will be induced by the grid? $\endgroup$
    – rchilton1980
    Aug 1, 2013 at 22:00
  • $\begingroup$ Yes, that's more or less what I'm doing now; "recursive bisection" of the largest blocks until a load balancing within some tolerance is achievable. It works okay, but in general it's not going to be optimal. The underlying objective is pretty straight forward; partition the grid while also maintaining good properties for geometric multigrid. $\endgroup$
    – Aurelius
    Aug 5, 2013 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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