×

An optimal robust equidistribution method for two-dimensional grid adaptation based on Monge-Kantorovich optimization. (English) Zbl 1155.65394

Summary: A new cell-area equidistribution method for two-dimensional grid adaptation, based on Monge-Kantorovich optimization (or Monge-Kantorovich optimal transport), is presented. The method is based on a rigorous variational principle, in which the \(L_{2}\) norm of the grid displacement is minimized, constrained locally to produce a prescribed positive-definite cell volume distribution. The procedure involves solving the Monge-Ampère equation: A single, nonlinear, elliptic scalar equation with no free parameters, and with proved existence and uniqueness theorems. We show that, for sufficiently small grid displacement, this method also minimizes the mean grid-cell distortion, measured by the trace of the metric tensor. We solve the Monge-Ampère equation numerically with a Jacobian-Free Newton-Krylov method. The ellipticity property of the Monge-Ampère equation allows multigrid preconditioning techniques to be used effectively, delivering a scalable algorithm under grid refinement. Several challenging test cases demonstrate that this method produces optimal grids in which the constraint is satisfied numerically to truncation error. We also compare this method to the well known deformation method [G. Liao and D. Anderson, Appl. Anal. 44, No. 3–4, 285–298 (1992; Zbl 0794.65085)]. We show that the new method achieves the desired equidistributed grid using comparable computational time, but with considerably better grid quality than the deformation method.

MSC:

65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs

Citations:

Zbl 0794.65085

Software:

