×

zbMATH — the first resource for mathematics

The CUDA implementation of the method of lines for the curvature dependent flows. (English) Zbl 1221.65071
Summary: We study the use of a graphics processing unit (GPU) for the numerical approximation of the curvature dependent flows of graphs – the mean-curvature flow and the Willmore flow. Both problems are often applied in image processing where fast solvers are required. We approximate these problems using the complementary finite volume method combined with the method of lines. We obtain a system of ordinary differential equations which we solve by the Runge-Kutta-Merson solver. It is a robust solver with an automatic choice of the integration time step. We implement this solver on CPU but also on GPU using the compute unified device architecture (CUDA) toolkit. We demonstrate that the mean-curvature flow can be successfully approximated in single precision arithmetic with the speed-up almost 17 on the Nvidia GeForce GTX 280 card compared to Intel Core 2 Quad CPU. On the same card, we obtain the speed-up 7 in double precision arithmetic which is necessary for the fourth order problem – the Willmore flow of graphs. Both speed-ups were achieved without affecting the accuracy of the approximation. The article is structured in such way that the reader interested only in the implementation of the Runge-Kutta-Merson solver on the GPU can skip the sections containing the mathematical formulation of the problems.

MSC:
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
35K20 Initial-boundary value problems for second-order parabolic equations
65M20 Method of lines for initial value and initial-boundary value problems involving PDEs
65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
65Y05 Parallel numerical computation
65M08 Finite volume methods for initial value and initial-boundary value problems involving PDEs
65D17 Computer-aided design (modeling of curves and surfaces)
68U10 Computing methodologies for image processing
68W10 Parallel algorithms in computer science
Software:
CUDA
PDF BibTeX XML Cite
Full Text: Link EuDML
References:
[1] Baskaran, M. M., Bordaweker, R.: Optimizing Sparse-Vector Matrix Multiplication on Gpus. IBM Research Report RC24704, IBM 2009.
[2] Bell, N., Garland, M.: Implementing sparse matrix-vector multiplication on throughput oriented processors. In Supercomputing’09, Nov. 2009.
[3] Beneš, M.: Mathematical and computational aspects of solidification of pure substances. Acta Math. Univ. Comenian. 70 (2000), 123-151. · Zbl 0990.80006 · eudml:121936
[4] Beneš, M.: Mathematical analysis of phase-field equations with numerically efficient coupling terms. Interfaces and Free Boundaries 3 (2001), 201-221. · Zbl 0986.35116 · doi:10.4171/IFB/38
[5] Beneš, M.: Diffuse-interface treatment of the anisotropic mean-curvature flow. Appl. Math. 80 (2003), 6, 437-453. · Zbl 1099.53044 · doi:10.1023/B:APOM.0000024485.24886.b9 · eudml:33159
[6] Beneš, M.: Phase Field Model of Microstructure Growth in Solidification of Pure Substances. PhD. Dissertation, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University, Prague 1997.
[7] Beneš, M., Mikula, K., Oberhuber, T., Ševčovič, D.: Comparison study for level set and direct Lagrangian methods for computing Willmore flow of closed plannar curves. Computing and Visualization in Science 12 (2009), 307-317. · Zbl 1213.35033 · doi:10.1007/s00791-008-0112-2
[8] Bertalmio, M., Caselles, V., Haro, G., Sapiro, G.: Handbook of Mathematical Models in Computer Vision. PDE-Based Image and Surface Inpainting, Springer 2006, pp. 33-61.
[9] Bolz, J., Farmer, I., Grinspun, E., Schröder, P.: Sparse matrix solvers on the gpu: Conjugate gradients and multigrid. ACM Trans. Graphics 22 (2003), 3, 917-924. · Zbl 05457243 · doi:10.1145/882262.882364
[10] Buatois, L., Caumon, G., Levy, B.: Concurrent number cruncher: a gpu implementation of a general sparse linear solver. Internat. J. Parallel Emerg. Distrib. Syst. 24 (2009), 3, 205-223. · Zbl 05596071 · doi:10.1080/17445760802337010
[11] Chen, Y.-G., Giga, Y., Goto, S.: Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations. J. Differential Geom. 33 (1991), 3, 749-786. · Zbl 0696.35087
[12] Clarenz, U.: The Wulff shape minimizes an anisotropic Willmore functional. Interfaces and Free Boundaries 6 (2004), 351-360. · Zbl 1072.35184 · doi:10.4171/IFB/104
[13] Clarenz, U., Diewald, U., Dziuk, G., Rumpf, M., Rusu, R.: A finite element method for surface restoration with smooth boundary conditions. Computer Aided Geometric Design 21 (2004), 5, 427-445. · Zbl 1069.65546 · doi:10.1016/j.cagd.2004.02.004
[14] Deckelnick, K., Dziuk, G.: Mathematical aspects of evolving interfaces. Lecture Notes in Math. 1812, Numerical Approximation of Mean Curvature Flow of Graphs and Level Sets, Springer-Verlag, Berlin-Heidelberg 2003, pp. 53-87. · Zbl 1036.65076
[15] Dziuk, G., Kuwert, E., Schätzle, R.: Evolution of elastic curves in \(\mathbb {R}^n\): Existence and computation. SIAM J. Math. Anal.41 (2003), 6, 2161-2179.
[16] Evans, L. C., Spruck, J.: Motion of level sets by mean curvature II. Trans. Amer. Math. Soc. 330 (1993), 1, 321-332. · Zbl 0776.53005 · doi:10.2307/2154167
[17] Giga, Y.: Surface evolution equations: A level set approach. Birkhauser Verlag 2006. · Zbl 1096.53039
[18] Göddeke, D., Strzodka, R., Mohd-Yusof, J., McCormick, P., Buijssen, S. H., Grajewski, M., Turek, S.: Exploring weak scalability for fem calculations on a gpu-enhanced cluster. Parallel Computing, Special issue: High-performance computing using accelerators 33 (2007), 685-699.
[19] Göddeke, D., Strzodka, R., Mohd-Yusof, J., McCormick, P., Wobker, H., Becker, C., Turek, S.: Using gpus to improve multigrid solver performance on a cluster. Internat. J. Comput. Sci. Engrg. 4 (2008), 1, 36-55.
[20] Göddeke, D., Wobker, H., Strzodka, R., Mohd-Yusof, J., McCormick, P., Turek, S.: Co-processor acceleration of an unmodified parallel solid mechanics code with feastgpu. Internat. J. Comput. Sci. Engrg. 4 (2009), 4, 254-269. · doi:10.1504/IJCSE.2009.029162
[21] Grama, A., Gupta, A., Karypis, G., Kumar, V.: Introduction to Parallel Computing. Pearson, Addison Wesley 2003. · Zbl 0861.68040
[22] Gurtin, M. E.: On the two-phase stefan problem with interfacial energy and entropy. Arch. Rational Mech. Anal. 96 (1986), 200-240. · Zbl 0654.73008
[23] Handlovičová, A., Mikula, K., Sgallari, F.: Semi-implicit complementary volume scheme for solving level set like equations in image processing and curve evolution. Numer. Math. 93 (2003), 675-695. · Zbl 1065.65105 · doi:10.1007/s002110100374
[24] Harris, M.: Optimizing parallel reduction in cuda. NVIDIA CUDA SDK 2007.
[25] Helfrich, W.: Elastic properties of lipid bilayers: theory and possible experiments. Zeitschrift für Naturforschung 28 (1973), 693-703.
[26] Huisken, G.: Flow by mean curvature of convex surfaces into spheres. J. Differential Geometry 20 (1984), 237-266. · Zbl 0556.53001
[27] Huisken, G.: Non-parametric mean curvature evolution with boudary conditions. J. Differential Geom. 77 (1988), 369-379. · Zbl 0686.34013 · doi:10.1016/0022-0396(89)90149-6
[28] Kimura, M.: Topics in mathematical modeling. Jindřich Nečas Center for Mathematical Modelling 4, Lecture Notes, Geometry of Hypersurfaces and Moving Hypersurfaces in \(R^m\) for the Study of Moving Boundary Problems, Matfyzpress, Publishing House of Mathematics and Physics, Charles University in Prague 2008, pp. 39-94.
[29] Kruger, J., Westermann, R.: Linear algebra operators for gpu implementation of numerical algorithms. ACM Trans. Graphics 22 (2003), 3, 908-916. · Zbl 05457403 · doi:10.1145/882262.882363
[30] Kuwert, E., Schätzle, R.: Gradient flow for the Willmore functional. Comm. Anal. Geom. 10 (2003), 2, 307-340. · Zbl 1029.53082
[31] Kuwert, E., Schätzle, R.: The Willmore flow with small initial energy. J. Differ. Geom. 57 (2001), 409-441. · Zbl 1035.53092
[32] Mayer, U. F., Simonett, G.: Evolution equations: Applications to physics, industry, life scienses economics. Self-intersections for Willmore flow, Progress in nonlinear differential equations and their applications, Birkhäuser Verlag, Basel 2003, pp. 341-348. · Zbl 1046.53046
[33] Mikula, K.: Image processing with partial differential equations. Modern Methods in Scientific Computing and Applications (A. Bourlioux and M. Gander, NATO Science Ser. II 75, Kluwer Academic Publishers, Dodrecht 2002, pp. 283-322. · Zbl 1065.94502
[34] Mikula, K., Sarti, A.: Parametric and geometric deformable models: An application in biomaterials and medical imagery. Parallel co-volume subjective surface method for 3D medical image segmentation 2, 2007, pp. 123-160.
[35] Nitsche, J. C. C.: On new results in the theory of minimal surfaces. Bull. Amer. Math. Soc. 71 (1965), 195-270. · Zbl 0135.21701 · doi:10.1090/S0002-9904-1965-11276-9
[36] Oberhuber, T.: Complementary finite volume scheme for the anisotropic surface diffusion flow. Proc. Algoritmy 2009 (A. Handlovičová, P. Frolkovič, K. Mikula, and D. Ševčovič, pp. 153-164. · Zbl 1172.65375
[37] Oberhuber, T.: Numerical Solution of Willmore Flow. PhD. Thesis, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, 2009.
[38] Pharr, M.: GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation. Addison-Wesley, 2005.
[39] Simonett, G.: The Willmore flow near spheres. Differential and Integral Equations 14 (2001), 8, 1005-1014. · Zbl 1161.35429
[40] Šimek, V., Dvořák, R., Zbořil, F., Kunovský, J.: Towards accelerated computation of atmospheric equations using CUDA. 11th Internat. Conf. on Computer Modelling and Simulation, pp. 449-454, 2009.
[41] Svetina, S., Žekš, B.: Membrane bending energy and shape determination of phospholipid vesicles and red blood cells. Eur. Biophys. J. 17 (1989), 101-111. · doi:10.1007/BF00257107
[42] Vitásek, E.: Numerické metody (In Czech). SNTL, Nakladatelství technické literatury, 1987.
[43] Walkington, N. J.: Algorithms for computing motion by mean curvature. SIAM J. Numer. Anal. 33 (1996), 6, 2215-2238. · Zbl 0863.65061 · doi:10.1137/S0036142994262068
[44] Zhang, Y., Cohen, J., Owens, J. D.: Fast tridiagonal solvers on the gpu. Proc. 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming 2010, p. 10.
[45] Nvidia: NVIDIA CUDA Programming Guide 3.0. , 2010. · developer.download.nvidia.com
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.