The CUDA implementation of the method of lines for the curvature dependent flows

Oberhuber, Tomáš   ; Suzuki, Atsushi   ; Žabka, Vítězslav

Kybernetika, Tome 47 (2011) no. 2, pp. 251-272

Abstract (VO)

We study the use of a 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 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.

Détail

Classification : 35K52, 35K55, 53A05, 53C44, 68W10, 74G15, 74S10
Keywords: GPGPU; CUDA; parallel algorithms; high performance computing; differential geometry; mean-curvature flow; Willmore flow; Runge--Kutta method; method of lines; explicit scheme; complementary finite volume method

Bibliographie

[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. | MR

[4] Beneš, M.: Mathematical analysis of phase-field equations with numerically efficient coupling terms. Interfaces and Free Boundaries 3 (2001), 201–221. | DOI | MR | Zbl

[5] Beneš, M.: Diffuse-interface treatment of the anisotropic mean-curvature flow. Appl. Math. 80 (2003), 6, 437–453. | DOI | MR | Zbl

[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. | DOI | MR

[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. | MR

[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. | DOI

[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. | DOI | MR

[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. | MR | Zbl

[12] Clarenz, U.: The Wulff shape minimizes an anisotropic Willmore functional. Interfaces and Free Boundaries 6 (2004), 351–360. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[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. | MR

[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. | DOI | MR

[17] Giga, Y.: Surface evolution equations: A level set approach. Birkhauser Verlag 2006. | MR | Zbl

[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

[21] Grama, A., Gupta, A., Karypis, G., Kumar, V.: Introduction to Parallel Computing. Pearson, Addison Wesley 2003.

[22] Gurtin, M. E.: On the two-phase stefan problem with interfacial energy and entropy. Arch. Rational Mech. Anal. 96 (1986), 200–240. | MR | Zbl

[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. | DOI | MR | Zbl

[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. | MR | Zbl

[27] Huisken, G.: Non-parametric mean curvature evolution with boudary conditions. J. Differential Geom. 77 (1988), 369–379. | DOI

[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. | MR

[29] Kruger, J., Westermann, R.: Linear algebra operators for gpu implementation of numerical algorithms. ACM Trans. Graphics 22 (2003), 3, 908–916. | DOI

[30] Kuwert, E., Schätzle, R.: Gradient flow for the Willmore functional. Comm. Anal. Geom. 10 (2003), 2, 307–340. | MR

[31] Kuwert, E., Schätzle, R.: The Willmore flow with small initial energy. J. Differ. Geom. 57 (2001), 409–441. | MR | Zbl

[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. | MR

[33] Mikula, K.: Image processing with partial differential equations. In: Modern Methods in Scientific Computing and Applications (A. Bourlioux and M. Gander, eds.), NATO Science Ser. II 75, Kluwer Academic Publishers, Dodrecht 2002, pp. 283–322. | MR | Zbl

[34] Mikula, K., Sarti, A.: Parametric and geometric deformable models: An application in biomaterials and medical imagery. In: 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. | MR | Zbl

[36] Oberhuber, T.: Complementary finite volume scheme for the anisotropic surface diffusion flow. In: Proc. Algoritmy 2009 (A. Handlovičová, P. Frolkovič, K. Mikula, and D. Ševčovič, eds.), pp. 153–164. | Zbl

[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., ed.: 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. | MR | Zbl

[40] Šimek, V., Dvořák, R., Zbořil, F., Kunovský, J.: Towards accelerated computation of atmospheric equations using CUDA. In: 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

[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. | DOI | MR | Zbl

[44] Zhang, Y., Cohen, J., Owens, J. D.: Fast tridiagonal solvers on the gpu. In: Proc. 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming 2010, p. 10.

[45] Nvidia: NVIDIA CUDA Programming Guide 3.0. http://developer.download.nvidia.com/compute/cuda/3_0/toolkit/docs/NVIDIA_CUDA_ProgrammingGuide.pdf, 2010.