CFD Online Discussion Forums

CFD Online Discussion Forums (
-   Main CFD Forum (
-   -   Weight in graph of mesh partitioning algo. (

Joseph November 29, 2006 06:48

Weight in graph of mesh partitioning algo.
Hi currently i am working on metis a graph partitioning package. I am converting my mesh information into graph and then partitioning. But i couldnt understand that what is weight in graph? Can anybody tell me abt this? Thanks u all in advance.

pc November 29, 2006 09:56

Re: Weight in graph of mesh partitioning algo.
You can assign a weighting factor for each element of the graph, which metis takes into account when balancing the partitions. If you want to consider each element equally, you can set the weights to 1. If the elements have a different workload associated with them in your solver, you can specify weights accordingly to balance the workload rather than the sheer number of elements.

Joseph November 30, 2006 01:39

Re: Weight in graph of mesh partitioning algo.
Thnaks pc, but i dont know how to find weight factor? Can u give some info of how to calculate weight of vertex? or can you provide any link. Thanks

pc November 30, 2006 10:04

Re: Weight in graph of mesh partitioning algo.
The weight factor is something that you, the user, define.

The simplest thing to do is to define the weights to be 1 for all vertices in the graph. Then the partitions will be balanced based solely on the number of vertices (roughly equal number of vertices per partition).

If you need to get more complex in balancing the workload among the processors for your code/application, metis allows you to do that by specifying weights that are non-uniform. In this case you the user define weights based on the amount of CPU work done for each vertex/cell in the graph, for example.

Is that a bit clearer?

Joseph December 1, 2006 00:40

Re: Weight in graph of mesh partitioning algo.
Thank you pc, I have your answer has encouraged me to understand , but at the same time generated these queries. (1) so, you mean to say that metis internally doesnt depend on weight of vertices. Is this right? (2) Wht i was thinking abt weight was that, suppose one vertices is connected to 3 edges, so its weight will be 3. In same way if one edge is conneted to 3 faces, so its weight will be 3. And for face there must be weight of 2,bcoz it cant be connected with more than 2 cells. Is it right? (3) so, in metis can i specify my own weights ? bcoz when i am converting my mesh structure into graph , it gives me diffent weight for different vertices. So, my doubt is how metis calcultes these weights for each vertices? Thnaks again.

pc December 1, 2006 09:14

Re: Weight in graph of mesh partitioning algo.
Hi Joseph. I'll try my best to answer:

1) Metis will use the weights you provide to form the partitions. There is also an option not to use weights at all, where it will (I believe) weight all vertices equally.

2) Weights can be anything you want them to be. Ideally you would like them to reflect the work done in your solver, to balance the processors' workload when running your simulation. So if the relative work for a given cell is dependent on its adjacencies, as you suggest, then the weights you suggest are good. If the work per cell in your solver is the same for all cells, the weights should be 1 for all cells.

3) Yes, you can specify your own weights, those are passed in to the partitioning routines. From what you describe, it seems metis calculates weights based on vertex adjacency (# of edges shared by each vertex). However I have never used the metis routines that convert the mesh to the graph, I've always provided the adjacency graph directly. So I can't say for certain.

Why don't you try a few weighting experiments and see how they alter the resulting decomposition? Then you can get a better feel for what metis is doing.

Good luck.

Joseph December 1, 2006 09:55

Re: Weight in graph of mesh partitioning algo.
Hi thank you very much pc.

Joseph December 4, 2006 06:02

Re: Weight in graph of mesh partitioning algo.
Hi pc, pls help me if you can. I have done partion using mesh, but i want to know that how interface information is written is output file. bcoz, when i am seeing in visulizes (pmvis) it gives me some space beteen interface. i.e. whether metis is cutting element of it is just passing though face between elments. Pls tell me. whther it will also produce fake elments?

pc December 4, 2006 09:41

Re: Weight in graph of mesh partitioning algo.
First of all, I've never used "pmvis", whatever that is.

Second, what you get from metis depends on what your graph represents. That is, the graph can represent physical cells or the actual nodes of your mesh. Then from that you will need to form the individual decomposed domains from the processor assignments metis computes. If the graph represents nodes metis will cut across physical edges. If the graph represents cells metis will cut across the faces of the mesh.

Why don't you send me an email and we can discuss this more offline.

- pc

All times are GMT -4. The time now is 22:21.