[petsc-users] Grid Partitioning with ParMetis

[Mohammad Mirzadeh]

Hi all,

I am trying to write a code to do parallel computation on quadtree adaptive
grids and to do so , I need to distribute the grid in parallel. I have
selected a general unstructured framework for telling PETSc about my node
numbering. An example of such grid is schematically shown below.

1                16              7                             3
+---------------+---------------+------------------------------+
|                |                |                               |
|                |                |                               |
|14             | 15           | 17                           |
+---------------+---------------+                              |
|                |                |                               |
|                |                |                               |
| 4             | 12            | 6                            |8
+---------------+---------------+------------------------------+
|                |                |                               |
|                |                |                               |
| 9              | 11           |  13                         |
+---------------+---------------+                              |
|                |                |                               |
|                |                |                               |
| 0              | 10           |5                             | 2
+---------------+---------------+------------------------------+


To distribute this in parallel I am using the ParMetis interface via
MatPartitioning object and I follow(more or less) the example in
$PETSC_DIR/src/dm/ao/examples/tutorials/ex2.c; To make the initial
distribution, I choose nodal based partitioning by creating the
adjacency matrix, for which I create ia and ja arrays accordingly.
once the grid is processed and the new orderings are generated, I
follow all required steps to generate the AO needed to map between
PETSc ordering and the new global numbering and this is the result:


Number of elements in ordering 18
PETSc->App  App->PETSc
  0    9                  0    1
  1    0                  1    3
  2   10                 2    4
  3    1                  3    7
  4    2                  4   12
  5   11                 5   14
  6   12                 6   15
  7    3                  7   16
  8   13                 8   17
  9   14                 9    0
 10   15               10    2
 11   16               11    5
 12    4                12    6
 13   17               13    8
 14    5                14    9
 15    6                15   10
 16    7                16   11
 17    8                17   13

Now I have two questions/concerns:

1) Do processors always have the nodes in contiguous chunks of PETSc
ordering? i.e 0-8 on rank 0 and 9-17 on rank 1 ? If so, this particular
ordering does not seem to be "good" for this grid since it seems to cross
too many edges in the graph (here 13 edges) and by just looking at the graph
I can(at least) think of a better distribution with only 6 edge cuts. (if
you are wondering how, having {0,9,4,14,1,10,11,12,15} on rank 0 and rest on
rank 1).

2) Isn't  it true that the final distribution should be independent of
initial grid numbering? When I try the same grid but with the following
(hand-generated) numbering:

14               15             16                             17
+---------------+---------------+------------------------------+
|                |                |                               |
|                |                |                               |
|11             | 12           | 13                           |
+---------------+---------------+                              |
|                |                |                               |
|                |                |                               |
| 7             | 8              | 9                            |10
+---------------+---------------+------------------------------+
|                |                |                               |
|                |                |                               |
| 4              | 5             |  6                           |
+---------------+---------------+                              |
|                |                |                               |
|                |                |                               |
| 0              | 1             |2                             | 3
+---------------+---------------+------------------------------+

I get the following AO:

Number of elements in ordering 18
PETSc->App  App->PETSc
  0    9                   0    9
  1   10                  1   10
  2   11                  2   11
  3   12                  3   12
  4   13                  4   13
  5   14                  5   14
  6   15                  6   15
  7   16                  7   16
  8   17                  8   17
  9    0                   9    0
 10    1                10    1
 11    2                11    2
 12    3                12    3
 13    4                13    4
 14    5                14    5
 15    6                15    6
 16    7                16    7
 17    8                17    8


which is simply the initial ordering with a change in the order in which
processors handle nodes.  Could it be that the partitioning is not unique
and each time the algorithm only tries to obtain the "best" possible
ordering depending on the initial distribution? If so, how should I know
what ordering to start with?

I am really confused and would appreciate if someone could provide some
insights.

Thanks,
Mohammad
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20110728/f8715986/attachment-0001.htm>