Article
Full entry |
PDF
(1.1 MB)
Feedback
PDF
(1.1 MB)
Feedback
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
Summary:
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.
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. MR 1865364
[4] Beneš, M.: Mathematical analysis of phase-field equations with numerically efficient coupling terms. Interfaces and Free Boundaries 3 (2001), 201–221. DOI 10.4171/IFB/38 | MR 1825658 | Zbl 0986.35116
[5] Beneš, M.: Diffuse-interface treatment of the anisotropic mean-curvature flow. Appl. Math. 80 (2003), 6, 437–453. DOI 10.1023/B:APOM.0000024485.24886.b9 | MR 2025297 | Zbl 1099.53044
[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 10.1007/s00791-008-0112-2 | MR 2520782
[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 2232523
[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.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. DOI 10.1080/17445760802337010 | MR 2750686
[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 1100211 | Zbl 0696.35087
[12] Clarenz, U.: The Wulff shape minimizes an anisotropic Willmore functional. Interfaces and Free Boundaries 6 (2004), 351–360. DOI 10.4171/IFB/104 | MR 2095337 | Zbl 1072.35184
[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 10.1016/j.cagd.2004.02.004 | MR 2058390 | Zbl 1069.65546
[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 2011033
[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 10.1090/S0002-9947-1992-1068927-8 | MR 1068927
[17] Giga, Y.: Surface evolution equations: A level set approach. Birkhauser Verlag 2006. MR 2238463 | 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.
[22] Gurtin, M. E.: On the two-phase stefan problem with interfacial energy and entropy. Arch. Rational Mech. Anal. 96 (1986), 200–240. MR 0855304 | 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. DOI 10.1007/s002110100374 | MR 1961884 | Zbl 1065.65105
[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 0772132 | Zbl 0556.53001
[27] Huisken, G.: Non-parametric mean curvature evolution with boudary conditions. J. Differential Geom. 77 (1988), 369–379. 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. MR 2868564
[29] Kruger, J., Westermann, R.: Linear algebra operators for gpu implementation of numerical algorithms. ACM Trans. Graphics 22 (2003), 3, 908–916. 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. MR 1900754
[31] Kuwert, E., Schätzle, R.: The Willmore flow with small initial energy. J. Differ. Geom. 57 (2001), 409–441. MR 1882663 | 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. MR 2013200
[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 2004358 | Zbl 1065.94502
[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 0173993 | Zbl 0135.21701
[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 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., 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 1827100 | Zbl 1161.35429
[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 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. DOI 10.1137/S0036142994262068 | MR 1427460 | Zbl 0863.65061
[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.
Search
Partner of
