3.5.2 Run-Length Encoding

Instead of using an adaptive grid to represent the entire simulation domain, it is better to use a regular grid with an appropriate resolution and store only the LS values of defined grid points needed for the time integration scheme.

Run-length encoding along a certain grid direction is an efficient technique for this purpose [45]. In the following, run-length encoding is explained for the ${x}_1$ -direction. However, it can be applied to all other grid directions analogously. Each line of grid points parallel to the ${x}_1$ -direction is separately run-length encoded. Consecutive undefined grid points, for which the LS values do not need to be stored, are combined in runs. It is advantageous to use two different run codes, depending on whether the corresponding run contains only grid points where the LS function is positive or negative, respectively. In this way the sign of the LS function is available for all grid points. This information is useful, since it reveals on which side of the surface a grid point is located.

To demonstrate, run-length encoding is applied to the two-dimensional example shown in Figure 3.3. There, a triangle is described by the LS. The LS function is resolved on a grid with extensions $12\times 12$ . Figure 3.4 shows the corresponding run-length encoded (RLE) data structure which consists of 4 arrays in order to store only the LS values of defined grid points near the boundary. To address array entries, zero based indexing is used.

Figure 3.3: A LS function representing a triangle is resolved on a $12\times 12$ grid. Only the LS of defined grid points (green) must be stored. Memory can be saved by not storing the LS values of all other positive (blue) and negative (red) undefined grid points. The LS values of all defined grid points are given on the right-hand side.

Figure 3.4: The RLE data structure for the example given in Figure 3.3. For each of the 12 grid lines along the ${x}_1$ -direction an index is stored in the start indices array to the corresponding run type sequence. Three different types of run codes can be distinguished: Undefined runs which are either positive (blue) or negative (red), and defined runs (green) whose run codes give the corresponding start indices in the LS values array. Another array stores the run breaks from which the start and end indices of a run can be obtained. The size of the run breaks array is always equal to the difference of the sizes of the run types array and the start indices array.

The LS values of all defined grid points are stored in lexicographical order in the LS values array. Sequences of positive undefined, negative undefined, or defined grid points are represented by integral run codes stored within the run types array. In case of a defined sequence the run code gives the corresponding start index in the LS values array. Grid indices at which new runs start are given in the run breaks array. Direct access to run codes for a specific line of grid points is provided by the start indices array. The size of this array is equal to the number of grid lines parallel to the ${x}_1$ -direction. In the two-dimensional case the size of this array is equal to the grid extension in the ${x}_2$ -direction, which is equal to 12 in this example. The index of the first run break for a given grid line can be obtained by subtracting the index of the corresponding entry in the start indices array from the content of the same entry.

The RLE data structure provides fast random access to LS values of defined grid points. The LS value of a certain grid point ${\vec{p}}=\left({p}_1,\ldots,{p}_{{D}}\right)$ can be found by accessing the corresponding RLE grid line through the start indices array. The array index of the grid line is calculated as $\sum_{i=2}^{{D}}({p}_i-{g}^{{\text{min}}}_i)\prod_{j=2}^{i-1}({g}^{{\text{max}}}_j-{g}^{\text{min}}_j+1)$ , where ${\vec{g}}^{{\text{min}}}$ and ${\vec{g}}^{\text{max}}$ denote the minimum and maximum index vectors of the grid. A binary search of ${p}_1$ within the corresponding run breaks is necessary to find the correct run code. If the run is defined, the index of the LS value of ${\vec{p}}$ can be calculated using the run code, the first grid index of the run obtained from the run breaks array or the grid extensions, and ${p}_1$ .

The complexity of accessing the LS value of a specific grid point is mainly given by the binary search, which scales logarithmically with the number of runs within a grid line. In the worst case, if all defined grid points belong to the same grid line and are separated by runs of undefined grid points (undefined runs), the complexity is of order ${\mathcal{O}}(\log{{N}_\text{D}})$ , where ${{N}_\text{D}}$ denotes the number of defined grid points. However, in practice a much better performance can be expected.

The memory requirements of the RLE data structure scale according to ${\mathcal{O}}({{N}_\text{D}}+\prod_{i=2}^{{D}}({g}^{{\text{max}}}_i-{g}^{\text{min}}_i+1))$ . The lexicographical order of LS values is very advantageous, because it allows fast serial processing. However, in contrast to tree data structures, since the data structure is based on arrays, it is not possible to add or remove grid points efficiently, except at the end. If the set of defined grid points changes, the entire data structure must be reset.