Generation of computational grids using optimization

A method for generation of computational grids using principles of nonlinear programming (optimization) is described. Grids are generated so that certain discrete measures of grid smoothness and orthogonality are max- imized using a fast iterative optimization procedure. The method can also be used to improve an existing grid ir- respective of the method used for its generation. If the original grid contains regions of overlap (nonpositive Jacobian), this method is capable of unraveling the grid and making it useful for computations. The iterative op- timization procedure is efficient due to the use of a conjugate direction method with exact line searching. Examples are given of the application of this technique to two- and three-dimensional computational grids. The extension of the method to generate solution adaptive grids is discussed. N the past few years, there has been a great deal of interest in the development of computational grid-generation techniques1 for discretizing complex regions for the numerical solution of partial differential equations. The commonly used grid-generation methods have achieved a high degree of sophistication and ease of use. However, for complex con- figurations, the existing methods do not always produce ac- ceptable grids for computations. Grid-quality deterioration is especially apparent in three-dimensional grid-generation methods and when two-dimensional grids are combined to form a three-dimensio nal grid.2'3 In addition to grid-quality problems, many methods suffer from computational ineffi- ciency. For these reasons, the authors have perceived a need for a grid-generatio n method that could be used to improve the quality of a given computational grid. In addition, the method should be capable of serving as a stand-alone grid- generation procedure, independent of other techniques. The basic concept behind this grid-generation method is to assume from the outset that the grid to be generated or op- timized consists of straight-line segments joining the nodal grid points. This is in contrast to methods that solve elliptic, parabolic, or hyperbolic partial differential equations or use conformal mapping. These methods are based on con- tinuous, not discrete, coordinate transformations and, therefore, suffer from discretization errors for any grid con- sisting of a finite number of grid points. The grid-generation technique described herein formulates discrete measures of grid smoothness and orthogonality at each grid point and, therefore, does not suffer from truncation errors on coarse grids. These measures of grid quality are then minimized us- ing a conjugate direction procedure with exact line searching. The resulting grids are optimal with respect to the particular smoothness and orthogonality measures chosen, and there are many possible choices for their exact forms. The next section describes the formulation of the method followed by some typical results of using this method to im- prove existing grids or generate new grids. Finally, exten- sions of the method for generating solution adaptive grids are discussed, and other areas of possible future research are pointed out. Analysis The formulation of the method will be illustrated for two- dimensional grids. The details of the method for the three- dimensional case are given in the Appendix. We will discuss the grid-generation method by first noting similarities with the Saltzman-Brackbill4 variational grid- generation method. In the variational method, two func- tionals are introduced that provide measures of grid smoothness