Kybernetika 47 no. 2, 251-272, 2011

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

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

Abstract:

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.

Keywords:

Willmore flow, method of lines, GPGPU, CUDA, parallel algorithms, high performance computing, differential geometry, mean-curvature flow, Runge-Kutta method, explicit scheme, complementary finite volume method

Classification:

35K55, 68W10, 74S10, 53C44, 35K52, 53A05, 74G15

References:

  1. M. M. Baskaran and R. Bordaweker: Optimizing Sparse-Vector Matrix Multiplication on Gpus. IBM Research Report RC24704, IBM 2009.   CrossRef
  2. N. Bell and M. Garland: Implementing sparse matrix-vector multiplication on throughput oriented processors. In Supercomputing'09, Nov. 2009.   CrossRef
  3. M. Beneš: Mathematical and computational aspects of solidification of pure substances. Acta Math. Univ. Comenian. 70 (2000), 123-151.   CrossRef
  4. M. Beneš: Mathematical analysis of phase-field equations with numerically efficient coupling terms. Interfaces and Free Boundaries 3 (2001), 201-221.   CrossRef
  5. M. Beneš: Diffuse-interface treatment of the anisotropic mean-curvature flow. Appl. Math. 80 (2003), 6, 437-453.   CrossRef
  6. M. Bertalmio, V. Caselles, G. Haro and G. Sapiro: Handbook of Mathematical Models in Computer Vision. PDE-Based Image and Surface Inpainting, Springer 2006, pp. 33-61.   CrossRef
  7. J. Bolz, I. Farmer, E. Grinspun and P. Schröder: Sparse matrix solvers on the gpu: Conjugate gradients and multigrid. ACM Trans. Graphics 22 (2003), 3, 917-924.   CrossRef
  8. L. Buatois, G. Caumon and B. Levy: Concurrent number cruncher: a gpu implementation of a general sparse linear solver. Internat. J. Parallel Emerg. Distrib. Syst. 24 (2009), 3, 205-223.   CrossRef
  9. Y.-G. Chen, Y. Giga and S. Goto: Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations. J. Differential Geom. 33 (1991), 3, 749-786.   CrossRef
  10. U. Clarenz, U. Diewald, G. Dziuk, M. Rumpf and R. Rusu: A finite element method for surface restoration with smooth boundary conditions. Computer Aided Geometric Design 21 (2004), 5, 427-445.   CrossRef
  11. K. Deckelnick and G. Dziuk: 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.   CrossRef
  12. Y. Giga: Surface evolution equations: A level set approach. Birkhauser Verlag 2006.   CrossRef
  13. D. Göddeke, R. Strzodka, J. Mohd-Yusof, P. McCormick, S. H. Buijssen, M. Grajewski and S. Turek: Exploring weak scalability for fem calculations on a gpu-enhanced cluster. Parallel Computing, Special issue: High-performance computing using accelerators 33 (2007), 685-699.   CrossRef
  14. D. Göddeke, R. Strzodka, J. Mohd-Yusof, P. McCormick, H. Wobker, C. Becker and S. Turek: Using gpus to improve multigrid solver performance on a cluster. Internat. J. Comput. Sci. Engrg. 4 (2008), 1, 36-55.   CrossRef
  15. D. Göddeke, H. Wobker, R. Strzodka, J. Mohd-Yusof, P. McCormick and S. Turek: Co-processor acceleration of an unmodified parallel solid mechanics code with feastgpu. Internat. J. Comput. Sci. Engrg. 4 (2009), 4, 254-269.   CrossRef
  16. A. Grama, A. Gupta, G. Karypis and V. Kumar: Introduction to Parallel Computing. Pearson, Addison Wesley 2003.   CrossRef
  17. M. E. Gurtin: On the two-phase stefan problem with interfacial energy and entropy. Arch. Rational Mech. Anal. 96 (1986), 200-240.   CrossRef
  18. A. Handlovičová, K. Mikula and F. Sgallari: Semi-implicit complementary volume scheme for solving level set like equations in image processing and curve evolution. Numer. Math. 93 (2003), 675-695.   CrossRef
  19. M. Harris: Optimizing parallel reduction in cuda. {N}{V}{I}{D}{I}{A} {C}{U}{D}{A} {S}{D}{K} 2007.   CrossRef
  20. W. Helfrich: Elastic properties of lipid bilayers: theory and possible experiments. Zeitschrift für Naturforschung {\mi 28} (1973), 693-703.   CrossRef
  21. G. Huisken: Flow by mean curvature of convex surfaces into spheres. J. Differential Geometry 20 (1984), 237-266.   CrossRef
  22. G. Huisken: Non-parametric mean curvature evolution with boudary conditions. J. Differential Geom. 77 (1988), 369-379.   CrossRef
  23. M. Kimura: 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.   CrossRef
  24. J. Kruger and R. Westermann: Linear algebra operators for gpu implementation of numerical algorithms. ACM Trans. Graphics 22 (2003), 3, 908-916.   CrossRef
  25. U. F. Mayer and G. Simonett: 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.   CrossRef
  26. K. Mikula: 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.   CrossRef
  27. K. Mikula and A. Sarti: 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.   CrossRef
  28. J. C. C. Nitsche: On new results in the theory of minimal surfaces. Bull. Amer. Math. Soc. 71 (1965), 195-270.   CrossRef
  29. T. Oberhuber: 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.   CrossRef
  30. T. Oberhuber: Numerical Solution of Willmore Flow. PhD. Thesis, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, 2009.   CrossRef
  31. M. Pharr and ed.: GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation. Addison-Wesley, 2005.   CrossRef
  32. S. Svetina and B. Žekš: Membrane bending energy and shape determination of phospholipid vesicles and red blood cells. Eur. Biophys. J. 17 (1989), 101-111.   CrossRef
  33. E. Vitásek: Numerické metody (In Czech). SNTL, Nakladatelstv\'{i} technické literatury, 1987.   CrossRef
  34. N. J. Walkington: Algorithms for computing motion by mean curvature. SIAM J. Numer. Anal. 33 (1996), 6, 2215-2238.   CrossRef
  35. Y. Zhang, J. Cohen and J. D. Owens: Fast tridiagonal solvers on the gpu. In: Proc. 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming 2010, p. 10.   CrossRef