{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T06:13:56Z","timestamp":1764828836786,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,1,22]],"date-time":"2021-01-22T00:00:00Z","timestamp":1611273600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,22]],"date-time":"2021-01-22T00:00:00Z","timestamp":1611273600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2017\/26\/M\/ ST1\/ 00281"],"award-info":[{"award-number":["2017\/26\/M\/ ST1\/ 00281"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008562","name":"University of Texas at Austin","doi-asserted-by":"publisher","award":["JTO Oden Research Faculty Fellowship"],"award-info":[{"award-number":["JTO Oden Research Faculty Fellowship"]}],"id":[{"id":"10.13039\/100008562","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1337281","1406355"],"award-info":[{"award-number":["1337281","1406355"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1618425"],"award-info":[{"award-number":["1618425"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-16-2-0004","FA8650-15-C-7563"],"award-info":[{"award-number":["FA8750-16-2-0004","FA8650-15-C-7563"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Engineering with Computers"],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we propose parallel graph-grammar-based algorithm for the longest-edge refinements and the pollution simulations in Lesser Poland area. We introduce graph-grammar productions for Rivara\u2019s longest-edged algorithm for the local refinement of unstructured triangular meshes. We utilize the hyper-graph to represent the computational mesh and the graph-grammar productions to express the longest-edge mesh refinement algorithm. The parallelism in the original Rivara\u2019s longest edge refinement algorithm is obtained by processing different longest edge refinement paths in different three ads. Our graph-grammar-based algorithm allows for additional parallelization within a single longest-edge refinement path. The graph-grammar-based algorithm automatically guarantees the validity and conformity of the generated mesh; it prevents the generation of duplicated nodes and edges, elongated elements with Jacobians converging to zero, and removes all the hanging nodes automatically from the mesh. We test the algorithm on generating a surface mesh based on a topographic data of Lesser Poland area. The graph-grammar productions also generate the layers of prismatic three-dimensional elements on top of the triangular mesh, and they break each prismatic element into three tetrahedral elements. Next, we propose graph-grammar productions generating element matrices and right-hand-side vectors for each tetrahedral element. We utilize the Streamline Upwind Petrov\u2013Galerkin (SUPG) stabilization for the pollution propagation simulations in Lesser Poland area. We use the advection\u2013diffusion-reaction model, the Crank\u2013Nicolson time integration scheme, and the graph-grammar-based interface to the GMRES solver.<\/jats:p>","DOI":"10.1007\/s00366-020-01253-y","type":"journal-article","created":{"date-parts":[[2021,1,22]],"date-time":"2021-01-22T12:10:04Z","timestamp":1611317404000},"page":"3857-3880","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Parallel graph-grammar-based algorithm for the longest-edge refinement of triangular meshes and the pollution simulations in Lesser Poland area"],"prefix":"10.1007","volume":"37","author":[{"given":"Krzysztof","family":"Podsiad\u0142o","sequence":"first","affiliation":[]},{"given":"Albert Oliver","family":"Serra","sequence":"additional","affiliation":[]},{"given":"Anna","family":"Paszy\u0144ska","sequence":"additional","affiliation":[]},{"given":"Rafael","family":"Montenegro","sequence":"additional","affiliation":[]},{"given":"Ian","family":"Henriksen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7766-6052","authenticated-orcid":false,"given":"Maciej","family":"Paszy\u0144ski","sequence":"additional","affiliation":[]},{"given":"Keshav","family":"Pingali","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,22]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"European Environment Agency, Air Quality in Europe - 2017 report","key":"1253_CR1","DOI":"10.21820\/23987073.2017.1.61"},{"doi-asserted-by":"crossref","unstructured":"Andrew A, Nguyen D, Pingali K (2015) Priority queues are not good concurrent priority schedulers. European Conference on Parallel Processing, Springer, Berlin, Heidelberg 209\u2013221","key":"1253_CR2","DOI":"10.1007\/978-3-662-48096-0_17"},{"key":"1253_CR3","volume-title":"Finite elements: computational aspects","author":"GF Carey","year":"1984","unstructured":"Carey GF, Oden JT (1984) Finite elements: computational aspects. Prentice-Hall, Upper Saddle River"},{"unstructured":"Demkowicz L (2006) Computing with hp-Adaptive Finite Elements, vol I. Chapman & Hall \/ CRC Applied Mathematics & Nonlinear Science, One and Two Dimensional Elliptic and Maxwell Problems","key":"1253_CR4"},{"doi-asserted-by":"crossref","unstructured":"Demkowicz L, Kurtz J, Pardo D, Paszy\u0144ski M, Rachowicz W, Zdunek A (2007) Computing with hp-Adaptive Finite Elements, Vol. II. Frontiers: Three Dimensional Elliptic and Maxwell Problems with Applications, Chapman & Hall \/ CRC Applied Mathematics & Nonlinear Science","key":"1253_CR5","DOI":"10.1201\/9781420011692"},{"doi-asserted-by":"crossref","unstructured":"Farr TG, Rosen PA, Caro E, Crippen R, Duren R, Hensley S, Kobrick M, Paller M, Rodriguez E, Roth L, Seal D, Shaffer S, Shimada J, Umland J, Werner M, Oskin M, Burbank D, Alsdorf D (2005) The Shuttle Radar Topography Mission, Reviews of Geophysics 45(2) https:\/\/agupubs.onlinelibrary.wiley.com\/doi\/pdf \/10.1029\/2005RG000183.","key":"1253_CR6","DOI":"10.1029\/2005RG000183"},{"key":"1253_CR7","first-page":"191","volume":"3","author":"M Flasi\u0144ski","year":"1996","unstructured":"Flasi\u0144ski M, Schaefer R (1996) Quasi context sensitive graph grammars as a formal model of FE mesh generation. Comput Assist Mech Eng Sci 3:191\u2013203","journal-title":"Comput Assist Mech Eng Sci"},{"unstructured":"Galois Framework. http:\/\/iss.ices.utexas.edu\/?p=projects\/galois","key":"1253_CR8"},{"issue":"11","key":"1253_CR9","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1002\/nme.2579","volume":"79","author":"C Geuzaine","year":"2009","unstructured":"Geuzaine C, Remacle J-F (2009) GMSH: a three-dimensional finite element mesh generator with built-in pre- and post-processing facilities. Int J Numer Meth Eng 79(11):1309\u20131331","journal-title":"Int J Numer Meth Eng"},{"key":"1253_CR10","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1016\/j.procs.2014.05.086","volume":"29","author":"D Goik","year":"2014","unstructured":"Goik D, Jopek K, Paszy\u0144ski M, Lenharth A, Nguyen D, Pingali K (2014) Graph grammar based multi-thread multi-frontal direct solver with Galois scheduler. Proc Comput Sci 29:960\u2013969","journal-title":"Proc Comput Sci"},{"issue":"1","key":"1253_CR11","first-page":"3","volume":"2","author":"E Grabska","year":"1993","unstructured":"Grabska E (1993a) Theoretical concepts of graphical modeling. Part one: realization of CP-graphs. Mach Graph Vis 2(1):3\u201338","journal-title":"Mach Graph Vis"},{"issue":"2","key":"1253_CR12","first-page":"149","volume":"2","author":"E Grabska","year":"1993","unstructured":"Grabska E (1993) Theoretical concepts of graphical modeling. Part two: CP-graph grammars and languages. Mach Graph Vis 2(2):149\u2013178","journal-title":"Mach Graph Vis"},{"key":"1253_CR13","first-page":"81","volume":"5","author":"E Grabska","year":"1993","unstructured":"Grabska E, Hliniak G (1993) Structural aspects of CP-graph languages. Schedae Informaticae 5:81\u2013100","journal-title":"Schedae Informaticae"},{"doi-asserted-by":"crossref","unstructured":"Hassaan MA, Burtscher M, Pingali K (2011) Ordered vs. Unordered: A comparison of parallelism and work-efficiency in irregular algorithms, Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, PPoPP \u201911","key":"1253_CR14","DOI":"10.1145\/1941553.1941557"},{"key":"1253_CR15","first-page":"5","volume":"291","author":"A Habel","year":"1987","unstructured":"Habel A, Kreowski HJ (1987) May we introduce to you: hyperedge replacement. Lect Notes Comput Sci 291:5\u201326","journal-title":"Lect Notes Comput Sci"},{"key":"1253_CR16","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/BFb0039608","volume":"247","author":"A Habel","year":"1987","unstructured":"Habel A, Kreowski HJ (1987) Some structural aspects of hypergraph languages generated by hyperedge replacement. Lect Notes Comput Sci 247:207\u2013219","journal-title":"Lect Notes Comput Sci"},{"issue":"9","key":"1253_CR17","doi-asserted-by":"publisher","first-page":"2218","DOI":"10.1016\/j.apnum.2008.12.011","volume":"59","author":"MC Rivara","year":"2009","unstructured":"Rivara MC (2009) Lepp-bisection algorithms, applications and mathematical properties. Appl Numer Math 59(9):2218\u20132235","journal-title":"Appl Numer Math"},{"issue":"4","key":"1253_CR18","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/j.apnum.2011.07.011","volume":"62","author":"MC Rivara","year":"2012","unstructured":"Rivara MC, Rodriguez P, Montenegro R, Jorquera G (2012) Multithread parallelization of Lepp-bisection algorithms. Appl Numer Math 62(4):473\u2013488","journal-title":"Appl Numer Math"},{"issue":"1","key":"1253_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3329872","volume":"24","author":"T Heuer","year":"2019","unstructured":"Heuer T, Sanders PG, Schlag S (2019) Network flow-based refinement for multilevel hypergraph partitioning. J Exp Algorithmics 24(1):1\u201336","journal-title":"J Exp Algorithmics"},{"key":"1253_CR20","doi-asserted-by":"publisher","first-page":"3313","DOI":"10.1002\/(SICI)1097-0207(19970930)40:18<3313::AID-NME214>3.0.CO;2-#","volume":"40","author":"M-C Rivara","year":"1997","unstructured":"Rivara M-C (1997) New longest-edge algorithms for the refinement and\/or improvement of unstructured triangulations. Int J Numer Meth Eng 40:3313\u20133324","journal-title":"Int J Numer Meth Eng"},{"key":"1253_CR21","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0045-7825(87)90125-3","volume":"6","author":"TJR Hughes","year":"1987","unstructured":"Hughes TJR, Franca LP, Mallet M (1987) A new finite element formulation for fluid dynamics: VI. Convergence analysis of the generalized SUPG formulation for linear time-dependent multidimensional advective-diffusive systems. Comput Methods Appl Mech Eng 6:97\u2013112","journal-title":"Comput Methods Appl Mech Eng"},{"unstructured":"Karypis G, Kumar V (1998) hMETIS 1.5: A Hypergraph Partitioning Package. Technical Report, Department of Computer Science, University of Minnesota","key":"1253_CR22"},{"issue":"3","key":"1253_CR23","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0377-0427(94)90034-5","volume":"55","author":"I Kossaczk\u00fd","year":"1994","unstructured":"Kossaczk\u00fd I (1994) A recursive approach to local mesh refinement in two and three dimensions. J Comput Appl Math 55(3):275\u2013288","journal-title":"J Comput Appl Math"},{"issue":"6","key":"1253_CR24","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1145\/1273442.1250759","volume":"42","author":"M Kulkarni","year":"2007","unstructured":"Kulkarni M, Pingali K, Walter B, Ramanarayanan G, Bala K, Kavita Chew LP (2007) Optimistic parallelism requires abstractions. ACM SIGPLAN Notices 42(6):211\u2013222","journal-title":"ACM SIGPLAN Notices"},{"key":"1253_CR25","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.energy.2012.10.051","volume":"49","author":"A Oliver","year":"2013","unstructured":"Oliver A, Montero G, Montenegro R, Rodr\u00edguez E, Escobar JM, P\u00e9rez-Foguet A (2013) Adaptive finite element simulation of stack pollutant emissions over complex terrain. Energy 49:47\u201360","journal-title":"Energy"},{"doi-asserted-by":"crossref","unstructured":"Papa DA, Markov IL (2007)Hypergraph partitioning and clustering. Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics, chapter 61 (2007) 61-1\u201361-19, CRC Press, Boca Raton","key":"1253_CR26","DOI":"10.1201\/9781420010749.ch61"},{"key":"1253_CR27","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.1007\/978-3-540-68111-3_139","volume":"4967","author":"M Paszy\u0144ski","year":"2008","unstructured":"Paszy\u0144ski M, Paszy\u0144ska A (2008) Graph transformations for modeling parallel $$hp$$-adaptive finite element method. Lect Notes Comput Sci 4967:1313\u20131322","journal-title":"Lect Notes Comput Sci"},{"key":"1253_CR28","first-page":"864","volume":"5545","author":"M Paszy\u0144ski","year":"2009","unstructured":"Paszy\u0144ski M, Paszy\u0144ska A, Grabska E (2009) Graph transformations for modeling hp-adaptive finite element method with mixed triangular and rectangular elements. Lect Notes Comput Sci 5545:864\u2013875","journal-title":"Lect Notes Comput Sci"},{"key":"1253_CR29","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1007\/978-3-540-69389-5_68","volume":"5103","author":"M Paszy\u0144ski","year":"2008","unstructured":"Paszy\u0144ski M, Paszy\u0144ska A, Grabska E (2008) Graph transformations for modeling hp-adaptive Finite Element Method with triangular elements. Lect Notes Comput Sci 5103:604\u2013613","journal-title":"Lect Notes Comput Sci"},{"doi-asserted-by":"crossref","unstructured":"Pingali K, Nguyen D, Kulkarni M, Burtscher M, Hassaan MA, Kaleem R, Lee TH, Lenharth A, Manevich R, Mendez-Lojo M, Prountzos D, Sui X (2011) The tao of parallelism in algorithms, in Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation 12-25","key":"1253_CR30","DOI":"10.1145\/1993316.1993501"},{"issue":"4","key":"1253_CR31","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1002\/nme.1620200412","volume":"20","author":"MC Rivara","year":"1984","unstructured":"Rivara MC (1984) Algorithms for refining triangular grids suitable for adaptive and multigrid techniques. Int J Numer Meth Eng 20(4):745\u2013756","journal-title":"Int J Numer Meth Eng"},{"issue":"3","key":"1253_CR32","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1137\/0721042","volume":"21","author":"MC Rivara","year":"1984","unstructured":"Rivara MC (1984) Mesh refinement processes based on the generalized bisection of simplices. SIAM J Numer Anal 21(3):604\u2013613","journal-title":"SIAM J Numer Anal"},{"unstructured":"Calo VM (2005) Residual-based multiscale turbulence modeling: Finite volume simulations of bypass transition, Stanford University, Ph.D. Thesis","key":"1253_CR33"},{"unstructured":"Paszy\u0144ski M (2020) Klasyczna i izogeometryczna metoda element\u00f3w sko\u0144czonych, AGH University, https:\/\/epodreczniki.open.agh.edu.pl\/openagh-podreczniki\\_view.php?categId=97&handbookId=77","key":"1253_CR34"},{"key":"1253_CR35","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-030-50371-0_8","volume":"12137","author":"M Paszy\u0144ski","year":"2020","unstructured":"Paszy\u0144ski M, Siwik L, Podsiad\u0142o K, Minev P (2020) A massively parallel algorithm for the three-dimensional Navier-Stokes-Boussinesq simulations of the atmospheric phenomena. Lect Notes Comput Sci 12137:102\u2013117","journal-title":"Lect Notes Comput Sci"}],"container-title":["Engineering with Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00366-020-01253-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00366-020-01253-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00366-020-01253-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T12:06:04Z","timestamp":1631534764000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00366-020-01253-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,22]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["1253"],"URL":"https:\/\/doi.org\/10.1007\/s00366-020-01253-y","relation":{},"ISSN":["0177-0667","1435-5663"],"issn-type":[{"type":"print","value":"0177-0667"},{"type":"electronic","value":"1435-5663"}],"subject":[],"published":{"date-parts":[[2021,1,22]]},"assertion":[{"value":"4 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}