zbMATH — the first resource for mathematics

Parallel level-set methods on adaptive tree-based grids. (English) Zbl 1352.65253
Summary: We present scalable algorithms for the level-set method on dynamic, adaptive Quadtree and Octree Cartesian grids. The algorithms are fully parallelized and implemented using the standard and the open-source library. We solve the level set equation with a semi-Lagrangian method which, similar to its serial implementation, is free of any time-step restrictions. This is achieved by introducing a scalable global interpolation scheme on adaptive tree-based grids. Moreover, we present a simple parallel reinitialization scheme using the pseudo-time transient formulation. Both parallel algorithms scale on the Stampede supercomputer, where we are currently using up to 4096 CPU cores, the limit of our current account. Finally, a relevant application of the algorithms is presented in modeling a crystallization phenomenon by solving a Stefan problem, illustrating a level of detail that would be impossible to achieve without a parallel adaptive strategy. We believe that the algorithms presented in this article will be of interest and useful to researchers working with the level-set framework and modeling multi-scale physics in general.

65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
65M50 Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs
Full Text: DOI
[1] Adalsteinsson, D.; Sethian, J., A fast level set method for propagating interfaces, J. Comput. Phys., 118, 269-277, (1995) · Zbl 0823.65137
[2] Alexiades, V.; Solomon, A. D., Mathematical modeling of melting and freezing processes, (1993), Hemisphere Washington, DC
[3] Alexiades, V.; Solomon, A. D.; Wilson, D. G., The formation of a solid nucleus in supercooled liquid. I, J. Non-Equilib. Thermodyn., 13, 281-300, (1988) · Zbl 0668.76079
[4] Aluru, Srinivas; Sevilgen, F., Parallel domain decomposition and load balancing using space-filling curves, (Proceedings of Fourth International Conference on High-Performance Computing, 1997, (1997), IEEE), 230-235
[5] Balay, Satish; Abhyankar, Shrirang; Adams, Mark F.; Brown, Jed; Brune, Peter; Buschelman, Kris; Eijkhout, Victor; Gropp, William D.; Kaushik, Dinesh; Knepley, Matthew G.; Curfman McInnes, Lois; Rupp, Karl; Smith, Barry F.; Zhang, Hong, (2014), PETSc Web page
[6] Bangerth, W.; Hartmann, R.; Kanschat, G., Deal.II - a general purpose object oriented finite element library, ACM Trans. Math. Softw., 33, 4, 24/1-24/27, (2007) · Zbl 1365.65248
[7] Bangerth, Wolfgang; Burstedde, Carsten; Heister, Timo; Kronbichler, Martin, Algorithms and data structures for massively parallel generic adaptive finite element codes, ACM Trans. Math. Softw., 38, 2, 14, (2011) · Zbl 1365.65247
[8] Boman, Erik G.; Çatalyürek, Ümit V.; Chevalier, Cédric; Devine, Karen D., The zoltan and isorropia parallel toolkits for combinatorial scientific computing: partitioning, ordering and coloring, Sci. Program., 20, 2, 129-150, (2012)
[9] Breuß, Michael; Cristiani, Emiliano; Gwosdek, Pascal; Vogel, Oliver, An adaptive domain-decomposition technique for parallelization of the fast marching method, Appl. Math. Comput., 218, 1, 32-44, (2011) · Zbl 1269.65132
[10] Brun, Emmanuel; Guittet, Arthur; Gibou, Frederic, A local level-set method using a hash table data structure, J. Comp. Physiol., 231, 2528-2536, (2012) · Zbl 1242.65156
[11] Burstedde, C., P4est: parallel adaptive mesh refinement on forests of octrees, (June 19, 2015), last accessed
[12] Burstedde, Carsten; Ghattas, Omar; Gurnis, Michael; Stadler, Georg; Tan, Eh; Tu, Tiankai; Wilcox, Lucas C.; Zhong, Shijie, Scalable adaptive mantle convection simulation on petascale supercomputers, (Proceedings of the 2008 ACM/IEEE Conference on Supercomputing, (2008), IEEE Press), 62
[13] Burstedde, Carsten; Wilcox, Lucas C.; Ghattas, Omar, P4est: scalable algorithms for parallel adaptive mesh refinement on forests of octrees, SIAM J. Sci. Comput., 33, 3, 1103-1133, (2011) · Zbl 1230.65106
[14] Campbell, Paul M.; Devine, Karen D.; Flaherty, Joseph E.; Gervasio, Luis G.; Teresco, James D., Dynamic octree load balancing using space-filling curves, (2003), Williams College Department of Computer Science, Tech. Rep. CS-03-01
[15] Chacon, Adam; Vladimirsky, Alexander, A parallel heap-cell method for eikonal equations, (2013), arXiv preprint · Zbl 1348.49025
[16] Chen, Han; Min, Chohong; Gibou, Frederic, A numerical scheme for the Stefan problem on adaptive Cartesian grids with supralinear convergence rate, J. Comput. Phys., 228, 16, 5803-5818, (2009) · Zbl 1176.80059
[17] Detrixhe, Miles; Gibou, Frédéric; Min, Chohong, A parallel fast sweeping method for the eikonal equation, J. Comput. Phys., 237, 46-55, (March 2013)
[18] Drake, John; Foster, Ian; Michalakes, John; Toonen, Brian; Worley, Patrick, Design and performance of a scalable parallel community climate model, Parallel Comput., 21, 10, 1571-1591, (1995) · Zbl 0875.65128
[19] Enright, D.; Fedkiw, R.; Ferziger, J.; Mitchell, I., A hybrid particle level set method for improved interface capturing, J. Comput. Phys., 183, 83-116, (2002) · Zbl 1021.76044
[20] Fortmeier, Oliver; Bücker, H. Martin, A parallel strategy for a level set simulation of droplets moving in a liquid medium, (High Performance Computing for Computational Science-VECPAR 2010, (2011), Springer), 200-209 · Zbl 1323.65128
[21] Griebel, Michael; Zumbusch, Gerhard W., Parallel multigrid in an adaptive PDE solver based on hashing and space-filling curves, Parallel Comput., 25, 827-843, (1999) · Zbl 0945.65138
[22] Herrmann, M., A domain decomposition parallelization of the fast marching method, (2003), Technical report, DTIC Document
[23] Herrmann, Marcus, A parallel eulerian interface tracking/Lagrangian point particle multi-scale coupling procedure, J. Comput. Phys., 229, 3, 745-759, (2010) · Zbl 1253.76126
[24] Hoefler, Torsten; Siebert, Christian; Lumsdaine, Andrew, Scalable communication protocols for dynamic sparse data exchange, ACM SIGPLAN Not., 45, 5, 159-168, (2010)
[25] Isaac, Tobin; Burstedde, Carsten; Ghattas, Omar, Low-cost parallel algorithms for 2:1 octree balance, (Parallel & Distributed Processing Symposium (IPDPS), 2012 IEEE 26th International, (2012), IEEE), 426-437
[26] Isaac, Tobin; Burstedde, Carsten; Wilcox, Lucas C.; Ghattas, Omar, Recursive algorithms for distributed forests of octrees, SIAM J. Sci. Comput., 37, 5, C497-C531, (2015) · Zbl 1323.65105
[27] Jeong, W. K.; Whitaker, R. T., A fast iterative method for eikonal equations, SIAM J. Sci. Comput., 30, 5, 2512-2534, (2008) · Zbl 1246.70003
[28] Juric, D., A front-tracking method for dendritic solidification, J. Comput. Phys., 123, 1, 127-148, (January 1996)
[29] George Karypis, Vipin Kumar, METIS - Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0, 1995.
[30] Karypis, George; Kumar, Vipin, A parallel algorithm for multilevel graph partitioning and sparse matrix ordering, J. Parallel Distrib. Comput., 48, 1, 71-95, (1998)
[31] Losasso, F.; Gibou, F.; Fedkiw, R., Simulating water and smoke with an octree data structure, (ACM Trans. Graph., SIGGRAPH Proc., (2004)), 457-462
[32] Losasso, Frank; Fedkiw, Ron; Osher, Stanley, Spatially adaptive techniques for level set methods and incompressible flow, Comput. Fluids, 35, 995-1010, (2006) · Zbl 1177.76295
[33] Min, C.; Gibou, F., A second order accurate level set method on non-graded adaptive Cartesian grids, J. Comput. Phys., 225, 300-321, (2007) · Zbl 1122.65077
[34] Müller, Andreas; Kopera, Michal A.; Marras, Simone; Wilcox, Lucas C.; Isaac, Tobin; Giraldo, Francis X., Strong scaling for numerical weather prediction at petascale with the atmospheric model NUMA, (2015)
[35] Osher, S.; Fedkiw, R., Level set methods and dynamic implicit surfaces, (2002), Springer-Verlag New York, NY
[36] Osher, S.; Fedkiw, R. P., Level set methods: an overview and some recent results, J. Comput. Phys., 169, 463-502, (2001) · Zbl 0988.65093
[37] Osher, S.; Sethian, J. A., Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79, 12-49, (1988) · Zbl 0659.65132
[38] Popinet, S., Gerris: a tree-based adaptive solver for the incompressible Euler equations in complex geometries, J. Comput. Phys., 190, 572-600, (2003) · Zbl 1076.76002
[39] Rodriguez, Joseph M.; Sahni, Onkar; Lahey, Richard T.; Jansen, Kenneth E., A parallel adaptive mesh method for the numerical simulation of multiphase flows, Comput. Fluids, 87, 115-131, (2013) · Zbl 1290.76072
[40] Rudi, Johann; Malossi, A. Cristiano I.; Isaac, Tobin; Stadler, Georg; Gurnis, Michael; Staar, Peter W. J.; Ineichen, Yves; Bekas, Costas; Curioni, Alessandro; Ghattas, Omar, An extreme-scale implicit solver for complex PDEs: highly heterogeneous flow in Earth’s mantle, (Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, (2015), ACM), 5
[41] Sahni, O.; Zhou, M.; Shephard, M. S.; Jansen, K. E., Scalable implicit finite element solver for massively parallel processing with demonstration to 160 K cores, (SC09: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, (2009))
[42] Samet, H., Applications of spatial data structures: computer graphics, image processing and GIS, (1990), Addison-Wesley New York
[43] Sampath, Rahul S.; Adavani, Santi S.; Sundar, Hari; Lashuk, Ilya; Biros, George, Dendro: parallel algorithms for multigrid and AMR methods on 2:1 balanced octrees, (Proceedings of the 2008 ACM/IEEE Conference on Supercomputing, (2008), IEEE Press), 18
[44] Sampath, Rahul S.; Biros, George, A parallel geometric multigrid method for finite elements on octree meshes, SIAM J. Sci. Comput., 32, 3, 1361-1392, (2010) · Zbl 1213.65144
[45] Sethian, J., A fast marching level set method for monotonically advancing fronts, Proc. Natl. Acad. Sci., 93, 1591-1595, (1996) · Zbl 0852.65055
[46] Sethian, J. A., Level set methods and fast marching methods, (1999), Cambridge University Press · Zbl 0929.65066
[47] Stewart, James R.; Edwards, H. Carter, A framework approach for developing parallel adaptive multiphysics applications, Finite Elem. Anal. Des., 40, 12, 1599-1617, (2004)
[48] Strain, J., Tree methods for moving interfaces, J. Comput. Phys., 151, 616-648, (1999) · Zbl 0942.76061
[49] Sussman, M.; Smereka, P.; Osher, S., A level set approach for computing solutions to incompressible two-phase flow, J. Comput. Phys., 114, 146-159, (1994) · Zbl 0808.76077
[50] Sussman, Mark, A parallelized, adaptive algorithm for multiphase flows in general geometries, Comput. Struct., 83, 6, 435-444, (2005)
[51] Theillard, M.; Gibou, F.; Pollock, T., A sharp computational method for the simulation of the solidification of binary alloys, J. Sci. Comput., (2014)
[52] Thomas, S.; Côté, J., Massively parallel semi-Lagrangian advection, Simul. Pract. Theory, 3, 4, 223-238, (1995)
[53] Towns, John; Cockerill, Timothy; Dahan, Maytal; Foster, Ian; Gaither, Kelly; Grimshaw, Andrew; Hazlewood, Victor; Lathrop, Scott; Lifka, Dave; Peterson, Gregory D.; Roskies, Ralph; Scott, J. Ray; Wilkens-Diehr, Nancy, Xsede: accelerating scientific discovery, Comput. Sci. Eng., 16, 5, 62-74, (2014)
[54] Tryggvason, G.; Bunner, B.; Esmaeeli, A.; Juric, D.; Al-Rawahi, N.; Tauber, W.; Han, J.; Nas, S.; Jan, Y.-J., A front-tracking method for the computations of multiphase flow, J. Comput. Phys., 169, 708-759, (2001) · Zbl 1047.76574
[55] Tu, Tiankai; O’Hallaron, David R.; Ghattas, Omar, Scalable parallel octree meshing for terascale applications, (SC’05: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis, (2005), IEEE)
[56] Tugurlan, Maria Cristina, Fast marching methods-parallel implementation and analysis, (2008), Louisiana State University, PhD thesis
[57] Wang, Kai; Chang, Anthony; Kale, Laxmikant V.; Dantzig, Jonathan A., Parallelization of a level set method for simulating dendritic growth, J. Parallel Distrib. Comput., 66, 11, 1379-1386, (2006) · Zbl 1178.68631
[58] White, J. B.; Dongarra, Jack J., High-performance high-resolution semi-Lagrangian tracer transport on a sphere, J. Comput. Phys., 230, 17, 6778-6799, (2011) · Zbl 1229.86011
[59] Zhao, Hongkai, A fast sweeping method for eikonal equations, Math. Comput., 74, 250, 603-627, (2005) · Zbl 1070.65113
[60] Zhao, Hongkai, Parallel implementations of the fast sweeping method, J. Comput. Math., 25, 421-429, (2007)
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.