1
$\begingroup$

I have a 2D domain which is discretized using Q4 elements. I have the nodal positions and the element connectivity matrix. I would now like to renumber the nodes in such a way that all the interior nodes are labeled first followed the boundary nodes.

At present, the bandwidth of the stiffness matrix is not of concern. Hence the node numbers can be arbitrary as long as all the interior nodes are numbered first. Such kind of numbering makes the implementation of certain domain decomposition methods easy to write.

Can someone suggest an efficient algorithm to accomplish this?

Improve this question
$\endgroup$
1
$\begingroup$

The first idea that comes to my mind:

  1. Create a multimap Edge2Quad, where edge numbers serve as keys, and quadrilateral element numbers as values.
  2. Traverse all of your edges and fill the Edge2Quad multimap. $\mathcal O(N_\text{edges})$
  3. Now, all interior edges will happen to belong to two quads, while the boundary ones will belong to exactly one.
  4. By traversing your multimap, you will be able to mark the nodes as interior or boundary. $O(N_\text{edges})$
  5. Perform node reordering. $O(N_\text{nodes})$

Of course, you can simplify this by using only arrays and just counting up.

Improve this answer
$\endgroup$
  • $\begingroup$ The standard Q4 element is a bilinear quadrilateral rather than a triangle, but the approach could still work with minor modification. $\endgroup$ – origimbo Jan 31 '19 at 17:05
  • $\begingroup$ @origimbo thanks for pointing it out!!!! Did not read the question with the required attention. $\endgroup$ – Anton Menshov♦ Jan 31 '19 at 17:18
  • $\begingroup$ @Menshov. Thanks. Can you please elaborate step 5 in your answer - Given a set of set interior nodes and boundary nodes how does one reorder them and update the element connectivity matrix and the nodal position array. $\endgroup$ – Salil S. Kulkarni Jan 31 '19 at 17:45
  • $\begingroup$ @SalilS.Kulkarni I would just use a simple local2global array of size $N_\text{nodes}$. And access elements through it. $\endgroup$ – Anton Menshov♦ Jan 31 '19 at 18:08
  • $\begingroup$ Filling and accessing the multimap is O(Nedges log(Nedges)) rather than O(Nedges) $\endgroup$ – BrunoLevy Aug 23 '20 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.