×

Optimal-transport – based mesh adaptivity on the plane and sphere using finite elements. (English) Zbl 1448.65143

Summary: In moving mesh methods, the underlying mesh is dynamically adapted without changing the connectivity of the mesh. We specifically consider the generation of meshes which are adapted to a scalar monitor function through equidistribution. Together with an optimal-transport condition, this leads to a Monge-Ampère equation for a scalar mesh potential. We adapt an existing finite element scheme for the standard Monge-Ampère equation to this mesh generation problem; this is a mixed finite element scheme, in which an extra discrete variable is introduced to represent the Hessian matrix of second derivatives. The problem we consider has additional nonlinearities over the basic Monge-Ampère equation due to the implicit dependence of the monitor function on the resulting mesh. We also derive an equivalent Monge-Ampère-like equation for generating meshes on the sphere. The finite element scheme is extended to the sphere, and we provide numerical examples. All numerical experiments are performed using the open-source finite element framework Firedrake.

MSC:

65M50 Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
35J96 Monge-Ampère equations
35K96 Parabolic Monge-Ampère equations
35R01 PDEs on manifolds
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. E. Aguilera and P. Morin, {\it On convex functions and the finite element method}, SIAM J. Numer. Anal., 47 (2009), pp. 3139-3157, . · Zbl 1204.65076
[2] M. S. Aln\ae s, A. Logg, K. B. Ø lgaard, M. E. Rognes, and G. N. Wells, {\it Unified form language: A domain-specific language for weak formulations of partial differential equations}, ACM Trans. Math. Software, 40 (2014), 9, . · Zbl 1308.65175
[3] G. Awanou, {\it Quadratic mixed finite element approximations of the Monge–Ampère equation in 2D}, Calcolo, 52 (2015), pp. 503-518, . · Zbl 1331.65158
[4] S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, D. A. May, L. C. McInnes, K. Rupp, P. Sanen, B. F. Smith, S. Zampini, H. Zhang, and H. Zhang, {\it PETSc Users Manual}, Tech. Report ANL-95/11 - Revision 3.8, Argonne National Laboratory, 2017, .
[5] S. Balay, W. D. Gropp, L. C. McInnes, and B. F. Smith, {\it Efficient management of parallelism in object oriented numerical software libraries}, in Modern Software Tools in Scientific Computing, E. Arge, A. M. Bruaset, and H. P. Langtangen, eds., Birkhäuser, 1997, pp. 163-202. · Zbl 0882.65154
[6] G. Beckett and J. Mackenzie, {\it Convergence analysis of finite difference approximations on equidistributed grids to a singularly perturbed boundary value problem}, Appl. Numer. Math., 35 (2000), pp. 87-109, . · Zbl 0963.65086
[7] J.-D. Benamou, B. D. Froese, and A. M. Oberman, {\it Two numerical methods for the elliptic Monge-Ampère equation}, ESAIM Math. Model. Numer. Anal., 44 (2010), pp. 737-758, . · Zbl 1192.65138
[8] J.-D. Benamou, B. D. Froese, and A. M. Oberman, {\it Numerical solution of the optimal transportation problem using the Monge–Ampère equation}, J. Comput. Phys., 260 (2014), pp. 107-126, . · Zbl 1349.65554
[9] E. Bernsen, O. Bokhove, and J. J. van der Vegt, {\it A (dis)continuous finite element model for generalized 2D vorticity dynamics}, J. Comput. Phys., 211 (2006), pp. 719-747, . · Zbl 1138.76380
[10] Y. Brenier, {\it Polar factorization and monotone rearrangement of vector-valued functions}, Comm. Pure Appl. Math., 44 (1991), pp. 375-417, . · Zbl 0738.46011
[11] S. C. Brenner, T. Gudi, M. Neilan, and L.-y. Sung, {\it \(\mathcal{C}^0\) penalty methods for the fully nonlinear Monge-Ampère equation}, Math. Comp., 80 (2011), pp. 1979-1995, . · Zbl 1228.65220
[12] S. C. Brenner and M. Neilan, {\it Finite element approximations of the three dimensional Monge-Ampère equation}, ESAIM Math. Model. Numer. Anal., 46 (2012), pp. 979-1001, . · Zbl 1272.65088
[13] J. Brown, M. G. Knepley, D. A. May, L. C. McInnes, and B. Smith, {\it Composable linear solvers for multiphysics}, in Proc. 11th International Symposium on Parallel and Distributed Computing, IEEE, 2012, pp. 55-62, .
[14] P. Browne, C. Budd, C. Piccolo, and M. Cullen, {\it Fast three dimensional r-adaptive mesh redistribution}, J. Comput. Phys., 275 (2014), pp. 174-196, . · Zbl 1349.65419
[15] P. Browne, J. Prettyman, H. Weller, T. Pryer, and J. Van lent, {\it Nonlinear Solution Techniques for Solving a Monge-Ampère Equation for Redistribution of a Mesh}, preprint, , 2016.
[16] P. R. Brune, M. G. Knepley, B. F. Smith, and X. Tu, {\it Composing scalable nonlinear algebraic solvers}, SIAM Rev., 57 (2015), pp. 535-565, . · Zbl 1336.65030
[17] C. Budd, M. Cullen, and E. Walsh, {\it Monge–Ampére based moving mesh methods for numerical weather prediction, with applications to the Eady problem}, J. Comput. Phys., 236 (2013), pp. 247-270, . · Zbl 1286.65178
[18] C. J. Budd, W. Huang, and R. D. Russell, {\it Adaptivity with moving grids}, Acta Numer., 18 (2009), pp. 111-241, . · Zbl 1181.65122
[19] C. J. Budd, A. T. T. McRae, and C. J. Cotter, {\it The Geometry of Optimally Transported Meshes on the Sphere}, preprint, , 2017; J. Comput. Phys., submitted. · Zbl 1416.65323
[20] C. Budd, R. Russell, and E. Walsh, {\it The geometry of r-adaptive meshes generated using optimal transport methods}, J. Comput. Phys., 282 (2015), pp. 113-137, . · Zbl 1352.65603
[21] C. J. Budd and J. F. Williams, {\it Parabolic Monge–Ampère methods for blow-up problems in several spatial dimensions}, J. Phys. A, 39 (2006), pp. 5425-5444, . · Zbl 1096.35070
[22] C. J. Budd and J. F. Williams, {\it Moving mesh generation using the parabolic Monge–Ampère equation}, SIAM J. Sci. Comput., 31 (2009), pp. 3438-3465, . · Zbl 1200.65099
[23] L. Chacón, G. Delzanno, and J. Finn, {\it Robust, multidimensional mesh-motion based on Monge–Kantorovich equidistribution}, J. Comput. Phys., 230 (2011), pp. 87-103, . · Zbl 1205.65260
[25] L. D. Dalcin, R. R. Paz, P. A. Kler, and A. Cosimo, {\it Parallel distributed computing using Python}, Adv. Water Res., 34 (2011), pp. 1124-1139, .
[26] E. Dean and R. Glowinski, {\it Numerical methods for fully nonlinear elliptic equations of the Monge–Ampère type}, Comput. Methods Appl. Mech. Engrg., 195 (2006), pp. 1344-1386, . · Zbl 1119.65116
[27] E. J. Dean and R. Glowinski, {\it An augmented Lagrangian approach to the numerical solution of the Dirichlet problem for the elliptic Monge-Ampère equation in two dimensions}, Electron. Trans. Numer. Anal., 22 (2006), pp. 71-96. · Zbl 1112.65119
[28] G. Delzanno, L. Chacón, J. Finn, Y. Chung, and G. Lapenta, {\it An optimal robust equidistribution method for two-dimensional grid adaptation based on Monge–Kantorovich optimization}, J. Comput. Phys., 227 (2008), pp. 9841-9864, . · Zbl 1155.65394
[29] G. L. Delzanno and J. M. Finn, {\it Generalized Monge–Kantorovich optimization for grid generation and adaptation in \(L_p\)}, SIAM J. Sci. Comput., 32 (2010), pp. 3524-3547, . · Zbl 1220.49020
[30] G. S. Dietachmayer and K. K. Droegemeier, {\it Application of continuous dynamic grid adaption techniques to meteorological modeling. Part \textupI: Basic formulation and accuracy}, Monthly Weather Review, 120 (1992), pp. 1675-1706, .
[31] X. Feng and M. Neilan, {\it Mixed finite element methods for the fully nonlinear Monge–Ampère equation based on the vanishing moment method}, SIAM J. Numer. Anal., 47 (2009), pp. 1226-1250, . · Zbl 1195.65170
[35] B. Froese and A. Oberman, {\it Fast finite difference solvers for singular solutions of the elliptic Monge–Ampère equation}, J. Comput. Phys., 230 (2011), pp. 818-834, . · Zbl 1206.65242
[36] B. D. Froese and A. M. Oberman, {\it Convergent finite difference solvers for viscosity solutions of the elliptic Monge–Ampère equation in dimensions two and higher}, SIAM J. Numer. Anal., 49 (2011), pp. 1692-1714, . · Zbl 1255.65195
[37] M. Homolya and D. A. Ham, {\it A parallel edge orientation algorithm for quadrilateral meshes}, SIAM J. Sci. Comput., 38 (2016), pp. S48-S61, . · Zbl 1404.65266
[38] M. Homolya, R. C. Kirby, and D. A. Ham, {\it Exposing and Exploiting Structure: Optimal Code Generation for High-Order Finite Element Methods}, preprint, , 2017; ACM Trans. Math. Software, submitted.
[39] M. Homolya, L. Mitchell, F. Luporini, and D. A. Ham, {\it TSFC: A structure-preserving form compiler}, SIAM J. Sci. Comput., to appear. Preprint version available at . · Zbl 1388.68020
[40] W. Huang and R. D. Russell, {\it Adaptive Moving Mesh Methods}, Appl. Math. Sci. 174, Springer, 2011, . · Zbl 1227.65090
[41] E. Jones, T. Oliphant, P. Peterson, et al., {\it SciPy: Open Source Scientific Tools for Python}, 2001, (accessed 2017-06-26).
[42] C. Kühnlein, P. K. Smolarkiewicz, and A. Dörnbrack, {\it Modelling atmospheric flows with adaptive moving meshes}, J. Comput. Phys., 231 (2012), pp. 2741-2763, . · Zbl 1426.76390
[43] O. Lakkis and T. Pryer, {\it A finite element method for second order nonvariational elliptic problems}, SIAM J. Sci. Comput., 33 (2011), pp. 786-801, . · Zbl 1227.65114
[44] O. Lakkis and T. Pryer, {\it A finite element method for nonlinear elliptic problems}, SIAM J. Sci. Comput., 35 (2013), pp. A2025-A2045, . · Zbl 1362.65126
[45] G. Loeper and F. Rapetti, {\it Numerical solution of the Monge–Ampère equation by a Newton’s algorithm}, C. R. Math. Acad. Sci. Paris, 340 (2005), pp. 319-324, . · Zbl 1067.65119
[46] F. Luporini, D. A. Ham, and P. H. J. Kelly, {\it An algorithm for the optimization of finite element integration loops}, ACM Trans. Math. Software, 44 (2017), 3, . · Zbl 1380.65381
[47] K.-A. Mardal and R. Winther, {\it Preconditioning discretizations of systems of partial differential equations}, Numer. Linear Algebra Appl., 18 (2011), pp. 1-40, . · Zbl 1249.65246
[48] R. J. McCann, {\it Polar factorization of maps on Riemannian manifolds}, Geom. Funct. Anal., 11 (2001), pp. 589-608, . · Zbl 1011.58009
[49] A. T. T. McRae, G.-T. Bercea, L. Mitchell, D. A. Ham, and C. J. Cotter, {\it Automated generation and symbolic manipulation of tensor product finite elements}, SIAM J. Sci. Comput., 38 (2016), pp. S25-S47, . · Zbl 1352.65615
[50] M. Neilan, {\it Finite element methods for fully nonlinear second order PDEs based on a discrete Hessian with applications to the Monge–Ampère equation}, J. Comput. Appl. Math., 263 (2014), pp. 351-369, . · Zbl 1301.65124
[51] V. Oliker and L. Prussner, {\it On the numerical solution of the equation \((^2z/ x^2)(^2z/ y^2)-(^2z/ x y)^2=f\) and its discretizations, I}, Numer. Math., 54 (1989), pp. 271-293, . · Zbl 0659.65116
[54] C. Piccolo and M. Cullen, {\it Adaptive mesh method in the Met Office variational data assimilation system}, Quart. J. Roy. Meteorological Soc. A, 137 (2011), pp. 631-640, .
[55] C. Piccolo and M. Cullen, {\it A new implementation of the adaptive mesh transform in the Met Office 3D-VAR system}, Quart. J. Roy. Meteorological Soc. B, 138 (2012), pp. 1560-1570, .
[56] J. M. Prusa and P. K. Smolarkiewicz, {\it An all-scale anelastic model for geophysical flows: Dynamic grid deformation}, J. Comput. Phys., 190 (2003), pp. 601-622, . · Zbl 1076.86001
[58] F. Rathgeber, D. A. Ham, L. Mitchell, M. Lange, F. Luporini, A. T. T. McRae, G.-T. Bercea, G. R. Markall, and P. H. J. Kelly, {\it Firedrake: Automating the finite element method by composing abstractions}, ACM Trans. Math. Software, 43 (2017), 24, . · Zbl 1396.65144
[59] T. D. Ringler, D. Jacobsen, M. Gunzburger, L. Ju, M. Duda, and W. Skamarock, {\it Exploring a multiresolution modeling approach within the shallow-water equations}, Monthly Weather Rev., 139 (2011), pp. 3348-3368, .
[60] M. E. Rognes, D. A. Ham, C. J. Cotter, and A. T. T. McRae, {\it Automating the solution of PDEs on the sphere and other manifolds in FEniCS 1.2}, Geosci. Model Develop., 6 (2013), pp. 2099-2119, .
[61] C.-W. Shu and S. Osher, {\it Efficient implementation of essentially non-oscillatory shock-capturing schemes}, J. Comput. Phys., 77 (1988), pp. 439-471, . · Zbl 0653.65072
[62] P. K. Smolarkiewicz and J. M. Prusa, {\it Towards mesh adaptivity for geophysical turbulence: Continuous mapping approach}, Int. J. Numer. Methods Fluids, 47 (2005), pp. 789-801, . · Zbl 1134.86005
[63] M. Sulman, J. Williams, and R. Russell, {\it Optimal mass transport for higher dimensional adaptive grid generation}, J. Comput. Phys., 230 (2011), pp. 3302-3330, . · Zbl 1218.65065
[66] H. Weller, P. Browne, C. Budd, and M. Cullen, {\it Mesh adaptation on the sphere using optimal transport and the numerical solution of a Monge–Ampère type equation}, J. Comput. Phys., 308 (2016), pp. 102-123, . · Zbl 1351.86008
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.