# simple and fast graph-clustering for paralelization of finite element simulations

I'm learning to use OpenCL to optimize some of my simulations. I realized that I need some sort of Graph-clustering or graph-partitioning to exploit efficiently local memory for un-ordered meshes.

example: I implemented elastic cloth simulation with regular mesh of 4-bonded vertexes, which I can separate manually to localized batches. Now I would like to move to general irregular mesh where each node can have any number of edges.

From quick search I found some resources but I'm not sure if it adress very well my needs (I have no experience in area of discrete math and graph theory).

What I want:

• split mesh to batches such that
1. all batches has approximately same size (number of nodes and edges) e.g. 16 nodes each correspoding to local_size of my OpenCL kernell
2. the number of edges between different batches is minimal - to minimize overlap between nodes loaded by each workgroup
• Algorithm which is concise and easy to implement by myself - for me this is just side issue not main topic. I do not what to create dependence on some 3rd party software or library even if it is open-source.
• it does not have to lead to optimal solution, it can be stochastic and rough heuristic
• it should be fast - $O(n)$ with small prefactor
• METIS is used precisely for such problems. Commented Apr 18, 2017 at 10:19
• thanks, but I'm looking for some simple algorithm which I would be able to implement myself, not a big 3rd party library. Nevertheless, form the webpage I can read multilevel recursive-bisection, multilevel k-way, and multi-constraint partitioning so perhaps I should look on these. Still I would like point out which specific algorithm, and idealy get some short code sample. Commented Apr 19, 2017 at 11:12

1) sort all the cells of the mesh using Hilbert sort

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() function of the STL. See also [3] for a nice explanation of spatial sorting.