<div dir="ltr">Thanks Matt for your help and support. I read a little on ParMetis manual and looked at PETSc implementation and I think I figured out the source of my confusion.<div><br></div><div>The fact is, ParMetis does create a good partitioning starting from the initial numbering. Indeed according to their manual for ParMetis 3.2 and on page 5:</div>

<div><br></div><div>&quot;... ParMETIS_V3_PartKway makes no assumptions on how the graph is initially distributed among the processors. </div><div>It can effectively partition a graph that is randomly distributed as well as a graph that is well distributed . If the graph </div>

<div>is initially well distributed among the processors, ParMETIS_V3_PartKway will take less time to run. </div><div>However, the quality of the computed partitionings does not depend on the initial distribution.&quot;</div>

<div><br></div><div>The problem that I was having was looking at the final AO and assuming that nodes 0-8 are on rank 0 and 9-17 on rank 1 of the <b>new partitioned grid. </b>This is wrong since &quot;ISPartitioningToNumbering()&quot; generates an index set &quot;is&quot; such that &quot;on each processor the index set that defines the global numbers (in the new numbering) for all the nodes currently (before the partitioning) on that processor&quot;. In other words, I still need to change the numbering such that each processors has the newly computed numbers! </div>

<div><br></div><div>This whole thing is little bit too confusing! Anyway, I think the problem is solved now.</div><div><br></div><div><br></div><div>Thanks again for the help,</div><div>Mohammad</div><meta http-equiv="content-type" content="text/html; charset=utf-8"><div>

<br></div><div><br></div><div><br></div><div><br><br><div class="gmail_quote">On Fri, Jul 29, 2011 at 2:09 PM, Matthew Knepley <span dir="ltr">&lt;<a href="mailto:knepley@gmail.com">knepley@gmail.com</a>&gt;</span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">On Fri, Jul 29, 2011 at 7:52 PM, Mohammad Mirzadeh <span dir="ltr">&lt;<a href="mailto:mirzadeh@gmail.com" target="_blank">mirzadeh@gmail.com</a>&gt;</span> wrote:<br>

</div><div class="gmail_quote"><div class="im"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Matt,<div><br></div><div>Is ParMetis implementation in PETSc only done via $PETSC_DIR/src/mat/partition/impls/pmetis/pmetis.c ? I am wondering if PETSc has interface to ParMETIS_V3_RefineKway function as noted in ParMetis manual?</div>


</div></blockquote><div><br></div></div><div>If you want to Mat, then pmetis.c is it. There is stuff for more general meshes, but it is experimental. There is a paper about it</div><div><br></div><div>  <a href="http://arxiv.org/abs/0908.4427" target="_blank">http://arxiv.org/abs/0908.4427</a></div>


<div><br></div><div>which will give you an idea what it does.</div><div><br></div><div>  Thanks,</div><div><br></div><div>     Matt</div><div><div></div><div class="h5"><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">


<div dir="ltr"><div>Thanks,</div><div>Mohammad</div><div><br><br><div class="gmail_quote">On Thu, Jul 28, 2011 at 10:11 PM, Mohammad Mirzadeh <span dir="ltr">&lt;<a href="mailto:mirzadeh@gmail.com" target="_blank">mirzadeh@gmail.com</a>&gt;</span> wrote:<br>




<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I see. Thanks for the help Matt<div><div></div><div><br><br><div class="gmail_quote">On Thu, Jul 28, 2011 at 10:01 PM, Matthew Knepley <span dir="ltr">&lt;<a href="mailto:knepley@gmail.com" target="_blank">knepley@gmail.com</a>&gt;</span> wrote:<br>





<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>On Fri, Jul 29, 2011 at 4:52 AM, Mohammad Mirzadeh <span dir="ltr">&lt;<a href="mailto:mirzadeh@gmail.com" target="_blank">mirzadeh@gmail.com</a>&gt;</span> wrote:<br>





</div><div class="gmail_quote"><div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Thank you Matt. Indeed I have looked into p4est and also Dendro. p4est uses parallel octrees/quadtrees but for what I intend to do I only need to distribute a single tree that is created in serial among processors. I definitely like to have the tree data-structure in parallel but that would be another project. I also looked into Dendro and they kind of follow the same strategy. i.e every single processor has a local copy of the whole tree. What they do differently, however, is they somehow manage to use DA instead of a general unstructured numbering which is quite interesting but I still don&#39;t know how they do it. Unfortunately, they do not handle (as far as I understood from their manual) non-graded trees which are the ones I work with.<div>








<br></div><div>So, all I need to do is to somehow distribute my grid among processors and since each one has a local copy of data-structure I could get around the problem. Just anotehr question. If the partitioning is not unique, do you at least get a better numbering than the tree you start with?</div>






</div></blockquote><div><br></div></div><div>You should, which is why I suggested that you are not giving the input you think you are.</div><div><br></div><div>   Matt</div><div><div></div><div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">






<div dir="ltr"><div><font color="#888888">Mohammad</font><div><div></div><div><br><div><br><div class="gmail_quote">On Thu, Jul 28, 2011 at 9:25 PM, Matthew Knepley <span dir="ltr">&lt;<a href="mailto:knepley@gmail.com" target="_blank">knepley@gmail.com</a>&gt;</span> wrote:<br>






