A diffusion generated method for orthogonal matrix-valued fields
HTML articles powered by AMS MathViewer
- by Braxton Osting and Dong Wang HTML | PDF
- Math. Comp. 89 (2020), 515-550 Request permission
Abstract:
We consider the problem of finding stationary points of the Dirichlet energy for orthogonal matrix-valued fields. Following the Ginzburg-Landau approach, this energy is relaxed by penalizing the matrix-valued field when it does not take orthogonal matrix values. A generalization of the Merriman-Bence-Osher (MBO) diffusion generated method is introduced that effectively finds local minimizers of this energy by iterating two steps until convergence. In the first step, as in the original method, the current matrix-valued field is evolved by the diffusion equation. In the second step, the field is pointwise reassigned to the closest orthogonal matrix, which can be computed via the singular value decomposition. We extend the Lyapunov function of Esedoglu and Otto to show that the method is non-increasing on iterates and hence, unconditionally stable. We also prove that spatially discretized iterates converge to a stationary solution in a finite number of iterations. The algorithm is implemented using the closest point method and non-uniform fast Fourier transform. We conclude with several numerical experiments on flat tori and closed surfaces, which, unsurprisingly, exhibit classical behavior from the Allen-Cahn and complex Ginzburg-Landau equations, but also new phenomena.References
- Thomas Batard and Marcelo Bertalmío, On covariant derivatives and their applications to image regularization, SIAM J. Imaging Sci. 7 (2014), no. 4, 2393–2422. MR 3280098, DOI 10.1137/140954039
- Eric Bonnetier, Elie Bretin, and Antonin Chambolle, Consistency result for a non monotone scheme for anisotropic mean curvature flow, Interfaces Free Bound. 14 (2012), no. 1, 1–35. MR 2929124, DOI 10.4171/ifb/272
- Fabrice Bethuel, Haïm Brezis, and Frédéric Hélein, Ginzburg-Landau vortices, Progress in Nonlinear Differential Equations and their Applications, vol. 13, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1269538, DOI 10.1007/978-1-4612-0287-5
- Miroslav Bačák, Ronny Bergmann, Gabriele Steidl, and Andreas Weinmann, A second order nonsmooth variational model for restoring manifold-valued images, SIAM J. Sci. Comput. 38 (2016), no. 1, A567–A597. MR 3463052, DOI 10.1137/15M101988X
- Marcelo Bertalmío, Li-Tien Cheng, Stanley Osher, and Guillermo Sapiro, Variational problems and partial differential equations on implicit surfaces, J. Comput. Phys. 174 (2001), no. 2, 759–780. MR 1868103, DOI 10.1006/jcph.2001.6937
- Guy Barles and Christine Georgelin, A simple proof of convergence for an approximation scheme for computing motions by mean curvature, SIAM J. Numer. Anal. 32 (1995), no. 2, 484–500. MR 1324298, DOI 10.1137/0732020
- Marcelo Bertalmío, Facundo Mémoli, Li-Tien Cheng, Guillermo Sapiro, and Stanley Osher, Variational problems and partial differential equations on implicit surfaces: bye bye triangulated surfaces?, Geometric level set methods in imaging, vision, and graphics, Springer, New York, 2003, pp. 381–397. MR 2070081, DOI 10.1007/0-387-21810-6_{2}0
- Benjamin Berkels, Andreas Rätz, Martin Rumpf, and Axel Voigt, Extracting grain boundaries and macroscopic deformations from images on atomic scale, J. Sci. Comput. 35 (2008), no. 1, 1–23. MR 2411212, DOI 10.1007/s10915-007-9157-5
- Antonin Chambolle and Matteo Novaga, Convergence of an algorithm for the anisotropic and crystalline mean curvature flow, SIAM J. Math. Anal. 37 (2006), no. 6, 1978–1987. MR 2213402, DOI 10.1137/050629641
- A. Dutt and V. Rokhlin, Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Comput. 14 (1993), no. 6, 1368–1393. MR 1241591, DOI 10.1137/0914081
- Matt Elsey and Selim Esedoḡlu, Threshold dynamics for anisotropic surface energies, Math. Comp. 87 (2018), no. 312, 1721–1756. MR 3787390, DOI 10.1090/mcom/3268
- Selim Esedoḡlu and Felix Otto, Threshold dynamics for networks with arbitrary surface tensions, Comm. Pure Appl. Math. 68 (2015), no. 5, 808–864. MR 3333842, DOI 10.1002/cpa.21527
- Selim Esedoḡlu, Steven J. Ruuth, and Richard Tsai, Threshold dynamics for high order geometric motions, Interfaces Free Bound. 10 (2008), no. 3, 263–282. MR 2453132, DOI 10.4171/IFB/189
- Selim Esedoḡlu and Yen-Hsi Richard Tsai, Threshold dynamics for the piecewise constant Mumford-Shah functional, J. Comput. Phys. 211 (2006), no. 1, 367–384. MR 2168882, DOI 10.1016/j.jcp.2005.05.027
- Lawrence C. Evans, Convergence of an algorithm for mean curvature motion, Indiana Univ. Math. J. 42 (1993), no. 2, 533–557. MR 1237058, DOI 10.1512/iumj.1993.42.42024
- Matt Elsey and Benedikt Wirth, A simple and efficient scheme for phase field crystal simulation, ESAIM Math. Model. Numer. Anal. 47 (2013), no. 5, 1413–1432 (English, with English and French summaries). MR 3100769, DOI 10.1051/m2an/2013074
- Matt Elsey and Benedikt Wirth, Fast automated detection of crystal distortion and crystal defects in polycrystal images, Multiscale Model. Simul. 12 (2014), no. 1, 1–24. MR 3151380, DOI 10.1137/130916515
- Michael S. Floater and Kai Hormann, Surface parameterization: a tutorial and survey, Advances in multiresolution for geometric modelling, Math. Vis., Springer, Berlin, 2005, pp. 157–186. MR 2112350, DOI 10.1007/3-540-26808-1_{9}
- P. Thomas Fletcher and Sarang Joshi, Riemannian geometry for the statistical analysis of diffusion tensor data, Signal Processing 87 (2007), no. 2, 250–262.
- Leslie Greengard and June-Yub Lee, Accelerating the nonuniform fast Fourier transform, SIAM Rev. 46 (2004), no. 3, 443–454. MR 2115056, DOI 10.1137/S003614450343200X
- John B. Greer, An improvement of a recent Eulerian method for solving PDEs on general geometries, J. Sci. Comput. 29 (2006), no. 3, 321–352. MR 2272322, DOI 10.1007/s10915-005-9012-5
- Hitoshi Ishii, Gabriel E. Pires, and Panagiotis E. Souganidis, Threshold dynamics type approximation schemes for propagating fronts, J. Math. Soc. Japan 51 (1999), no. 2, 267–308. MR 1674750, DOI 10.2969/jmsj/05120267
- Katsuyuki Ishii, Optimal rate of convergence of the Bence-Merriman-Osher algorithm for motion by mean curvature, SIAM J. Math. Anal. 37 (2005), no. 3, 841–866. MR 2191779, DOI 10.1137/04061862X
- Matt Jacobs, Ekaterina Merkurjev, and Selim Esedoḡlu, Auction dynamics: a volume constrained MBO scheme, J. Comput. Phys. 354 (2018), 288–310. MR 3738108, DOI 10.1016/j.jcp.2017.10.036
- Shidong Jiang, Dong Wang, and Xiao-Ping Wang, An efficient boundary integral scheme for the MBO threshold dynamics method via the NUFFT, J. Sci. Comput. 74 (2018), no. 1, 474–490. MR 3742888, DOI 10.1007/s10915-017-0448-1
- Gershon Kresin and Vladimir Maz’ya, Maximum principles and sharp constants for solutions of elliptic and parabolic systems, Mathematical Surveys and Monographs, vol. 183, American Mathematical Society, Providence, RI, 2012. MR 2962313, DOI 10.1090/surv/183
- June-Yub Lee and Leslie Greengard, The type 3 nonuniform FFT and its applications, J. Comput. Phys. 206 (2005), no. 1, 1–5. MR 2135833, DOI 10.1016/j.jcp.2004.12.004
- J. Y. Lee, L. Greengard, and Z. Gimbutas, NUFFT Version 1.3.2 Software Release, http://www.cims.nyu.edu/cmcl/nufft/nufft.html, 2009.
- Tim Laux and Felix Otto, Convergence of the thresholding scheme for multi-phase mean-curvature flow, Calc. Var. Partial Differential Equations 55 (2016), no. 5, Art. 129, 74. MR 3556529, DOI 10.1007/s00526-016-1053-0
- Fanghua Lin, Xing-Bin Pan, and Changyou Wang, Phase transition for potentials of high-dimensional wells, Comm. Pure Appl. Math. 65 (2012), no. 6, 833–888. MR 2903801, DOI 10.1002/cpa.21386
- Adrian S. Lewis and Hristo S. Sendov, Nonsmooth analysis of singular values. I. Theory, Set-Valued Anal. 13 (2005), no. 3, 213–241. MR 2162512, DOI 10.1007/s11228-004-7197-7
- Tim Laux and Drew Swartz, Convergence of thresholding schemes incorporating bulk effects, Interfaces Free Bound. 19 (2017), no. 2, 273–304. MR 3667702, DOI 10.4171/IFB/383
- Tim Laux and Nung Kwan Yip, Analysis of diffusion generated motion for mean curvature flow in codimension two: a gradient-flow approach, Arch. Ration. Mech. Anal. 232 (2019), no. 2, 1113–1163. MR 3925538, DOI 10.1007/s00205-018-01340-x
- P. Mascarenhas, Diffusion generated motion by mean curvature, UCLA CAM Report 92-33, 1992.
- B. Merriman, J. K. Bence, and S. Osher, Diffusion generated motion by mean curvature, UCLA CAM Report 92-18, 1992.
- B. Merriman, J.K. Bence, and S. Osher, Diffusion generated motion by mean curvature, AMS Selected Letters, Crystal Grower’s Workshop (1993), 73–83.
- Barry Merriman, James K. Bence, and Stanley J. Osher, Motion of multiple functions: a level set approach, J. Comput. Phys. 112 (1994), no. 2, 334–363. MR 1277282, DOI 10.1006/jcph.1994.1105
- Colin B. Macdonald, Jeremy Brandman, and Steven J. Ruuth, Solving eigenvalue problems on curved surfaces using the closest point method, J. Comput. Phys. 230 (2011), no. 22, 7944–7956. MR 2835404, DOI 10.1016/j.jcp.2011.06.021
- Ekaterina Merkurjev, Tijana Kostić, and Andrea L. Bertozzi, An MBO scheme on graphs for classification and image processing, SIAM J. Imaging Sci. 6 (2013), no. 4, 1903–1930. MR 3115457, DOI 10.1137/120886935
- Steven J. Ruuth and Barry Merriman, Convolution-generated motion and generalized Huygens’ principles for interface motion, SIAM J. Appl. Math. 60 (2000), no. 3, 868–890. MR 1740854, DOI 10.1137/S003613999833397X
- Barry Merriman and Steven J. Ruuth, Diffusion generated motion of curves on surfaces, J. Comput. Phys. 225 (2007), no. 2, 2267–2282. MR 2349702, DOI 10.1016/j.jcp.2007.03.034
- Colin B. Macdonald and Steven J. Ruuth, Level set equations on surfaces via the closest point method, J. Sci. Comput. 35 (2008), no. 2-3, 219–240. MR 2429939, DOI 10.1007/s10915-008-9196-6
- Colin B. Macdonald and Steven J. Ruuth, The implicit closest point method for the numerical solution of partial differential equations on surfaces, SIAM J. Sci. Comput. 31 (2009/10), no. 6, 4330–4350. MR 2594984, DOI 10.1137/080740003
- Braxton Osting and Dong Wang, Diffusion generated methods for denoising target-valued images, preprint, arXiv:1806.07225, (2018).
- Steven J. Ruuth and Barry Merriman, Convolution-thresholding methods for interface motion, J. Comput. Phys. 169 (2001), no. 2, 678–707. MR 1836529, DOI 10.1006/jcph.2000.6580
- Steven J. Ruuth and Barry Merriman, A simple embedding method for solving partial differential equations on surfaces, J. Comput. Phys. 227 (2008), no. 3, 1943–1961. MR 2450979, DOI 10.1016/j.jcp.2007.10.009
- S. J. Ruuth, B. Merriman, J. Xin, and S. Osher, Diffusion-generated motion by mean curvature for filaments, J. Nonlinear Sci. 11 (2001), no. 6, 473–493. MR 1871280, DOI 10.1007/s00332-001-0404-x
- Jacob Rubinstein, Peter Sternberg, and Joseph B. Keller, Reaction-diffusion processes and evolution to harmonic maps, SIAM J. Appl. Math. 49 (1989), no. 6, 1722–1733. MR 1025956, DOI 10.1137/0149104
- Guy Rosman, Xue-Cheng Tai, Ron Kimmel, and Alfred M. Bruckstein, Augmented-Lagrangian regularization of matrix-valued maps, Methods Appl. Anal. 21 (2014), no. 1, 105–121. MR 3257962, DOI 10.4310/MAA.2014.v21.n1.a5
- Steven J. Ruuth, A diffusion-generated approach to multiphase motion, J. Comput. Phys. 145 (1998), no. 1, 166–192. MR 1640166, DOI 10.1006/jcph.1998.6028
- Steven J. Ruuth, Efficient algorithms for diffusion-generated motion by mean curvature, J. Comput. Phys. 144 (1998), no. 2, 603–625. MR 1638032, DOI 10.1006/jcph.1998.6025
- Steven J. Ruuth and Brian T. R. Wetton, A simple scheme for volume-preserving motion by mean curvature, J. Sci. Comput. 19 (2003), no. 1-3, 373–384. Special issue in honor of the sixtieth birthday of Stanley Osher. MR 2028850, DOI 10.1023/A:1025368328471
- J. Saunderson, P. A. Parrilo, and A. S. Willsky, Semidefinite descriptions of the convex hull of rotation matrices, SIAM J. Optim. 25 (2015), no. 3, 1314–1343. MR 3369076, DOI 10.1137/14096339X
- Drew Swartz and Nung Kwan Yip, Convergence of diffusion generated motion to motion by mean curvature, Comm. Partial Differential Equations 42 (2017), no. 10, 1598–1643. MR 3764921, DOI 10.1080/03605302.2017.1383418
- Li (Luke) Tian, Colin B. Macdonald, and Steven J. Ruuth, Segmentation on surfaces with the Closest Point Method, Proc. ICIP09, 16th IEEE International Conference on Image Processing (Cairo, Egypt), 2009, pp. 3009–3012.
- Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen, Directional field synthesis, design, and processing, Computer Graphics Forum 35 (2016), no. 2, 545–572.
- Yves van Gennip, Nestor Guillen, Braxton Osting, and Andrea L. Bertozzi, Mean curvature, threshold dynamics, and phase field theory on finite graphs, Milan J. Math. 82 (2014), no. 1, 3–65. MR 3207626, DOI 10.1007/s00032-014-0216-8
- Ryan Viertel and Braxton Osting, An approach to quad meshing based on harmonic cross-valued maps and the Ginzburg-Landau theory, SIAM J. Sci. Comput. 41 (2019), no. 1, A452–A479. MR 3908824, DOI 10.1137/17M1142703
- Dong Wang, Haohan Li, Xiaoyu Wei, and Xiao-Ping Wang, An efficient iterative thresholding method for image segmentation, J. Comput. Phys. 350 (2017), 657–667. MR 3707176, DOI 10.1016/j.jcp.2017.08.020
- Dong Wang and Braxton Osting, A diffusion generated method for computing Dirichlet partitions, J. Comput. Appl. Math. 351 (2019), 302–316. MR 3885732, DOI 10.1016/j.cam.2018.11.015
- Dong Wang, Braxton Osting, and Xiao-Ping Wang, Interface dynamics for an allen-cahn-type equation governing a matrix-valued field, to appear in Multiscale Model. Simul. arXiv:1906.05985, 2019.
- Dong Wang, Xiao-Ping Wang, and Xianmin Xu, An improved threshold dynamics method for wetting dynamics, J. Comput. Phys. 392 (2019), 291–310. MR 3948721, DOI 10.1016/j.jcp.2019.04.037
- Xianmin Xu, Dong Wang, and Xiao-Ping Wang, An efficient threshold dynamics method for wetting on rough surfaces, J. Comput. Phys. 330 (2017), 510–528. MR 3581477, DOI 10.1016/j.jcp.2016.11.008
Additional Information
- Braxton Osting
- Affiliation: Department of Mathematics, University of Utah, Salt Lake City, Utah 84112
- MR Author ID: 876194
- ORCID: 0000-0002-4123-9048
- Email: osting@math.utah.edu
- Dong Wang
- Affiliation: Department of Mathematics, University of Utah, Salt Lake City, Utah 84112
- Email: dwang@math.utah.edu
- Received by editor(s): December 13, 2017
- Received by editor(s) in revised form: August 1, 2018, March 27, 2019, and May 17, 2019
- Published electronically: September 24, 2019
- Additional Notes: The first author was partially supported by NSF DMS 16-19755 and 17-52202.
- © Copyright 2019 American Mathematical Society
- Journal: Math. Comp. 89 (2020), 515-550
- MSC (2010): Primary 35K93, 35K05, 65M12
- DOI: https://doi.org/10.1090/mcom/3473
- MathSciNet review: 4044441