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

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

Kybernetika (2011)

  • Volume: 47, Issue: 2, page 251-272
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Oberhuber, Tomáš, Suzuki, Atsushi, and Žabka, Vítězslav. "The CUDA implementation of the method of lines for the curvature dependent flows." Kybernetika 47.2 (2011): 251-272. <http://eudml.org/doc/197096>.

@article{Oberhuber2011,
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.},
author = {Oberhuber, Tomáš, Suzuki, Atsushi, Žabka, Vítězslav},
journal = {Kybernetika},
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; 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; computer graphics; image processing; graphics processing unit; compute unified device architecture},
language = {eng},
number = {2},
pages = {251-272},
publisher = {Institute of Information Theory and Automation AS CR},
title = {The CUDA implementation of the method of lines for the curvature dependent flows},
url = {http://eudml.org/doc/197096},
volume = {47},
year = {2011},
}

TY - JOUR
AU - Oberhuber, Tomáš
AU - Suzuki, Atsushi
AU - Žabka, Vítězslav
TI - The CUDA implementation of the method of lines for the curvature dependent flows
JO - Kybernetika
PY - 2011
PB - Institute of Information Theory and Automation AS CR
VL - 47
IS - 2
SP - 251
EP - 272
AB - 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.
LA - eng
KW - 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; 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; computer graphics; image processing; graphics processing unit; compute unified device architecture
UR - http://eudml.org/doc/197096
ER -

References