<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<div>On Fri, Jul 29, 2011 at 3:49 AM, Mohammad Mirzadeh <span dir="ltr">&lt;<a href="mailto:mirzadeh@gmail.com" target="_blank">mirzadeh@gmail.com</a>&gt;</span> wrote:<br></div><div class="gmail_quote"><div>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Hi all,<div><br></div><div>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. </div>









</div></blockquote><div><br></div></div><div>0) If you are doing this, I think you should at least look at the p4est package before proceeding.</div><div><div></div><div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">









<div dir="ltr">

<div><br></div><div>1                16              7                             3    </div><div>+---------------+---------------+------------------------------+</div><div>|                |                |                               |</div>











<div>|                |                |                               |</div>

<div>|14             | 15           | 17                           |</div>

<div>+---------------+---------------+                              |</div>

<div>|                |                |                               |</div><div>|                |                |                               |</div>

<div>| 4             | 12            | 6                            |8</div><div>+---------------+---------------+------------------------------+</div><div>

<div>|                |                |                               |</div><div>|                |                |                               |</div>

<div>| 9              | 11           |  13                         |</div><div>+---------------+---------------+                              |</div><div>

|                |                |                               |</div><div>|                |                |                               |</div>

<div>| 0              | 10           |5                             | 2</div></div><div>+---------------+---------------+------------------------------+</div>

<div>
<pre style="margin-top:0px;margin-bottom:0px;margin-left:0px;margin-right:0px;text-indent:0px"><br></pre><pre style="margin-top:0px;margin-bottom:0px;margin-left:0px;margin-right:0px;text-indent:0px"><font face="arial"><span style="white-space:normal">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. </span></font><span style="font-family:arial;white-space:normal">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:</span></pre>











</div><div><br></div><div><div>Number of elements in ordering 18</div><div>PETSc-&gt;App  App-&gt;PETSc</div><div>  0    9                  0    1</div><div>  1    0                  1    3</div><div>  2   10                 2    4</div>











<div>  3    1                  3    7</div><div>  4    2                  4   12</div><div>  5   11                 5   14</div><div>  6   12                 6   15</div><div>  7    3                  7   16</div><div>  8   13                 8   17</div>











<div>  9   14                 9    0</div><div> 10   15               10    2</div><div> 11   16               11    5</div><div> 12    4                12    6</div><div> 13   17               13    8</div><div> 14    5                14    9</div>











<div> 15    6                15   10</div><div> 16    7                16   11</div><div> 17    8                17   13</div></div><div><br></div><div>Now I have two questions/concerns: </div><div><br></div><div>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 &quot;good&quot; 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).</div>









</div></blockquote><div><br></div></div></div><div>Yes, the PETSc ordering is always contiguous. Perhaps you are not providing the graph you think you are for partitioning.</div><div><div></div><div><div> </div>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div>2) Isn&#39;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:</div><div><br></div><div>









<div>
14               15             16                             17    </div><div>+---------------+---------------+------------------------------+</div><div>|                |                |                               |</div>











<div>|                |                |                               |</div><div>|11             | 12           | 13                           |</div><div>+---------------+---------------+                              |</div>











<div>|                |                |                               |</div><div>|                |                |                               |</div><div>| 7             | 8              | 9                            |10</div>











<div>+---------------+---------------+------------------------------+</div><div><div>|                |                |                               |</div><div>|                |                |                               |</div>











<div>| 4              | 5             |  6                           |</div><div>+---------------+---------------+                              |</div><div>|                |                |                               |</div>











<div>|                |                |                               |</div><div>| 0              | 1             |2                             | 3</div></div><div>+---------------+---------------+------------------------------+</div>











</div><div><br></div><div>I get the following AO:</div><div><br></div><div><div>Number of elements in ordering 18</div><div>PETSc-&gt;App  App-&gt;PETSc</div><div>  0    9                   0    9</div><div>  1   10                  1   10</div>











<div>  2   11                  2   11</div><div>  3   12                  3   12</div><div>  4   13                  4   13</div><div>  5   14                  5   14</div><div>  6   15                  6   15</div><div>










  7   16                  7   16</div>
<div>  8   17                  8   17</div><div>  9    0                   9    0</div><div> 10    1                10    1</div><div> 11    2                11    2</div><div> 12    3                12    3</div><div> 13    4                13    4</div>











<div> 14    5                14    5</div><div> 15    6                15    6</div><div> 16    7                16    7</div><div> 17    8                17    8</div></div><div><br></div><div><br></div><div>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 &quot;best&quot; possible ordering depending on the initial distribution? If so, how should I know what ordering to start with?</div>









</div></blockquote><div><br></div></div></div><div>Yes, ParMetis does not provide a unique &quot;best&quot; ordering, which is at least NP-complete if not worse.</div><div><br></div><div>   Matt</div><div><div>

 </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div>I am really confused and would appreciate if someone could provide some insights.</div><div><br></div><div>Thanks,</div><div>Mohammad</div></div>
</blockquote></div></div><font color="#888888"><br><br clear="all"><br>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>








-- Norbert Wiener<br>

</font></blockquote></div><br></div></div></div></div></div>
</blockquote></div></div></div><div><div></div><div><br><br clear="all"><br>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>





-- Norbert Wiener<br>

</div></div></blockquote></div><br></div></div></div>
</blockquote></div><br></div></div>
</blockquote></div></div></div><div><div></div><div class="h5"><br><br clear="all"><br>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>

-- Norbert Wiener<br>

</div></div></blockquote></div><br></div></div>