METIS vs Rtree (partitioning)

[fdrmrc]

@luca-heltai @andreacangiani

I will collect on this discussion some other examples as the ones of this morning. Feel free to ask for other geometries as well.

---

EXAMPLE 1: Unstructured square rectangular mesh

• Size underlying fine tria: 21 760 elements:

• Number of partitions: 22
  Left: METIS
  Right: R-tree
  

---

• Number of partitions: 85
  Left: METIS
  Right: R-tree
  

---

• Number of partitions: 340
  Left: METIS
  Right: R-tree
  

---

[andreacangiani]

This is NOT good....it IS FANTASTIC!!!

ps: what is the domain? It looks rectangular...

[fdrmrc]

Sorry for replying now, yesterday I was at home sick in bed.

Here's the underlying grid, the size of the elements on the top right corner looks the same as the other elements.

[andreacangiani]

Then I don't understand why the agglomerate are so uneven. Perhaps we should look at the whole tree as Luca suggeste, but, to start with, can you plot the list of the numbers of leaves each agglomerate is made of?
(I am in bed myself now with a nasty cold!)

[fdrmrc]

can you plot the list of the numbers of leaves each agglomerate is made of?

For 22 agglomerates we have:

N subdomains = 22
1024 cells have subdomain 0
1024 cells have subdomain 1
1024 cells have subdomain 2
1024 cells have subdomain 3
1024 cells have subdomain 4
1024 cells have subdomain 5
1024 cells have subdomain 6
1024 cells have subdomain 7
1024 cells have subdomain 8
1024 cells have subdomain 9
1024 cells have subdomain 10
1024 cells have subdomain 11
1024 cells have subdomain 12
1024 cells have subdomain 13
1024 cells have subdomain 14
1024 cells have subdomain 15
1024 cells have subdomain 16
1024 cells have subdomain 17
1024 cells have subdomain 18
1024 cells have subdomain 19
1024 cells have subdomain 20
256 cells have subdomain 21

[andreacangiani]

Interesting....so indeed it maintains perfectly the subdivision but then the last agglomerate is made of the remaining ones. That's not ideal. Mumble, mumble.

[fdrmrc]

In one of the following messages I played with the parameters of the rtree (see here https://github.com/fdrmrc/Polydeal/discussions/48#discussioncomment-7798830) . The situation looks better to me in that instance

[fdrmrc]

If I take the same domain (the rectangle $[0,1.25] \times [0,1]$) , but structured, things are again okay with the tree.

• N partitions: 16
  

• N partitions: 64
  

• N partitions: 256
  

• N partitions: 1024
  

[fdrmrc]

I played with the parameters of the rtree. The grids above have been obtained with a maximum number of entries per node = 4. Setting this parameter to 2 we have better(?) results. In the following I am comparing the Rtree results after changing this value. For the sake of comparison, on the left column I am displaying the agglomerates we obtained before.

LEFT: max entries per node = 4 ---------- RIGHT: max entries per node = 2

• N partitions = 22
  

• N partitions = 85
  

• N partitions = 340