Ordering of elements in an unstructured mesh is undoubtedly very important for the performance of computations. For example, it determines the structure of sparse matrices arising from PDE discretizations, which affects the performance of most linear algebra operations like matrix-vector product.
Recently we used an unstructured tetrahedral mesh generated by COMSOL Multiphysics. For given mesh, we construct a matrix with the following structure: each row corresponds to some facet $F$ of the mesh and the non-zero elements correspond to the facets of the one or two cells adjacent to the facet $F$, i.e. for tetrahedral mesh each row has at most 7 non-zero elements. The matrix structure for the mesh generated by COMSOL is shown on the following figure.
Simultaneously, we experiment with other mesh generators, but we currently don't have a good way to order the mesh. Using a simple approach of an in-order traversal of an octree of the cell centers, we get the following structure of the same matrix as above, which is not as "nice" as the original:
Unfortunately the COMSOL documentation does not say anything about mesh ordering algorithms. Does anybody have an idea which algorithm it might be using or which algorithms might generate similar (or better) structure?