A fast adaptive grid scheme for elliptic partial differential equations

ABSTRACT

We describe the Recursive Subdivision (RS) method-an efficient and effective adaptive grid scheme for two-dimensional elliptic partial differential equations (PDEs). The RS method generates a new grid by recursively subdividing a rectangular domain. We use a heuristic approach which attempts to equidistribute a given density function over the domain. The resulting grid is used to generate an adaptive grid domain mapping (AGDM), which may be applied to transform the PDE problem to another coordinate system. The PDE is then solved in the transformed coordinate system using a uniform grid. We believe parallelism is most easily exploited when computations are carried out on uniform grids; the AGDM framework allows the power of adaptation to be applied while still preserving this uniformity. Our method generates good adaptive grid domain mappings at a small cost compared to the cost of the entire computation. We describe the RS algorithm in detail, briefly describe the AGDM framework, and illustrate the effectiveness of our scheme on several realistic test problems.

REFERENCES

• 1: ADJERID, S., AND FLAHERTY, J.E. Adaptive finite element methods for parabolic systems in one and two space dimensions. Tech. Rep. 86-20. Rensselaer Polytechnic Institute, Troy, N.Y., 1986.
• 2: BABUSHKA, i., AND RHEINBOLDT, W.C. Error estimates for adaptive finite element computations. SIAM J. Numer. Anal. 15 (1978), 736-754.
• 3: Ivo Babuéska , J. Chandra , J. E. Flaherty, Adaptive Computational Methods for Partial Differential Equations, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 4: Marsha J. Berger, Adaptive Mesh Refinement for Parallel Processors, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.182-194, December 01-04, 1987
• 5: M. J. Berger , S. H. Bokhari, A partitioning strategy for nonuniform problems on multiprocessors, IEEE Transactions on Computers, v.36 n.5, p.570-580, May 1987 [doi>10.1109/TC.1987.1676942]
• 6: Marsha J. Berger , Joseph E. Oliger, Adaptive mesh refinement for hyperbolic partial differential equations, Stanford University, Stanford, CA, 1983
• 7: BRACKBILL, J. U., AND SALTZMAN, J.S. Adaptive zoning for singular problems in two dimensions. J. Comput. Phys. 46 (1982), 342-368.
• 8: DEBOOR, C. A Practical Guide to Splines. Springer-Verlag, New York, 1978.
• 9: DWYER, H. A., SMOOKE, M. D., AND KEE, R.J. Adaptive gridding for finite difference solutions to heat and mass transfer problems. In Numerical Grid Generation, J. F. Thompson, Ed. North- Holland, New York, 1982, pp. 339-356.
• 10: Wayne R. Dyksen , Calvin J. Ribbens, Interactive ELLPACK: an interactive problem-solving environment for elliptic partial differential equations, ACM Transactions on Mathematical Software (TOMS), v.13 n.2, p.113-132, June 1987 [doi>10.1145/328512.328515]
• 11: DYKSEN, W. R., RIBBENS, C. J., AND RICE, J.R. The performance of numerical methods for elliptic problems with mixed boundary conditions. Tech. Rep. CSD-TR 590. Computer Sciences Dept., Purdue Univ., West Lafayette, Ind., 1987, (to appear in Numer. Meth. PDEs).
• 12: EISENSTAT,. S. C., AND SCHULTZ, M.H. The complexity of partial differential equations. In Complexity of Sequential and Parallel Numerical Algorithms, J. F. Traub, Ed. Academic Press, New York, 1973, pp. 271-282.
• 13: FLAHERTY, J. E., COYLE, M., LUDWIG, R., AND DAVIS, S.F. Adaptive finite element methods for parabolic partial differential equations. In Adaptive Computational Methods for PDEs, I. Babushka, J. E. Flaherty, and J. Chandra, Eds. SIAM, Philadelphia, Pa., 1983, pp. 144-164.
• 14: GROPP, W. D. Local uniform mesh refinement on loosely-coupled parallel processors. Comput. Math. Appl. 15 (1988), 375-387.
• 15: HOUSTIS, E. N., AND RICE, J.R. High order methods for elliptic partial differential equations with singularities. Int. J. Numer. Meth. Eng. 18 (1982), 737-754.
• 16: Kenichi Matsuno , Harry A. Dwyer, Adaptive methods for elliptic grid generation, Journal of Computational Physics, v.77 n.1, p.40-52, July 1988 [doi>10.1016/0021-9991(88)90155-6]
• 17: MILLER, K., AND MILLER, R.N. Moving finite elements I. SIAM J. Numer. Anal. 18 (1981), 1019-1032.
• 18: RHEINBOLDT, W. C. On a theory of mesh-refinement processes. SIAM J. Numer. Anal. 17 (1980), 766-778.
• 19: Calvin John Ribbens, Domain mappings: a tool for the development of vector algorithms for numerical solutions of partial differential equations (adaptive grids, elliptic problems), 1986
• 20: RIBBENS, C.J. A priori grid adaption strategies for elliptic PDEs. In Advances in Computer Methods for Partial Differential Equations VI, (R. Vichnevetsky and R. S. Stepleman, Eds. IMACS, New Brunswick, N.J., 1987, pp. 102-107.
• 21: RIBBENS, C.J. A computational framework for constructing adaptive grid domain mappings. Tech. Rep. CSD-TR 673. Computer Science Dept., Purdue Univ., West Lafayette, Ind., 1987.
• 22: RIBBENS, C. J., AND RICE, J.R. Realistic pde solutions for nonrectangular domains. Tech. Rep. CSD-TR 639. Computer Science Dept., Purdue Univ., West Lafayette, Ind., 1986.
• 23: John Rischard Rice, Numerical Methods, Software and Analysis, McGraw-Hill, Inc., New York, NY, 1983
• 24: John R. Rice , Ronald F. Boisvert, Solving elliptic problems using ELLPACK, Springer-Verlag New York, Inc., New York, NY, 1985
• 25: RICE, J. R., HOUSTIS, E. N., AND DYKSEN, W.R. A population of linear, second order, elliptic partial differential equations on rectangular domain~. Math. Comput. 36 (1981), 475-484.
• 26: SEWELL, G. A finite element program with automatic user controlled mesh grading. In Advances in Computer Methods for Partial Differential Equations III, R. Vichnevetsky and R. S. Stepleman, Eds. IMACS, New Brunswick, N.J., 1979, pp. 8-10.
• 27: THOMPSON, J.F. A survey of dynamically-adaptive grids in the numerical solution of partial differential equations. American Institute of Aeronautics and Astronautics, Tech. Rep. 84-1606, New York, 1984.
• 28: Joe F. Thompson , Z. U.A. Warsi , C. Wayne Mastin, Numerical grid generation: foundations and applications, Elsevier North-Holland, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Elliptic equations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms