Applied Computational Fluid Dynamics Techniques: An Introduction Based on Finite Element Methods, 2nd Edition

2 DATA STRUCTURES AND ALGORITHMS

Data structures play a major role in any field solver. They enable the rapid access and manipulation of information, allowing significant simplifications in methodologies and code structure, as well as a drastic reduction in CPU requirements. Data structures are of eminent importance for field solvers based on unstructured grids, for which the data is unordered and must be retrieved from lists. It is therefore necessary to devote some attention to this area. This chapter describes the techniques most commonly used to store and manipulate the components of a grid, as well as the relation between the different possible data items and representations. The description starts from the fundamental data items required to describe a grid, proceeding to derived data structures, sorting and searching, and techniques to rapidly scan for spatial proximity. Even though the presentation is done with typical Fortran/C arrays, the principles and ideas are general: anyone handling grids, spatial data or search operations will have to devise similar algorithmic solutions.

2.1. Representation of a grid

If we assume that in order to solve numerically a PDE the geometrical domain is subdivided into small regions called elements, then the most basic task is how to represent in the code the discretization of the problem. For any given subregion or element, its spatial extent must be provided in order to define it. This is done by providing the coordinate information at ...