×

An efficient boundary integral scheme for the MBO threshold dynamics method via the NUFFT. (English) Zbl 1419.65080

Summary: The MBO threshold dynamics method consists of two steps. The first step solves a pure initial value problem of the heat equation with the initial data being the indicator function of some bounded domain. In the second step, the new sharp interface is generated via thresholding either by some prescribed solution value or by volume preserving. We propose an efficient boundary integral scheme for simulating the threshold dynamics via the nonuniform fast Fourier transform (NUFFT). The first step is carried out by evaluating a boundary integral via the NUFFT, and the second step is performed applying a root-finding algorithm along the normal directions of a discrete set of points at the interface. Unlike most existing methods where volume discretization is needed for the whole computational domain, our scheme requires the discretization of physical space only in a small neighborhood of the interface and thus is meshfree. The algorithm is spectrally accurate in space for smooth interfaces and has \(O(N\log N)\) complexity, where \(N\) is the total number of discrete points near the interface when the time step \(\Delta t\) is not too small. The performance of the algorithm is illustrated via several numerical examples in both two and three dimensions.

MSC:

65M70 Spectral, collocation and related methods for initial value and initial-boundary value problems involving PDEs
35K05 Heat equation
82C24 Interface problems; diffusion-limited aggregation in time-dependent statistical mechanics

Software:

NUFFT; Matlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barles, G., Georgelin, C.: A simple proof of convergence for an approximation scheme for computing motions by mean curvature. SIAM J. Numer. Anal. 32(2), 484-500 (1995) · Zbl 0831.65138 · doi:10.1137/0732020
[2] Chambolle, A., Novaga, M.: Convergence of an algorithm for the anisotropic and crystalline mean curvature flow. SIAM J. Math. Anal. 37(6), 1978-1987 (2006) · Zbl 1116.35074 · doi:10.1137/050629641
[3] Deckelnick, K., Dziuk, G., Elliott, C.M.: Computation of geometric partial differential equations and mean curvature flow. Acta Numerica 14, 139-232 (2005) · Zbl 1113.65097 · doi:10.1017/S0962492904000224
[4] Dutt, A., Rokhlin, V.: Fast Fourier transforms for nonequispaced data. SIAM J. Sci. Comput. 14, 1368-1393 (1993) · Zbl 0791.65108 · doi:10.1137/0914081
[5] Dutt, A., Rokhlin, V.: Fast Fourier transforms for nonequispaced data. II. Appl. Comput. Harmon. Anal. 2, 85-100 (1995) · Zbl 0822.65130 · doi:10.1006/acha.1995.1007
[6] Dym, H., McKean, H.P.: Fourier Series and Integrals. Academic Press, Cambridge (1972) · Zbl 0242.42001
[7] Esedoglu, S., Otto, F.: Threshold dynamics for networks with arbitrary surface tensions. Comm. Pure Appl. Math. 68, 808-864 (2015) · Zbl 1334.82072 · doi:10.1002/cpa.21527
[8] Esedoglu, S., Ruuth, S., Tsai, R.: Threshold dynamics for high order geometric motions. Interf. Free Bound. 10(3), 263-282 (2008) · Zbl 1157.65330 · doi:10.4171/IFB/189
[9] Esodoglu, S., Smereka, P.: A variational formulation for a level set representation of multiphase flow and area preserving curvature flow. Comm. Math. Sci. 6(1), 125-148 (2008) · Zbl 1137.76067 · doi:10.4310/CMS.2008.v6.n1.a6
[10] Evans, L.C.: Convergence of an algorithm for mean curvature motion. Indiana Math. J. 42(2), 533-557 (1993) · Zbl 0802.65098 · doi:10.1512/iumj.1993.42.42024
[11] Evans, L.C.: Partial Differential Equations, 2nd edn. American Mathematical Society, Providence (2010) · Zbl 1194.35001
[12] Gao, M., Wang, X.: A gradient stable scheme for a phase field model for the moving contact line problem. J. Comput. Phys. 231, 1372-386 (2012) · Zbl 1408.76138 · doi:10.1016/j.jcp.2011.10.015
[13] Greengard, L., Lee, J.Y.: Accelerating the nonuniform fast Fourier transform. SIAM Rev. 46(3), 443-454 (2004) · Zbl 1064.65156 · doi:10.1137/S003614450343200X
[14] Greengard, L., Lin, P.: Spectral approximation of the free-space heat kernel. Appl. Comput. Harmon. Anal. 9(1), 83-97 (2000) · Zbl 0959.65111 · doi:10.1006/acha.2000.0310
[15] Greengard, L., Strain, J.: The fast Gauss transform. SIAM J. Sci. Statist. Comput. 12(1), 79-94 (1991) · Zbl 0721.65089 · doi:10.1137/0912004
[16] Greengard, L., Sun, X.: A new version of the fast Gauss transform. Proc. Int. Cong. Math. III, 575-584 (1998) · Zbl 0908.65126
[17] Ilmanen, T.: Lectures on Mean Curvature Flow and Related Equations, Lecture Notes. ICTP, Trieste (1995). http://www.math.ethz.ch/ ilmanen/papers/pub.html
[18] Ishii, K.: Optimal rate of convergence of the Bence-Merriman-Osher algorithm for motion by mean curvature. SIAM J. Math. Anal. 37(3), 841-866 (2005) · Zbl 1101.35006 · doi:10.1137/04061862X
[19] Kublik, C., Esedoglu, S., Fessler, J.A.: Algorithms for area preserving flows. SIAM J. Sci. Comput. 33(5), 2382-2401 (2011) · Zbl 1232.65012 · doi:10.1137/100815542
[20] Lee, J.Y., Greengard, L., Gimbutas, Z.: NUFFT Version 1.3.2 Software Release. http://www.cims.nyu.edu/cmcl/nufft/nufft.html (2009) · Zbl 0822.65130
[21] Leung, S., Zhao, H.: A grid based particle method for moving interface problems. J. Comput. Phys. 228(8), 2993-3024 (2009) · Zbl 1161.65013 · doi:10.1016/j.jcp.2009.01.005
[22] Li, J.R., Greengard, L.: On the numerical solution of the heat equation. I. Fast solvers in free space. J. Comput. Phys. 226(2), 1891-1901 (2007) · Zbl 1125.65095 · doi:10.1016/j.jcp.2007.06.021
[23] Mascarenhas, P.: Diffusion Generated Motion by Mean Curvature. Department of Mathematics. University of California, Los Angeles, Los Angeles (1992)
[24] Merriman, B., Bence, J.K., Osher, S.: Diffusion generated motion by mean curvature. UCLA CAM Report 92-18 (1992) · Zbl 1113.65097
[25] Müller, D.E.: A method for solving algebraic equations using an automatic computer. Math. Tables Aids Comput. 10, 208-215 (1956) · Zbl 0072.34002 · doi:10.2307/2001916
[26] Mullins, W.W.: Two-dimensional motion of idealized grain boundaries. J. Appl. Phys. 27(8), 900-904 (1956) · doi:10.1063/1.1722511
[27] Osher, S., Sethian, J.: Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. 79(1), 12-49 (1988) · Zbl 0659.65132 · doi:10.1016/0021-9991(88)90002-2
[28] Randol, B.: On the Fourier transform of the indicator function of a planar set. Trans. Amer. Math. Soc. 139, 271-278 (1969) · Zbl 0183.26904
[29] Ruuth, S.: An algorithm for generating motion by mean curvature. ICAOS’96 pp. 82-91 (1996) · Zbl 0854.65085
[30] Ruuth, S.J.: Efficient algorithms for diffusion-generated motion by mean curvature. Ph.D. thesis, University of British Columbia, Vancouver, Canada (1996) · Zbl 0946.65093
[31] Ruuth, S.J.: A diffusion-generated approach to multiphase motion. J. Comput. Phys. 145(1), 166-192 (1998) · Zbl 0929.76101 · doi:10.1006/jcph.1998.6028
[32] Ruuth, S.J.: Efficient algorithms for diffusion-generated motion by mean curvature. J. Comput. Phys. 144(2), 603-625 (1998) · Zbl 0946.65093 · doi:10.1006/jcph.1998.6025
[33] Ruuth, S.J., Wetton, B.T.: A simple scheme for volume-preserving motion by mean curvature. J. Sci. Comput. 19(1-3), 373-384 (2003) · Zbl 1035.65097 · doi:10.1023/A:1025368328471
[34] Stenger, F.: Numerical methods based on Whittaker cardinal, or sinc functions. SIAM Rev. 23(2), 165-224 (1981) · Zbl 0461.65007 · doi:10.1137/1023037
[35] Svadlenka, K., Ginder, E., Omata, S.: A variational method for multiphase volume-preserving interface motions. J. Comput. Appl. Math. 257, 157-179 (2014) · Zbl 1294.53064 · doi:10.1016/j.cam.2013.08.027
[36] Trefethen, L.N.: Spectral Methods in MATLAB. SIAM, Philadelphia (2000) · Zbl 0953.68643 · doi:10.1137/1.9780898719598
[37] Womble, D.E.: A front-tracking method for multiphase free boundary problems. SIAM J. Numer. Anal. 26(2), 380-396 (1989) · Zbl 0681.65090 · doi:10.1137/0726021
[38] Xu, X., Wang, D., Wang, X.P.: An efficient threshold dynamics method for wetting on rough surfaces. J. Comput. Phys. 330, 510-528 (2017) · Zbl 1378.76087 · doi:10.1016/j.jcp.2016.11.008
[39] Yue, P., Feng, J., Liu, C., Shen, J.: A diffuse-interface method for simulating two-phase flows of complex fluids. J. Fluid Mech. 515, 293-317 (2004) · Zbl 1130.76437 · doi:10.1017/S0022112004000370
[40] Zhao, H., Chan, T., Merriman, B., Osher, S.J.: A variational level set approach to multiphase motion. J. Comput. Phys. 127(1), 179-195 (1996) · Zbl 0860.65050 · doi:10.1006/jcph.1996.0167
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.