Meshing, Geometric Modeling and Numerical Simulation 3

Chapter 3Renumbering and Memory

Numerical simulations based on finite elements use a mesh as spatial support. A matrix (so-called elementary matrix)¹ will be constructed for every element and the assembly of these elementary quantities results in obtaining the corresponding global matrix. Filling up this matrix, that is, the position of its a priori non-zero entries, depends on the numbering of mesh nodes. The aspect of this filling, visible by looking at the distribution of coefficients, has, according to the solving methods used to solve the corresponding systems, an impact on several points, obviously the matrix bandwidth and, also, the memory size needed to store it. Another effect (most often extremely perverse) is that access to coefficients can trigger cache misses when moving from one coefficient to another whose memory locations are very distant. It should also be noted that the numbering of the vertices and/or of the elements (of a mesh) may also have a nonnegligible effect on the performance of a particular algorithm (for example, in visualization, but also in mesh algorithms themselves as well as for purposes of parallelization of certain methods in which there is a link between mesh renumbering and partition). These two questions will therefore be looked into: how can vertices, and more generally nodes, and/or mesh elements be renumbered to optimize a given criterion?

It is interesting to indicate that conventional (and somewhat old) renumbering methods, to a great ...