1. Introduction
  2. Boundary-Conforming Coordinate Systems
  3. Transformation Relations
  4. Numerical Implementation
  5. Truncation Error
  6. Elliptic Generation Systems
  7. Parabolic and Hyperbolic Generation Systems
  8. Algebraic Generation Systems
  9. Orthogonal Systems
  10. Conformal Mapping
  11. Adaptive Grids
  12. Appendix A
    Appendix B
    Appendix C

    Downloadable Version (PDF)
Numerical Grid Generation
Foundations and Applications
By: Joe E. Thompson, Z.U.A. Warsi and C. Wayne Mastin


          Numerical grid generation has now become a fairly common tool for use in the numerical solution of partial differential equations on arbitrarily shaped regions. This is especially true in computational fluid dynamics, from whence has come much of the impetus for the development of this technique, but the procedures are equally applicable to all physical problems that involve field solutions. Numerically generated grids have provided the key to removing the problem of boundary shape from finite difference methods, and these grids also can serve for the construction of finite element meshes. With such grids all numerical algorithms, finite difference or finite element, are implemented on a square grid in a rectangular computational region regardless of the shape and configuration of the physical region. (Finite volume methods are effectively a type of conservative finite difference method on these grids.)
          In this text, grid generation and the use thereof in numerical solutions of partial equations are both discussed. The intent was to provide the necessary basic information, from both the standpoint of mathematical background and from that of coding implementation, for numerical solutions of partial differential equations to be constructed on general regions. Since these numerical solutions are ultimately constructed on a square grid in a rectangular computational region, any solution algorithm that can treat equations with variable coefficients is basically applicable, and therefore discussion of specific algorithms is left to classical texts on the numerical solution of partial differential equations.
          The area of numerical grid generation is relatively young in practice, although its roots in mathematics are old. This somewhat eclectic area involves the engineer's feel for physical behavior, the mathematician's understanding of functional behavior, and a lot of imagination, with perhaps a little help from Urania. The physics of the problem at hand must ultimately direct the grid points to congregate so that a functional relationship on these points can represent the physical solution with sufficient accuracy. The mathematics controls the points by sensing the gradients in the evolving physical solution, evaluating the accuracy of the discrete representation of that solution, communicating the needs of the physics to the points, and by providing mutual communication among the points as they respond to the physics.
          Numerical grid generation can be thought of as a procedure for the orderly distribution of observers, or sampling stations, over a physical field in such a way that efficient communication among the observers is possible and that all physical phenomena on the entire continuous field may be represented with sufficient accuracy by this finite collection of observations. The structure of an intersecting net of families of coordinate lines allows the observers to be readily identified in relation to each other, and results in much more simple coding than would the use of a triangular structure or a random distribution of points. The grid generation system provides some influence of each observer on the others, so that if one moves to get into a better position for observation of the solution, its neighbors will follow to some extent in order to maintain smooth coverage of the field.
          Another way to think of the grid is as the structure on which the numerical solution is built. As the design of the lightest structure requires consideration of the load distribution, so the most economical distribution of grid points requires that the grid be influenced by both the geometric configuration and by the physical solution being done thereon. In any case, since resources are limited in any numerical solution, it is the function of the numerical grid generation to make the best use of the number of points that are available, and thus to make the grid points an active part of the numerical solution.
          This is a rapidly developing area, being now only about ten years old, and thus is still in search of new ideas. Therefore no book on the subject at this time could possibly be considered to be definitive. However, enough material has now accumulated in the literature, and enough basic concepts have emerged, that a fundamental text is now needed to meet the needs of the rapidly expanding circle of interest in the area. It is with the knowledge of both these needs and these limitations that this text has been written. Some of the techniques discussed will undoubtedly be superceded by better ideas, but the fundamental concepts should serve for understanding, and hopefully also for some inspiration, of new directions. The only background assumed of the student is a senior-level understanding of numerical analysis and partial differential equations. Concepts from differential geometry and tensor analysis are introduced and explained as needed.
          Numerical grid generation draws on various areas of mathematics, and emphasis throughout is placed on the development of the relations involved, as well as on the techniques of application. This text is intended to provide the student with the understanding of both the mathematical background and the application techniques necessary to generate grids and to develop codes based on numerically generated grids for the numerical solution of partial differential equations on regions of arbitrary shape.
          The writing of this text has been a cooperative effort over the last two years, spurred on by the institution of a graduate course in numerical grid generation, as well as an annual short course, at Mississippi State. The students in both of these courses have contributed significantly in revising the text as it evolved. The last appendix is the result of a class assignment prepared by Col. Hyun Jin Kim, graduate student in the computational fluid dynamics program, who also compiled the index. Our colleage, Dr. Helen V. McConnaughey of Mathematics contributed significantly through continual discussions and wrote most of Chapter IV.
          We are indebted to a large number of former students and fellow researchers around the world for the development of the ideas that have crystallized into numerical grid generation. The complete debt can be acknowledged only through mention of the bibliographies contained in the several surveys cited herein. A list here would either be too long to note the strongest influences or too short to acknowledge all the significant ones. We must, however, acknowledge the many long and fruitful discussions with Peter Eiseman of Columbia University.
          0f vital importance is the support that has been provided for the research from which the developments discussed in this book have emerged, including NASA; the research offices of the Air Force, Army, and Navy; the National Science Foundation, and various industrial concerns. The interest and contributions of a number of contract monitors has been essential over the years. We are especially appreciative of Bud Bobbitt and Jerry South of NASA Langley Research Center, who provided the initial support for an unknown with an idea.
          Particular debts are owed to W. H. Chu for an idea in the Journal of Computational Physics in 1971, and to Frank Thames who put the idea into a dissertation.
          In the preparation of the text we had the conscientious and untiring efforts of two most able secretaries, Rita Curry and Susan Triplett, who typed on in good spirits through a year of numerous revisions and frustrations as the text evolved.
          Finally, we were particularly fortunate to have the services of Yeon Seok Chae, graduate student in the computational fluid dynamics program and illustrator par excellence, who did all the figures with understanding of the intended meaning as well as artistic competence. His meticulous efforts were extensions of our thoughts.

Joe F. Thompson
Z. U. A. Warsi
C. Wayne Mastin
Mississippi State, Mississippi
January 1985