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?


1 Answer 1


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.

  • $\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, 2019 at 17:05
  • $\begingroup$ @origimbo thanks for pointing it out!!!! Did not read the question with the required attention. $\endgroup$
    – Anton Menshov
    Jan 31, 2019 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$ Jan 31, 2019 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, 2019 at 18:08
  • $\begingroup$ Filling and accessing the multimap is O(Nedges log(Nedges)) rather than O(Nedges) $\endgroup$
    – BrunoLevy
    Aug 23, 2020 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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