KELLEY
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Thompson, J. F., Survey of dynamically-adaptive grids in the numerical solution of partial differential equations, Applied Numerical Mathematics, 1, 1, 3-27 (1985) · Zbl 0551.65081
[2] Eiseman, P. R., Adaptive grid generation, Computer Methods in Applied Mechanics and Engineering, 64, 1-3, 321-376 (1987) · Zbl 0636.65126
[3] Anderson, D. A., Equidistribution schemes, Poisson generators, and adaptive grids, Applied Mathematics and Computation, 24, 3, 211-227 (1987) · Zbl 0636.65125
[4] Huang, W.; Ren, Y.; Russell, R. D., Moving mesh partial differential equations (MMPDES) based on the equidistribution principle, SIAM J. Numer. Anal., 31, 3, 709-730 (1994) · Zbl 0806.65092
[5] Baines, M. J., Least squares and approximate equidistribution in multidimensions, Numerical Methods for Partial Differential Equations, 15, 5, 605-615 (1999) · Zbl 0941.65085
[6] Lapenta, G., Variational grid adaptation based on the minimization of local truncation error: Time independent problems, Journal of Computational Physics, 193, 159 (2004) · Zbl 1036.65104
[7] Thompson, J. F.; Warsi, Z. A.; Mastin, C. W., Numerical Grid Generation: Foundations and Applications (1985), North-Holland: North-Holland New York · Zbl 0598.65086
[8] Liseikin, V. D., Grid Generation Methods (1999), Springer: Springer Berlin, New York · Zbl 0949.65098
[9] Winslow, A., Numerical solution of the quasi-linear poisson equation in a nonuniform triangle mesh, Journal of Computational Physics, 1, 149 (1967)
[10] A. Winslow, Adaptive Mesh Zoning by the Equipotential Method, UCID-19062, Lawrence Livermore National Laboratory, 1981.; A. Winslow, Adaptive Mesh Zoning by the Equipotential Method, UCID-19062, Lawrence Livermore National Laboratory, 1981.
[11] Brackbill, J. U.; Saltzman, J. S., Adaptive zoning for singular problems in 2 dimensions, Journal of Computational Physics, 46, 3, 342-368 (1982) · Zbl 0489.76007
[12] Dvinsky, A. S., Adaptive grid generation from Harmonic maps, Journal of Computational Physics, 95, 450-476 (1991) · Zbl 0733.65074
[13] Brackbill, J. U., An adaptive grid with directional control, Journal of Computational Physics, 108, 38-50 (1993) · Zbl 0832.65132
[14] Cao, W.; Huang, W.; Russell, R. D., An r-adaptive finite element method based upon moving mesh pdes, Journal of Computational Physics, 149, 221-244 (1999) · Zbl 0923.65062
[15] Cao, W.; Huang, W.; Russell, R. D., A study of monitor functions for two-dimensional adaptive grid generation, SIAM J. Sci. Comput., 20, 6, 1978-1994 (1999) · Zbl 0937.65104
[16] Hamilton, R., Harmonic maps of manifolds with boundary, (Lecture Notes in Mathematics, vol. 471 (1975), Springer-Verlag: Springer-Verlag New York) · Zbl 0308.35003
[17] Schoen, R.; Yau, S. T., On univalent harmonic maps between surfaces, Inventiones Mathematicae, 44, 265-278 (1978) · Zbl 0388.58005
[18] Huang, W., Variational mesh adaptation: isotropy and equidistribution, Journal of Computational Physics, 174, 903-924 (2001) · Zbl 0991.65131
[19] R.I. Kreis, H.A. Hassan, F.C. Thames, Application of a variational method for generating adaptive grids, in: AIAA 23rd Aerospace Sciences Meeting, Reno, NV, 1985, pp. 85-0487.; R.I. Kreis, H.A. Hassan, F.C. Thames, Application of a variational method for generating adaptive grids, in: AIAA 23rd Aerospace Sciences Meeting, Reno, NV, 1985, pp. 85-0487. · Zbl 0592.76082
[20] Chacón, L.; Lapenta, G., A fully implicit, nonlinear adaptive grid strategy, Journal of Computational Physics, 212, 2, 703 (2006) · Zbl 1083.65110
[21] Thompson, J. F.; Thames, F. C.; Mastin, C. W., Automatic numerical generation of body fitted curvilinear coordinate system for field containing any number of arbitrary two dimensional bodies (appl. to airfoils), Journal of Computational Physics, 15, 3, 299-319 (1974) · Zbl 0283.76011
[22] Knupp, P. M., Jacobian-weighted elliptic grid generation, SIAM Journal on Scientific Computing, 17, 6, 1475-1490 (1996) · Zbl 0860.65114
[23] Kania, L., Elliptic adaptive grid generation and area equidistribution, International Journal for Numerical Methods in Fluids, 30, 5, 481-491 (1999) · Zbl 0946.76080
[24] Huang, W.; Sloan, D. M., A simple adaptive grid method in two dimensions, SIAM Journal on Scientific Computing, 15, 4, 776-797 (1994) · Zbl 0809.65096
[25] Castillo, J.; Pedersen, E. M., Solution adaptive direct variational grids for fluid flow calculations, Journal of Computational and Applied Mathematics, 67, 2, 343-370 (1996) · Zbl 0856.76039
[26] Chen, T. F.; Yang, H. D., Numerical construction of optimal adaptive grids in two spatial dimensions, Computers and Mathematics with Applications, 39, 12, 101-120 (2000) · Zbl 0964.65124
[27] Yang, J.-C.; Soni, B. K., Structured adaptive grid generation, Applied Mathematics and Computation, 65, 1-3, 265-278 (1994) · Zbl 0811.65077
[28] D.A. Anderson, Adaptive grid scheme controlling cell area/volume, in: AIAA 25rd Aerospace Sciences Meeting, Reno, NV, 1987, pp. 87-0202.; D.A. Anderson, Adaptive grid scheme controlling cell area/volume, in: AIAA 25rd Aerospace Sciences Meeting, Reno, NV, 1987, pp. 87-0202.
[29] Liao, G.; Anderson, D., A new approach to grid generation, Applicable Analysis, 44, 285-297 (1992) · Zbl 0794.65085
[30] Moser, J., On volume elements on a manifold, Transactions of the American Mathematical Society, 120, 2, 286-294 (1965) · Zbl 0141.19407
[31] Dacorogna, B.; Moser, J., On a partial-differential equation involving the Jacobian determinant, Annales de l’Institut Henri Poincaré. Analyse non Linéaire, 7, 1, 1-26 (1990) · Zbl 0707.35041
[32] G. Monge, Mémoire sur la théorie des déblais at des remblais, Histoire de l’Académie Royale des Sciences de Paris (1781) 666-704.; G. Monge, Mémoire sur la théorie des déblais at des remblais, Histoire de l’Académie Royale des Sciences de Paris (1781) 666-704.
[33] Kantorovich, L. V., On the translocation of masses, C.R. (Doklady) Acad. Sci. URSS (N.S.), 37, 199-201 (1942) · Zbl 0061.09705
[34] Evans, L. C., Partial Differential Equations (1999), American Mathematical Society · Zbl 0920.49004
[35] Caffarelli, L.; Nirenberg, L.; Spruck, J., The Dirichlet problem for nonlinear 2nd-order elliptic equations I. Monge-Ampère equation, Communications on Pure and Applied Mathematics, 37, 3, 369-402 (1984) · Zbl 0598.35047
[36] Budd, C. J.; Williams, J. F., Parabolic Monge-Ampère methods for blow-up problems in several spatial dimensions, Journal of Physics A, 39, 5425 (2006) · Zbl 1096.35070
[37] J.M. Finn, G.L. Delzanno, L. Chacón, Grid generation and adaptation by Monge-Kantorovich optimization in two and three dimensions, in: 17th International Meshing Roundtable, Pittsburgh, PA, USA (accepted for publication).; J.M. Finn, G.L. Delzanno, L. Chacón, Grid generation and adaptation by Monge-Kantorovich optimization in two and three dimensions, in: 17th International Meshing Roundtable, Pittsburgh, PA, USA (accepted for publication). · Zbl 1220.49020
[38] Li, S.; Petzold, L., Moving mesh methods with upwinding schemes for time dependent PDEs, Journal of Computational Physics, 131, 368-377 (1997) · Zbl 0870.65076
[39] Brenier, Y., Polar factorization and monotone rearrangement of vector-valued functions, Communications on Pure and Applied Mathematics, 44, 375 (1991) · Zbl 0738.46011
[40] L.C. Evans, Partial differential equations and Monge-Kantorovich mass transfer, in: S.T. Yau (Ed.), Current Developments in Mathematics, 1997.; L.C. Evans, Partial differential equations and Monge-Kantorovich mass transfer, in: S.T. Yau (Ed.), Current Developments in Mathematics, 1997.
[41] Kelley, C. T., Iterative Methods for Linear and Nonlinear Equations (1995), SIAM: SIAM Philadelphia · Zbl 0832.65046
[42] Dembo, R.; Eisenstat, S.; Steihaug, R., Inexact Newton methods, Journal of Numerical Analysis, 19, 400 (1982) · Zbl 0478.65030
[43] Chacón, L.; Knoll, D. A., A 2D high-\(β\) Hall MHD implicit nonlinear solver, Journal of Computational Physics, 188, 2, 573-592 (2003) · Zbl 1127.76375
[44] Knoll, D. A.; Rider, W. J., Multigrid preconditioned Newton-Krylov method, SIAM Journal on Scientific Computing, 21, 2, 691-710 (1999) · Zbl 0952.65102
[45] Rider, W. J.; Knoll, D. A.; Olson, G. L., A multigrid Newton-Krylov method for multimaterial equilibrium radiation diffusion, Journal of Computational Physics, 152, 1, 164-191 (1999) · Zbl 0944.85002
[46] Knoll, D. A.; Mousseau, V. A., On Newton-Krylov multigrid methods for the incompressible Navier-Stokes equations, Journal of Computational Physics, 163, 1, 262-267 (2000) · Zbl 0994.76055
[47] Pernice, M.; Tocci, M. D., A multigrid-preconditioned Newton-Krylov method for the incompressible Navier-Stokes equations, SIAM Journal on Scientific Computing, 23, 2, 398-418 (2001) · Zbl 0995.76061
[48] Chacón, L.; Barnes, D. C.; Knoll, D. A.; Miley, G. H., An implicit energy-conservative 2d Fokker-Planck algorithm. II. Jacobian-free Newton-Krylov solver, Journal of Computational Physics, 157, 2, 654-682 (2000) · Zbl 0961.76058
[49] Chacón, L.; Knoll, D. A.; Finn, J. M., An implicit, nonlinear reduced resistive MHD solver, Journal of Computational Physics, 178, 1, 15-36 (2002) · Zbl 1139.76328
[50] Briggs, W. L., A Multigrid Tutorial (1987), SIAM: SIAM Philadelphia · Zbl 0659.65095
[51] Knoll, D. A.; Lapenta, G.; Brackbill, J. U., A multilevel iterative field solver for implicit, kinetic, plasma simulation, Journal of Computational Physics, 149, 2, 377-388 (1999) · Zbl 0934.76048
[52] Brackbill, J. U.; Ruppel, H. M., FLIP: a method for adaptively zoned, particle-in-cell calculations of fluid flows in two dimensions, Journal of Computational Physics, 65, 2, 314-343 (1986) · Zbl 0592.76090
[53] Brackbill, J. U., FLIP MHD: a particle-in-cell method for magnetohydrodynamics, Journal of Computational Physics, 96, 1, 163-192 (1991) · Zbl 0726.76078
[54] Sulsky, D.; Brackbill, J. U., A numerical method for suspension flow, Journal of Computational Physics, 96, 2, 339-368 (1991) · Zbl 0727.76082
[55] Hansen, G. A.; Douglass, R. W.; Zardecki, A., Mesh Enhancement: Selected Elliptic Methods, Foundations, and Applications (2005), Imperial College Press · Zbl 1079.65119
[56] Knupp, P. M.; Steinberg, S., Fundamentals of Grid Generation (1993), CRC-Press
[57] Banyaga, A., Formes volume sur es varietes a bord, Enseignement Mathematics, 20, 127-131 (1974) · Zbl 0281.58001
[58] Cho, M.; Jun, S., r-Adaptive mesh generation for shell finite element analysis, Journal of Computational Physics, 199, 1, 291-316 (2004) · Zbl 1127.74348
[59] Liu, F.; Ji, S. H.; Liao, G. J., Adaptive grid method and its application to steady Euler flow calculations, SIAM Journal on Scientific Computing, 20, 3, 811-825 (1998) · Zbl 0929.76091
[60] Semper, B.; Liao, G., A moving grid finite-element method using grid deformation, Numerical Method for PDEs, 11, 603-615 (1995) · Zbl 0838.65093
[61] Bochev, P.; Liao, G.; Pena, G. D., Analysis and computation of adaptive moving grids by deformation, Numerical Method for PDEs, 12, 489-506 (1996) · Zbl 0856.65109
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.