A diffusion generated method for orthogonal matrix-valued fields. (English) Zbl 1435.65144
Matrix-valued fields occur in many setting like in inverse problems of image analysis, e.g. diffusion tensor MRI, in the study of polycrystals, in geometry processing and computer graphics. In this paper, the authors develop an algorithm for finding stationary points of the Dirichlet energy for orthogonal matrix-valued fields.
The energy minimization problem is given as \[ \min_{A \in H^1(\Omega,O_n)} \ E(A), \text{ where }E(A) := \frac{1}{2} \int_\Omega \| \nabla A \|_F^2 \ dx,\tag{GL} \] where \(\Omega\) to be a flat torus, or more generally, a closed manifold. Let \(O_n \subset M_n = \mathbb R^{n\times n} \) be the group of orthogonal matrices. Let \(H^1(\Omega,M_n)\) and \(H^1(\Omega,O_n) \subset H^1(\Omega,M_n)\) denote the matrix-valued Sobolev spaces. Here, \(\| \cdot \|_F\) denotes the Frobenius norm, induced by the Frobenius inner product, \(\langle A, B \rangle_F = \sum_{i,j} A_{i,j} B_{i,j}\). The gradient of \(A\) is understood in the sense that \(A\) takes values in the Euclidean embedding space, \(M_n\).
The stationary points of the energy in (GL) and the related gradient flow can be approximated following Ginzburg-Landau theory as \[ \min_{A \in H^1(\Omega,M_n)} \ E_{2,\varepsilon} (A),\text{ where }E_{2,\varepsilon}(A) := \int_\Omega \frac{1}{2} \| \nabla A \|_F^2 + \frac{1}{4\varepsilon^2} \| A^t A - I_n \|_F^2 \ dx.\tag{GL2} \] In (GL) and (GL2), the first term can be interpreted as a smoothing term while the second term penalizes when the matrix-valued field is not an orthogonal matrix. The minimum in (GL) and (GL2) are attained by any constant orthogonal matrix-valued function. In order to compute the non-trivial stationary solutions, a diffusion generated method is developed for finding local minima as generalization of the Merriman-Bence-Osher (MBO) algorithm [B. Merriman et al., J. Comput. Phys. 112, No. 2, 343–363 (1994; Zbl 0805.65090)]
Several numerical experiments on flat tori and closed surfaces, on the sphere, “peanut surface”, constrained volume exhibit classical behavior from the Allen-Cahn and complex Ginzburg Landau equations, but also new phenomena.
The energy minimization problem is given as \[ \min_{A \in H^1(\Omega,O_n)} \ E(A), \text{ where }E(A) := \frac{1}{2} \int_\Omega \| \nabla A \|_F^2 \ dx,\tag{GL} \] where \(\Omega\) to be a flat torus, or more generally, a closed manifold. Let \(O_n \subset M_n = \mathbb R^{n\times n} \) be the group of orthogonal matrices. Let \(H^1(\Omega,M_n)\) and \(H^1(\Omega,O_n) \subset H^1(\Omega,M_n)\) denote the matrix-valued Sobolev spaces. Here, \(\| \cdot \|_F\) denotes the Frobenius norm, induced by the Frobenius inner product, \(\langle A, B \rangle_F = \sum_{i,j} A_{i,j} B_{i,j}\). The gradient of \(A\) is understood in the sense that \(A\) takes values in the Euclidean embedding space, \(M_n\).
The stationary points of the energy in (GL) and the related gradient flow can be approximated following Ginzburg-Landau theory as \[ \min_{A \in H^1(\Omega,M_n)} \ E_{2,\varepsilon} (A),\text{ where }E_{2,\varepsilon}(A) := \int_\Omega \frac{1}{2} \| \nabla A \|_F^2 + \frac{1}{4\varepsilon^2} \| A^t A - I_n \|_F^2 \ dx.\tag{GL2} \] In (GL) and (GL2), the first term can be interpreted as a smoothing term while the second term penalizes when the matrix-valued field is not an orthogonal matrix. The minimum in (GL) and (GL2) are attained by any constant orthogonal matrix-valued function. In order to compute the non-trivial stationary solutions, a diffusion generated method is developed for finding local minima as generalization of the Merriman-Bence-Osher (MBO) algorithm [B. Merriman et al., J. Comput. Phys. 112, No. 2, 343–363 (1994; Zbl 0805.65090)]
Several numerical experiments on flat tori and closed surfaces, on the sphere, “peanut surface”, constrained volume exhibit classical behavior from the Allen-Cahn and complex Ginzburg Landau equations, but also new phenomena.
Reviewer: Bülent Karasözen (Ankara)
MSC:
| 65M12 | Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs |
| 35K93 | Quasilinear parabolic equations with mean curvature operator |
| 35K05 | Heat equation |
| 35Q56 | Ginzburg-Landau equations |
| 35R09 | Integro-partial differential equations |
| 35C20 | Asymptotic expansions of solutions to PDEs |
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
| 65K10 | Numerical optimization and variational techniques |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
Keywords:
Allen-Cahn equation; Ginzburg-Landau equation; Merriman-Bence-Osher (MBO) diffusion generated method; constrained harmonic map; orthogonal matrix-valued fieldCitations:
Zbl 0805.65090Software:
NUFFTReferences:
| [1] | Batard, Thomas; Bertalm\'{\i}o, Marcelo, On covariant derivatives and their applications to image regularization, SIAM J. Imaging Sci., 7, 4, 2393-2422 (2014) · Zbl 1361.94007 · doi:10.1137/140954039 |
| [2] | Bonnetier, Eric; Bretin, Elie; Chambolle, Antonin, Consistency result for a non monotone scheme for anisotropic mean curvature flow, Interfaces Free Bound., 14, 1, 1-35 (2012) · Zbl 1254.35128 · doi:10.4171/ifb/272 |
| [3] | Bethuel, Fabrice; Brezis, Ha\`“{\i}m; H\'”{e}lein, Fr\'{e}d\'{e}ric, Ginzburg-Landau Vortices, Progress in Nonlinear Differential Equations and their Applications 13, xxviii+159 pp. (1994), Birkh\"{a}user Boston, Inc., Boston, MA · Zbl 0802.35142 · doi:10.1007/978-1-4612-0287-5 |
| [4] | Ba\v{c}\'{a}k, Miroslav; Bergmann, Ronny; Steidl, Gabriele; Weinmann, Andreas, A second order nonsmooth variational model for restoring manifold-valued images, SIAM J. Sci. Comput., 38, 1, A567-A597 (2016) · Zbl 1382.94007 · doi:10.1137/15M101988X |
| [5] | Bertalm\'{\i}o, Marcelo; Cheng, Li-Tien; Osher, Stanley; Sapiro, Guillermo, Variational problems and partial differential equations on implicit surfaces, J. Comput. Phys., 174, 2, 759-780 (2001) · Zbl 0991.65055 · doi:10.1006/jcph.2001.6937 |
| [6] | Barles, Guy; Georgelin, Christine, 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 |
| [7] | Bertalm\'{\i}o, Marcelo; M\'{e}moli, Facundo; Cheng, Li-Tien; Sapiro, Guillermo; Osher, Stanley, Variational problems and partial differential equations on implicit surfaces: bye bye triangulated surfaces?. Geometric level set methods in imaging, vision, and graphics, 381-397 (2003), Springer, New York · doi:10.1007/0-387-21810-6\_20 |
| [8] | Berkels, Benjamin; R\"{a}tz, Andreas; Rumpf, Martin; Voigt, Axel, Extracting grain boundaries and macroscopic deformations from images on atomic scale, J. Sci. Comput., 35, 1, 1-23 (2008) · Zbl 1203.65039 · doi:10.1007/s10915-007-9157-5 |
| [9] | Chambolle, Antonin; Novaga, Matteo, 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 |
| [10] | Dutt, A.; Rokhlin, V., Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Comput., 14, 6, 1368-1393 (1993) · Zbl 0791.65108 · doi:10.1137/0914081 |
| [11] | Elsey, Matt; Esedo\={g}lu, Selim, Threshold dynamics for anisotropic surface energies, Math. Comp., 87, 312, 1721-1756 (2018) · Zbl 1397.65156 · doi:10.1090/mcom/3268 |
| [12] | Esedo\={g}lu, Selim; Otto, Felix, Threshold dynamics for networks with arbitrary surface tensions, Comm. Pure Appl. Math., 68, 5, 808-864 (2015) · Zbl 1334.82072 · doi:10.1002/cpa.21527 |
| [13] | Esedo\={g}lu, Selim; Ruuth, Steven J.; Tsai, Richard, Threshold dynamics for high order geometric motions, Interfaces Free Bound., 10, 3, 263-282 (2008) · Zbl 1157.65330 · doi:10.4171/IFB/189 |
| [14] | Esedo\={g}lu, Selim; Tsai, Yen-Hsi Richard, Threshold dynamics for the piecewise constant Mumford-Shah functional, J. Comput. Phys., 211, 1, 367-384 (2006) · Zbl 1086.65522 · doi:10.1016/j.jcp.2005.05.027 |
| [15] | Evans, Lawrence C., Convergence of an algorithm for mean curvature motion, Indiana Univ. Math. J., 42, 2, 533-557 (1993) · Zbl 0802.65098 · doi:10.1512/iumj.1993.42.42024 |
| [16] | Elsey, Matt; Wirth, Benedikt, A simple and efficient scheme for phase field crystal simulation, ESAIM Math. Model. Numer. Anal., 47, 5, 1413-1432 (2013) · Zbl 1286.74118 · doi:10.1051/m2an/2013074 |
| [17] | Elsey, Matt; Wirth, Benedikt, Fast automated detection of crystal distortion and crystal defects in polycrystal images, Multiscale Model. Simul., 12, 1, 1-24 (2014) · Zbl 1328.68270 · doi:10.1137/130916515 |
| [18] | Floater, Michael S.; Hormann, Kai, Surface parameterization: a tutorial and survey. Advances in multiresolution for geometric modelling, Math. Vis., 157-186 (2005), Springer, Berlin · Zbl 1065.65030 · doi:10.1007/3-540-26808-1\_9 |
| [19] | P. Thomas Fletcher and Sarang Joshi, Riemannian geometry for the statistical analysis of diffusion tensor data, Signal Processing 87 (2007), no. 2, 250-262. · Zbl 1186.94126 |
| [20] | Greengard, Leslie; Lee, June-Yub, Accelerating the nonuniform fast Fourier transform, SIAM Rev., 46, 3, 443-454 (2004) · Zbl 1064.65156 · doi:10.1137/S003614450343200X |
| [21] | Greer, John B., An improvement of a recent Eulerian method for solving PDEs on general geometries, J. Sci. Comput., 29, 3, 321-352 (2006) · Zbl 1122.65073 · doi:10.1007/s10915-005-9012-5 |
| [22] | Ishii, Hitoshi; Pires, Gabriel E.; Souganidis, Panagiotis E., Threshold dynamics type approximation schemes for propagating fronts, J. Math. Soc. Japan, 51, 2, 267-308 (1999) · Zbl 0935.53006 · doi:10.2969/jmsj/05120267 |
| [23] | Ishii, Katsuyuki, 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 |
| [24] | Jacobs, Matt; Merkurjev, Ekaterina; Esedo\={g}lu, Selim, Auction dynamics: a volume constrained MBO scheme, J. Comput. Phys., 354, 288-310 (2018) · Zbl 1380.52018 · doi:10.1016/j.jcp.2017.10.036 |
| [25] | Jiang, Shidong; Wang, Dong; Wang, Xiao-Ping, An efficient boundary integral scheme for the MBO threshold dynamics method via the NUFFT, J. Sci. Comput., 74, 1, 474-490 (2018) · Zbl 1419.65080 · doi:10.1007/s10915-017-0448-1 |
| [26] | Kresin, Gershon; Maz’ya, Vladimir, Maximum Principles and Sharp Constants for Solutions of Elliptic and Parabolic Systems, Mathematical Surveys and Monographs 183, viii+317 pp. (2012), American Mathematical Society, Providence, RI · Zbl 1255.35001 · doi:10.1090/surv/183 |
| [27] | Lee, June-Yub; Greengard, Leslie, The type 3 nonuniform FFT and its applications, J. Comput. Phys., 206, 1, 1-5 (2005) · Zbl 1072.65170 · doi:10.1016/j.jcp.2004.12.004 |
| [28] | 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. |
| [29] | Laux, Tim; Otto, Felix, Convergence of the thresholding scheme for multi-phase mean-curvature flow, Calc. Var. Partial Differential Equations, 55, 5, Art. 129, 74 pp. (2016) · Zbl 1388.35121 · doi:10.1007/s00526-016-1053-0 |
| [30] | Lin, Fanghua; Pan, Xing-Bin; Wang, Changyou, Phase transition for potentials of high-dimensional wells, Comm. Pure Appl. Math., 65, 6, 833-888 (2012) · Zbl 1248.49059 · doi:10.1002/cpa.21386 |
| [31] | Lewis, Adrian S.; Sendov, Hristo S., Nonsmooth analysis of singular values. I. Theory, Set-Valued Anal., 13, 3, 213-241 (2005) · Zbl 1129.49025 · doi:10.1007/s11228-004-7197-7 |
| [32] | Laux, Tim; Swartz, Drew, Convergence of thresholding schemes incorporating bulk effects, Interfaces Free Bound., 19, 2, 273-304 (2017) · Zbl 1376.82004 · doi:10.4171/IFB/383 |
| [33] | Laux, Tim; Yip, Nung Kwan, Analysis of diffusion generated motion for mean curvature flow in codimension two: a gradient-flow approach, Arch. Ration. Mech. Anal., 232, 2, 1113-1163 (2019) · Zbl 1411.53050 · doi:10.1007/s00205-018-01340-x |
| [34] | P. Mascarenhas, Diffusion generated motion by mean curvature, UCLA CAM Report 92-33, 1992. |
| [35] | B. Merriman, J. K. Bence, and S. Osher, Diffusion generated motion by mean curvature, UCLA CAM Report 92-18, 1992. |
| [36] | B. Merriman, J.K. Bence, and S. Osher, Diffusion generated motion by mean curvature, AMS Selected Letters, Crystal Grower’s Workshop (1993), 73-83. |
| [37] | Merriman, Barry; Bence, James K.; Osher, Stanley J., Motion of multiple functions: a level set approach, J. Comput. Phys., 112, 2, 334-363 (1994) · Zbl 0805.65090 · doi:10.1006/jcph.1994.1105 |
| [38] | Macdonald, Colin B.; Brandman, Jeremy; Ruuth, Steven J., Solving eigenvalue problems on curved surfaces using the closest point method, J. Comput. Phys., 230, 22, 7944-7956 (2011) · Zbl 1231.65205 · doi:10.1016/j.jcp.2011.06.021 |
| [39] | Merkurjev, Ekaterina; Kosti\'{c}, Tijana; Bertozzi, Andrea L., An MBO scheme on graphs for classification and image processing, SIAM J. Imaging Sci., 6, 4, 1903-1930 (2013) · Zbl 1279.68335 · doi:10.1137/120886935 |
| [40] | Ruuth, Steven J.; Merriman, Barry, Convolution-generated motion and generalized Huygens’ principles for interface motion, SIAM J. Appl. Math., 60, 3, 868-890 (2000) · Zbl 0958.65021 · doi:10.1137/S003613999833397X |
| [41] | Merriman, Barry; Ruuth, Steven J., Diffusion generated motion of curves on surfaces, J. Comput. Phys., 225, 2, 2267-2282 (2007) · Zbl 1123.65011 · doi:10.1016/j.jcp.2007.03.034 |
| [42] | Macdonald, Colin B.; Ruuth, Steven J., Level set equations on surfaces via the closest point method, J. Sci. Comput., 35, 2-3, 219-240 (2008) · Zbl 1203.65143 · doi:10.1007/s10915-008-9196-6 |
| [43] | Macdonald, Colin B.; Ruuth, Steven J., The implicit closest point method for the numerical solution of partial differential equations on surfaces, SIAM J. Sci. Comput., 31, 6, 4330-4350 (2009/10) · Zbl 1205.65238 · doi:10.1137/080740003 |
| [44] | Braxton Osting and Dong Wang, Diffusion generated methods for denoising target-valued images, preprint, arXiv:1806.07225, (2018). · Zbl 1437.65126 |
| [45] | Ruuth, Steven J.; Merriman, Barry, Convolution-thresholding methods for interface motion, J. Comput. Phys., 169, 2, 678-707 (2001) · Zbl 0988.65094 · doi:10.1006/jcph.2000.6580 |
| [46] | Ruuth, Steven J.; Merriman, Barry, A simple embedding method for solving partial differential equations on surfaces, J. Comput. Phys., 227, 3, 1943-1961 (2008) · Zbl 1134.65058 · doi:10.1016/j.jcp.2007.10.009 |
| [47] | Ruuth, S. J.; Merriman, B.; Xin, J.; Osher, S., Diffusion-generated motion by mean curvature for filaments, J. Nonlinear Sci., 11, 6, 473-493 (2001) · Zbl 1037.35033 · doi:10.1007/s00332-001-0404-x |
| [48] | Rubinstein, Jacob; Sternberg, Peter; Keller, Joseph B., Reaction-diffusion processes and evolution to harmonic maps, SIAM J. Appl. Math., 49, 6, 1722-1733 (1989) · Zbl 0702.35128 · doi:10.1137/0149104 |
| [49] | Rosman, Guy; Tai, Xue-Cheng; Kimmel, Ron; Bruckstein, Alfred M., Augmented-Lagrangian regularization of matrix-valued maps, Methods Appl. Anal., 21, 1, 105-121 (2014) · Zbl 1292.65072 · doi:10.4310/MAA.2014.v21.n1.a5 |
| [50] | Ruuth, Steven 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 |
| [51] | Ruuth, Steven 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 |
| [52] | Ruuth, Steven J.; Wetton, Brian T. R., 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 |
| [53] | Saunderson, J.; Parrilo, P. A.; Willsky, A. S., Semidefinite descriptions of the convex hull of rotation matrices, SIAM J. Optim., 25, 3, 1314-1343 (2015) · Zbl 1317.90231 · doi:10.1137/14096339X |
| [54] | Swartz, Drew; Yip, Nung Kwan, Convergence of diffusion generated motion to motion by mean curvature, Comm. Partial Differential Equations, 42, 10, 1598-1643 (2017) · Zbl 1387.35389 · doi:10.1080/03605302.2017.1383418 |
| [55] | 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. |
| [56] | 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. |
| [57] | van Gennip, Yves; Guillen, Nestor; Osting, Braxton; Bertozzi, Andrea L., Mean curvature, threshold dynamics, and phase field theory on finite graphs, Milan J. Math., 82, 1, 3-65 (2014) · Zbl 1325.35245 · doi:10.1007/s00032-014-0216-8 |
| [58] | Viertel, Ryan; Osting, Braxton, An approach to quad meshing based on harmonic cross-valued maps and the Ginzburg-Landau theory, SIAM J. Sci. Comput., 41, 1, A452-A479 (2019) · Zbl 1410.35223 · doi:10.1137/17M1142703 |
| [59] | Wang, Dong; Li, Haohan; Wei, Xiaoyu; Wang, Xiao-Ping, An efficient iterative thresholding method for image segmentation, J. Comput. Phys., 350, 657-667 (2017) · Zbl 1380.65048 · doi:10.1016/j.jcp.2017.08.020 |
| [60] | Wang, Dong; Osting, Braxton, A diffusion generated method for computing Dirichlet partitions, J. Comput. Appl. Math., 351, 302-316 (2019) · Zbl 1407.51027 · doi:10.1016/j.cam.2018.11.015 |
| [61] | 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. · Zbl 1439.35408 |
| [62] | Wang, Dong; Wang, Xiao-Ping; Xu, Xianmin, An improved threshold dynamics method for wetting dynamics, J. Comput. Phys., 392, 291-310 (2019) · Zbl 1452.76191 · doi:10.1016/j.jcp.2019.04.037 |
| [63] | Xu, Xianmin; Wang, Dong; Wang, Xiao-Ping, 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 |
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.
