Rectangular Grids
Table of Contents
Most techniques for doing computational fluid dynamics rely on the subdivision of space into a grid of discrete volume elements in which average values of flow variables can be defined. The simplest kind of grid is one composed of rectangular elements defined by a set of planes perpendicular to each of the coordinate axes (x,y,z). The spacing between parallel planes may be constant or variable. The former is often referred to as a “uniform” rectangular grid, while the latter is a “non-uniform” rectangular grid.
Why are Rectangular Grids Simple?
Rectangular grids are simple because they are very easy to generate. It is only necessary to define the beginning and ending coordinate of the grid in each coordinate direction, and in the spacing between the planes subdividing the space to be modeled.
Pros and Cons of Rectangular Grids
As with any gridding system, there are pros and cons to contend with (see, for example, Free Gridding Saves Time). One pro for rectangular grids is that the amount of information to be stored for describing the grid is minimal. A con is that a region to be modeled may not fit into a rectangular region. For example, think of a bird’s eye view of a winding river, which when set in a rectangular region, may only occupy a small portion of the area of the rectangle. In such a case, most of the grid elements lie outside the river and would be a computational burden.
Difference Equations are Simpler
Another pro for a rectangular grid is that difference equations are generally simpler than they are in a non-rectangular grid. For instance, in three dimensions an approximation to the Navier-Stokes equation for the velocity in an element need only involve the six adjacent elements, that is, two neighbors in each of three coordinate directions. In contrast, a non-rectangular grid typically requires a coupling to all the surrounding elements in a 3x3x3=27 array surrounding the central element.
Numerical Accuracy is Best When Grid Elements are Uniform
As a general rule, numerical accuracy associated with finite difference equations is best when grid elements are uniform. This is because numerical approximations to partial differential equations, by definition, involve the rate of change of spatial and temporal values of physical quantities. Evaluating the change between values of quantities on either side of an element is most accurate when the elements are uniform because higher order terms will then, as a rule, cancel by symmetry. When non-uniform grid elements are used, more complicated numerical approximations are usually needed to preserve accuracy (see the Appendix for an example).
Weighing the Pros and Cons of Rectangular Grids
By weighing the pros and cons it can be seen that simple rectangular grids have many good properties, but the limitations they have for accommodating complex geometric shapes can limit their usefulness. In the remainder of this article, several conceptually simple techniques are described that greatly extend the usefulness of rectangular grids without sacrificing their good properties. For simplicity of presentation only two-dimensional situations will be described, however, the extension to three-dimensions is completely straightforward.
Notation for Rectangular Grids
In a rectangular (2D) grid, the elements are typically labeled by integers i and j in the x and y coordinate directions, respectively. An element (i,j) has principal neighbors (i-1,j), (i+1,j), (i,j-1) and (i,j+1). Physical properties in a cell are stored as values of two-dimensional arrays such as p(i,j) for the pressure of element (i,j). When programming difference equations, the use of repeated indexed arrays requires the compiler to perform the index shifts, e.g., i+1 or j-1, as arithmetic operations in order to evaluate the memory locations of these quantities.
To save computational time it is useful to replace multiple-indexed quantities by single-indexed arrays. Multiple array locations are computed only once at the beginning of a string of computations, for instance, the notation ipj=i+1,j or ijm=i,j-1 are short, simple and easy to read single indices. They are easy to read by remembering that ip means i plus 1 and jm means j minus 1, etc. Thus, a double-indexed quantity P(i+1,j-1) would be replaced by the single-indexed quantity P(ipjm), and so forth. Not only is this notation easy to use and saves computational time, it will be seen below that it has another very useful property.
Multiple Grid Blocks
A good way to extend the usefulness of rectangular grids is to employ multiple rectangular grids that are coupled at their boundaries. There are two simple possibilities as illustrated in Fig. 1A and Fig. 1B. The linked blocks are connected by boundary conditions where the blocks are adjacent to one another. The nested blocks are superimposed on one another and use boundary conditions to couple the nested block to the containing block.
This multi-block capability greatly extends the usefulness of rectangular grids, as the linked-block feature allows for more extended geometric regions to be modeled with fewer grid elements. The nested-block feature is very useful for locally increasing the resolution of a simulation without having to endure the cost of simulating the finer resolution throughout the full region.
Distributed Memory Parallelization
The multi-block feature also offers a natural way of domain decomposition for distributed memory parallelization. Updating of solution data at inter-block boundaries then requires an exchange of that data between compute nodes of the cluster using an interconnect.
Unstructured Grid Blocks
A further generalization can be made that allows considerably more efficiency in the gridding of complex geometric regions. If the simple, rectangular ordering of elements is replaced by lists that define which elements are adjacent to one another, then all unneeded elements can be eliminated from the grid. This frees up memory and forces solver routines to simply run through a list of active grid elements, further saving computational time. A simple illustration of such an “unstructured” grid is illustrated in Fig. 2.
Changing from a structured, rectangular grid, where neighboring elements have memory locations that are easy to compute, to an unstructured set of elements may seem at first sight to be a daunting task. However, using the single index notation described earlier where, for example, location (i, j+1) is replace by ijp, makes this transition quite easy. All that is necessary is to redefine the single-indexed values using the list of neighboring elements and then all solver algorithms and routines can be used without further changes.
As with any unstructured grid, additional storage is required to be able to quickly find neighbor cell indices and other mesh-related quantities. A two-way mapping of the structured and unstructured grids onto each other provides an efficient way to navigate the unstructured grid without using significant memory resources.
Other variations of this idea are easy to imagine. For instance, if more than one set of physical properties are required in a given element, because it contains some mixture of materials (e.g., both fluid and solid), then an additional element could be added to the element list that is defined at the same location. The coincident elements would be identified in a special list intended for processing mixed elements.
Summary of the Simplest Gridding System
A short discussion has been given of what might be viewed as an evolutionary development of the simplest gridding system, a rectangular grid. Several stages of relatively easy adaptations are outlined as a means of addressing the demands for more sophisticated simulations while maintaining the many advantages of the original simple grid system.
Appendix: Illustration of Accuracy Considerations for Non-Uniform Grids
The following account has been adapted from the paper “Volume of Fluid (VOF) Method for the Dynamics of Free Boundaries,” by C.W. Hirt and B.D. Nichols, J. Comp. Phys. 39, 201 (1981).
A simple illustration of the difficulties that can occur in non-uniform grids is given by numerically approximating the term for advection of momentum of an incompressible fluid, which in divergence form is ∇•uu. The constant density of the fluid has been divided out from this expression. In one dimension this term is $latex \displaystyle \frac{\partial \left( uu \right)}{\partial x}.$
Here u is the fluid velocity in the x-direction. The divergence form is usually desirable because it is a simple way to insure a conservation of momentum. This may be seen by considering the control volume used for the discrete value of u located at the boundary between two grid elements as shown in Fig. A1 by the dashed lines. Placing the velocity at the boundary between two elements is referred to as the staggered grid arrangement often used for incompressible flow modeling.
In the divergence form, Gauss’ theorem may be used to convert the integrated values of the advective flux over the control volume to boundary fluxes at its sides. Then, the flux leaving one control volume will automatically be gained by the adjacent one and conservation during advection is guaranteed.
However, conservation in a non-uniform grid, does not automatically imply accuracy. To see this, suppose an upstream or donor difference approximation is used to approximate the advective flux (assuming all u values are positive for simplicity), which is known to provide a conditionally stable algorithm, $latex \displaystyle \frac{\partial uu}{\partial x}\approx \frac{{{u}_{i+1/2}}\left( {{u}_{i+3/2}}+{{u}_{i+1/2}} \right)/2-{{u}_{i-1/2}}\left( {{u}_{i+1/2}}+{{u}_{i-1/2}} \right)/2}{\left( \delta {{x}_{i}}+\delta {{x}_{i+1}} \right)/2}$
The notation ui+1/2 stands for the velocity assigned to the right edge of the ith element.
To check that this approximation is “consistent” with the original partial differential equation we expand all terms in the difference equation in a Taylor series about the location x=xi+1/2 where the u equation is evaluated (see Heuristic Analysis),
$latex \displaystyle \frac{\delta uu}{\delta x}\approx \frac{1}{2}\left( \frac{3\delta {{x}_{1}}+\delta {{x}_{i+1}}}{\delta {{x}_{1}}+\delta {{x}_{i+1}}} \right)\frac{\partial uu}{\partial x}+O\left( \delta x \right).$
Clearly, the right side does not agree with the left side to order δx when the element sizes are not equal. In other words, the difference approximation is not “consistent” since it does not agree with the original differential expression at zeroth order. It may be noted that, if instead of the upstream or donor approximation, a centered value for the fluxed velocity had been used, then the approximation would be first-order accurate in a non-uniform grid, instead of second-order as it is in a uniform grid. In other words, what seems like a straightforward approximation is one order less accurate in a non-uniform grid than in one that is uniform.
It does not necessarily follow that non-uniform grids are always less accurate because they may allow for finer zoning in localized regions where flow variables are expected to vary most rapidly. Nevertheless, non-uniform grids must be used with care. It is best, for example, to allow for gradual variations in element sizes to minimize the reduction in approximation order. It is also worthwhile to look for other approximations that do not lose their accuracy in a non-uniform grid. In this regard, it should be observed that the reason the conservation form of the advection term is less accurate is because the control volume is not centered about the position where the u variable is located. To avoid losing one order of approximation, the numerical approximation should have been corrected to account for the difference in locations of the variable being updated and the centroid of its control volume.
