It’s all in the numbering – mesh renumbering may improve simulation speed

Posted on August 26, 2020 by John Chawner

We all know that the mesh plays a vital role in CFD simulations. Yet, not many realize that renumbering (ordering) of the cells in the Finite Volume Method (FVM) can affect the performance of the linear solver and thus the speed of the simulation. In some circumstances, a poorly numbered mesh may result in solver divergence and failure of the simulation. In this blog, we use Pointwise and OpenFOAM® to illustrate the effect of mesh renumbering on the matrix structure.

Implicit discretisation of the governing partial differential equations using the FVM leads to sets of large sparse coefficient matrices. These are solved using iterative or direct methods. Consider a sparse n x n matrix “A”. Clustering of all the nonzero elements near the diagonal makes “A” a banded matrix. The bandwidth of the matrix is defined by

\beta = {\rm max} { |i-j| \; | \; a_{ij} \neq 0 }.

Another important quantity is the matrix profile. To calculate the profile we first define

f_i = {\rm min}{ j \; | \; a_{ij} \neq 0}.

This locates the leftmost nonzero element in each row. We now define

\delta_i= i- f_i

The profile is then defined to be

\sum^n_{i=1} \delta_i.

The goal of mesh renumbering is to reduce the matrix bandwidth and profile. There are many sparse matrix renumbering strategies, with the most commonly used in CFD being the Cuthill-McKee.

Most CFD solvers either renumber the mesh without user intervention or provide an application for the user to renumber the mesh manually. OpenFOAM has an application called renumberMesh that reduces the bandwidth and profile of the coefficient matrices by renumbering the cell label list. By default, OpenFOAM uses Cuthill-Mckee but also offers reverse Cuthill-McKee, Sloan, Zoltan, Structured, Spring and Random (not for use).

Pointwise stores the mesh internally in a format and numbering that is efficient for mesh generation. This numbering does not necessarily result in a low bandwidth or profile matrix upon export. Let’s look at several examples.

Simple structured mesh

Our first case is a simple structured mesh, as shown in Figure 1. The initial bandwidth and profile reported from renumberMesh (OpenFOAM v2006) were 7 and 300, respectively.

Simple structured mesh (Figure 1)

Plotting the matrix sparsity pattern (nonzero entries) allows visual inspection of the effect of matrix bandwidth and profile reduction (see Figure 2). A visualisation of the matrix sparsity for the simple structured mesh example before renumbering exhibits diagonal banding.

Matrix sparsity pattern for simple structure mesh as exported from Pointwise (Figure 2).

Figure 3 shows the sparsity pattern for the renumbered simple structure mesh after the application of the Cuthill-McKee renumbering method. In this case, the matrix bandwidth remains unchanged, but the profile was reduced by 18.3% to 245.

Matrix sparsity pattern for simple structure mesh after renumbering with Cuthill-Mckee (Figure 3).

Simple unstructured mesh

Our second case is a simple unstructured mesh consisting of triangles, formed by sub-dividing a structured mesh, as shown in Figure 4. The initial bandwidth and profile reported from renumberMesh (OpenFOAM v2006) were 25 and 310, respectively.

Simple unstructured mesh (Figure 4).

Figure 5 shows a visualisation of the matrix sparsity for the simple unstructured mesh example before renumbering. The sparsity pattern is very different from the simple structured mesh with minimal diagonal banding.

Matrix sparsity pattern for simple unstructured mesh as exported from Pointwise (Figure 5).

After renumbering (Cuthill-McKee), the sparsity is more diagonally aligned, as shown in Figure 6. In this case, the matrix bandwidth reduced to 7, a 72% reduction and the profile reduced to 139, a 55.1% reduction.

Matrix sparsity pattern for simple unstructured mesh after renumbering with Cuthill-Mckee (Figure 6).

Unstructured mesh with T-Rex

Our third case is an unstructured mesh with T-Rex, consisting of triangles and quadrilaterals, as shown in Figure 7. The initial bandwidth and profile reported from renumberMesh (OpenFOAM v2006) were 58 and 777, respectively. Figure 8 shows the sparsity pattern before the renumbering with clustering around the diagonal and at the matrix extents.

Unstructured mesh with T-Rex (Figure 7).
Matrix sparsity pattern for an unstructured mesh with T-Rex as exported from Pointwise (Figure 8).

After renumbering (Cuthill-McKee), the sparsity is more diagonally aligned, as shown in Figure 9. In this case, the matrix bandwidth changed to 9, an 84.4% reduction and the profile reduced to 353, a 54.5% reduction.

Matrix sparsity pattern for unstructured mesh with T-Rex after renumbering (Figure 9).

Larger unstructured mesh with T-Rex

The last example is for a larger unstructured mesh involving T-Rex, as shown in Figure 11. The initial bandwidth and profile reported from renumberMesh (OpenFOAM v2006) were 3,656 and 1,402,820. Figure 12 shows the sparsity pattern before the renumbering, with non-zero entries found across the entire matrix extents.

Large unstructured mesh with T-Rex (Figure 10).
Matrix sparsity pattern for the larger unstructured mesh with T-Rex exported from Pointwise (Figure 11).

After renumbering (Cuthill-McKee), the sparsity is more diagonally aligned, as shown in Figure 12. Resulting in the matrix bandwidth changing to 116, a 96.8% reduction and the profile reduced to 297,498, a 78.8.5% reduction.

Matrix sparsity pattern for the larger unstructured mesh with T-Rex after renumbering (Figure 12).

Dicing with danger

There are always some people that like to dice with danger. You recall OpenFOAM has a renumbering option called “random” and it was recommended not to use it. If you did, for the simple unstructured mesh, you would get the sparsity pattern shown in Figure 13. Resulting in the matrix bandwidth changing to 29 (up 16%) and the profile reduced to 306 (down 1.2%).

Matrix sparsity pattern for simple unstructured mesh after renumbering with Random (Figure 13).

Take away

If you are using meshes generated with Pointwise in OpenFOAM, then you should be renumbering your mesh in OpenFOAM before running your simulation.

Beginners tip

If you use the OpenFOAM renumberMesh utility on ASCII formatted meshes with small cell sizes, make sure your choice of write precision is suitable for the smallest cell size. Beginners often find the mesh quality deteriorates after renumbering due to inappropriate write precision in OpenFOAM. Renumbering of the mesh should not alter the mesh quality. If you see a change, check your write precision and format.

Want to give it a go yourself?

Request a Pointwise free trial.

This entry was posted in Applications, Software and tagged , , , . Bookmark the permalink.

5 Responses to It’s all in the numbering – mesh renumbering may improve simulation speed

  1. Bruno Santos says:
    September 8, 2020 at 11:12 am

    Another beginner tip: Use ASCII data formatting only when testing things on a case, use binary formatting for real work.

    @Darrin Stephens: In the introduction paragraph, the link for OpenFOAM at “we use Pointwise and OpenFOAM®” is broken, given that it only uses “www.openfoam” 😉

    Reply

  2. Pingback: Recap of Six Recent CFD Success Stories with a Meshing Assist | Another Fine Mesh

  3. Pingback: Recombination of Voxel Transition Cells for OpenFOAM Meshes | Another Fine Mesh

Leave a Reply to Bruno SantosCancel reply