top
  1. Baskaran, M. M., Bordaweker, R., Optimizing Sparse-Vector Matrix Multiplication on Gpus, IBM Research Report RC24704, IBM 2009. (2009) 
  2. Bell, N., Garland, M., Implementing sparse matrix-vector multiplication on throughput oriented processors, In Supercomputing’09, Nov. 2009. (2009) 
  3. Beneš, M., Mathematical and computational aspects of solidification of pure substances, Acta Math. Univ. Comenian. 70 (2000), 123–151. (2000) MR1865364
  4. Beneš, M., 10.4171/IFB/38, Interfaces and Free Boundaries 3 (2001), 201–221. (2001) Zbl0986.35116MR1825658DOI10.4171/IFB/38
  5. Beneš, M., 10.1023/B:APOM.0000024485.24886.b9, Appl. Math. 80 (2003), 6, 437–453. (2003) Zbl1099.53044MR2025297DOI10.1023/B:APOM.0000024485.24886.b9
  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. (1997) 
  7. Beneš, M., Mikula, K., Oberhuber, T., Ševčovič, D., 10.1007/s00791-008-0112-2, Computing and Visualization in Science 12 (2009), 307–317. (2009) MR2520782DOI10.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. (2006) MR2232523
  9. Bolz, J., Farmer, I., Grinspun, E., Schröder, P., 10.1145/882262.882364, ACM Trans. Graphics 22 (2003), 3, 917–924. (2003) DOI10.1145/882262.882364
  10. Buatois, L., Caumon, G., Levy, B., 10.1080/17445760802337010, Internat. J. Parallel Emerg. Distrib. Syst. 24 (2009), 3, 205–223. (2009) MR2750686DOI10.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. (1991) Zbl0696.35087MR1100211
  12. Clarenz, U., 10.4171/IFB/104, Interfaces and Free Boundaries 6 (2004), 351–360. (2004) Zbl1072.35184MR2095337DOI10.4171/IFB/104
  13. Clarenz, U., Diewald, U., Dziuk, G., Rumpf, M., Rusu, R., 10.1016/j.cagd.2004.02.004, Computer Aided Geometric Design 21 (2004), 5, 427–445. (2004) Zbl1069.65546MR2058390DOI10.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. (1812) MR2011033
  15. Dziuk, G., Kuwert, E., Schätzle, R., Evolution of elastic curves in ℝ n : Existence and computation, SIAM J. Math. Anal.41 (2003), 6, 2161–2179. (2003) 
  16. Evans, L. C., Spruck, J., 10.1090/S0002-9947-1992-1068927-8, Trans. Amer. Math. Soc. 330 (1993), 1, 321–332. (1993) MR1068927DOI10.1090/S0002-9947-1992-1068927-8
  17. Giga, Y., Surface evolution equations: A level set approach, Birkhauser Verlag 2006. (2006) Zbl1096.53039MR2238463
  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. (2007) 
  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. (2008) 
  20. Göddeke, D., Wobker, H., Strzodka, R., Mohd-Yusof, J., McCormick, P., Turek, S., 10.1504/IJCSE.2009.029162, Internat. J. Comput. Sci. Engrg. 4 (2009), 4, 254–269. (2009) DOI10.1504/IJCSE.2009.029162
  21. Grama, A., Gupta, A., Karypis, G., Kumar, V., Introduction to Parallel Computing, Pearson, Addison Wesley 2003. (2003) 
  22. Gurtin, M. E., On the two-phase stefan problem with interfacial energy and entropy, Arch. Rational Mech. Anal. 96 (1986), 200–240. (1986) Zbl0654.73008MR0855304
  23. Handlovičová, A., Mikula, K., Sgallari, F., 10.1007/s002110100374, Numer. Math. 93 (2003), 675–695. (2003) Zbl1065.65105MR1961884DOI10.1007/s002110100374
  24. Harris, M., Optimizing parallel reduction in cuda, NVIDIA CUDA SDK 2007. (2007) 
  25. Helfrich, W., Elastic properties of lipid bilayers: theory and possible experiments, Zeitschrift für Naturforschung 28 (1973), 693–703. (1973) 
  26. Huisken, G., Flow by mean curvature of convex surfaces into spheres, J. Differential Geometry 20 (1984), 237–266. (1984) Zbl0556.53001MR0772132
  27. Huisken, G., 10.1016/0022-0396(89)90149-6, J. Differential Geom. 77 (1988), 369–379. (1988) DOI10.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 for the Study of Moving Boundary Problems, Matfyzpress, Publishing House of Mathematics and Physics, Charles University in Prague 2008, pp. 39–94. (2008) MR2868564
  29. Kruger, J., Westermann, R., 10.1145/882262.882363, ACM Trans. Graphics 22 (2003), 3, 908–916. (2003) DOI10.1145/882262.882363
  30. Kuwert, E., Schätzle, R., Gradient flow for the Willmore functional, Comm. Anal. Geom. 10 (2003), 2, 307–340. (2003) MR1900754
  31. Kuwert, E., Schätzle, R., The Willmore flow with small initial energy, J. Differ. Geom. 57 (2001), 409–441. (2001) Zbl1035.53092MR1882663
  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. (2003) MR2013200
  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. (2002) Zbl1065.94502MR2004358
  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. (2007) 
  35. Nitsche, J. C. C., On new results in the theory of minimal surfaces, Bull. Amer. Math. Soc. 71 (1965), 195–270. (1965) Zbl0135.21701MR0173993
  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. (2009) Zbl1172.65375
  37. Oberhuber, T., Numerical Solution of Willmore Flow, PhD. Thesis, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, 2009. (2009) 
  38. Pharr, M., ed., GPU Gems 2: Programming Techniques for High-Performance Graphics and General–Purpose Computation, Addison-Wesley, 2005. (2005) 
  39. Simonett, G., The Willmore flow near spheres, Differential and Integral Equations 14 (2001), 8, 1005–1014. (2001) Zbl1161.35429MR1827100
  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. (2009) 
  41. Svetina, S., Žekš, B., 10.1007/BF00257107, Eur. Biophys. J. 17 (1989), 101–111. (1989) DOI10.1007/BF00257107
  42. Vitásek, E., Numerické metody (In Czech), SNTL, Nakladatelství technické literatury, 1987. (1987) 
  43. Walkington, N. J., 10.1137/S0036142994262068, SIAM J. Numer. Anal. 33 (1996), 6, 2215–2238. (1996) Zbl0863.65061MR1427460DOI10.1137/S0036142994262068
  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. (2010) 
  45. Nvidia, NVIDIA CUDA Programming Guide 3.0, http://developer.download.nvidia.com/compute/cuda/3_0/toolkit/docs/NVIDIA_CUDA_ProgrammingGuide.pdf, 2010. (2010) 

NotesEmbed ?

top

You must be logged in to post comments.