{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T14:02:53Z","timestamp":1750428173720,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T00:00:00Z","timestamp":1630627200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T00:00:00Z","timestamp":1630627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001652","name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001652","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Genet Program Evolvable Mach"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For many systems of linear equations that arise from the discretization of partial differential equations, the construction of an efficient multigrid solver is challenging. Here we present EvoStencils, a novel approach for optimizing geometric multigrid methods with grammar-guided genetic programming, a stochastic program optimization technique inspired by the principle of natural evolution. A multigrid solver is represented as a tree of mathematical expressions that we generate based on a formal grammar. The quality of each solver is evaluated in terms of convergence and compute performance by automatically generating an optimized implementation using code generation that is then executed on the target platform to measure all relevant performance metrics. Based on this, a multi-objective optimization is performed using a non-dominated sorting-based selection. To evaluate a large number of solvers in parallel, they are distributed to multiple compute nodes. We demonstrate the effectiveness of our implementation by constructing geometric multigrid solvers that are able to outperform hand-crafted methods for Poisson\u2019s equation and a linear elastic boundary value problem with up to 16 million unknowns on multi-core processors with Ivy Bridge and Broadwell microarchitecture.<\/jats:p>","DOI":"10.1007\/s10710-021-09412-w","type":"journal-article","created":{"date-parts":[[2021,9,4]],"date-time":"2021-09-04T00:55:55Z","timestamp":1630716955000},"page":"511-537","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["EvoStencils: a grammar-based genetic programming approach for constructing efficient geometric multigrid methods"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8891-0046","authenticated-orcid":false,"given":"Jonas","family":"Schmitt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Kuckuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harald","family":"K\u00f6stler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,3]]},"reference":[{"key":"9412_CR1","doi-asserted-by":"publisher","DOI":"10.1201\/9780367802486","volume-title":"Handbook of Evolutionary Computation","author":"T Back","year":"1997","unstructured":"T. Back, D.B. Fogel, Z. Michalewicz, Handbook of Evolutionary Computation, 1st edn. (IOP Publishing Ltd., GBR, Bristol, 1997)","edition":"1"},{"key":"9412_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0962492904000212","volume":"14","author":"M Benzi","year":"2005","unstructured":"M. Benzi, G.H. Golub, J. Liesen, Numerical solution of saddle point problems. Acta Numer. 14, 1\u2013137 (2005)","journal-title":"Acta Numer."},{"issue":"1","key":"9412_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1023\/A:1015059928466","volume":"1","author":"HG Beyer","year":"2002","unstructured":"H.G. Beyer, H.P. Schwefel, Evolution strategies - a comprehensive introduction. Nat. Comput. 1(1), 3\u201352 (2002)","journal-title":"Nat. Comput."},{"issue":"138","key":"9412_CR4","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1090\/S0025-5718-1977-0431719-X","volume":"31","author":"A Brandt","year":"1977","unstructured":"A. Brandt, Multi-level adaptive solutions to boundary-value problems. Math. Comput. 31(138), 333\u2013390 (1977)","journal-title":"Math. Comput."},{"key":"9412_CR5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719505","volume-title":"A multigrid tutorial","author":"WL Briggs","year":"2000","unstructured":"W.L. Briggs, V. E. Henson, S.F. McCormick, A multigrid tutorial, 2nd esdn, (Society for Industrial and Applied Mathematics, Philadelphia, 2000)","edition":"2"},{"issue":"1","key":"9412_CR6","doi-asserted-by":"publisher","first-page":"A109","DOI":"10.1137\/19M1308669","volume":"43","author":"J Brown","year":"2021","unstructured":"J. Brown, Y. He, S. MacLachlan, M. Menickelly, S.M. Wild, Tuning multigrid methods with robust optimization and local fourier analysis. SIAM J. Sci. Comput. 43(1), A109\u2013A138 (2021). https:\/\/doi.org\/10.1137\/19M1308669","journal-title":"SIAM J. Sci. Comput."},{"key":"9412_CR7","volume-title":"Evolutionary Algorithms for Solving Multi-Objective Problems","author":"CAC Coello","year":"2007","unstructured":"C.A.C. Coello, G.B. Lamont, D.A. Van Veldhuizen et al., Evolutionary Algorithms for Solving Multi-Objective Problems, vol. 5 (Springer-Verlag, New York, 2007)"},{"key":"9412_CR8","doi-asserted-by":"publisher","unstructured":"K. Deb, S. Agrawal, A. Pratap, T. Meyarivan, A fast elitist non-dominated sorting genetic algorithm for multi-objective optimisation: Nsga-ii. In: Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, PPSN VI, (Springer-Verlag, Berlin, Heidelberg, 2000), p. 849\u2013858. https:\/\/doi.org\/10.1007\/3-540-45356-3_83","DOI":"10.1007\/3-540-45356-3_83"},{"issue":"1","key":"9412_CR9","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00211-007-0114-x","volume":"108","author":"J Demmel","year":"2007","unstructured":"J. Demmel, I. Dumitriu, O. Holtz, Fast linear algebra is stable. Numer. Math. 108(1), 59\u201391 (2007). https:\/\/doi.org\/10.1007\/s00211-007-0114-x","journal-title":"Numer. Math."},{"issue":"4","key":"9412_CR10","doi-asserted-by":"publisher","first-page":"1471","DOI":"10.1137\/040615195","volume":"27","author":"YA Erlangga","year":"2006","unstructured":"Y.A. Erlangga, C.W. Oosterlee, C. Vuik, A novel multigrid based preconditioner for heterogeneous helmholtz problems. SIAM J. Sci. Comput. 27(4), 1471\u20131492 (2006)","journal-title":"SIAM J. Sci. Comput."},{"key":"9412_CR11","doi-asserted-by":"publisher","unstructured":"O.G. Ernst, M.J. Gander, Why it is Difficult to Solve Helmholtz Problems with Classical Iterative Methods. In: I.G. Graham, T. Hou, O. Lakkis, R. Scheichl (eds.) Numerical Analysis of Multiscale Problems (Springer, Berlin, Heidelberg, 2012), p. 325\u2013363. https:\/\/doi.org\/10.1007\/978-3-642-22061-6_10","DOI":"10.1007\/978-3-642-22061-6_10"},{"issue":"5","key":"9412_CR12","first-page":"922","volume":"1","author":"RP Fedorenko","year":"1961","unstructured":"R.P. Fedorenko, A relaxation method for solving elliptic difference equations. Zhurnal Vychislitel\u2019noi Mat. Mat. Fiziki 1(5), 922\u2013927 (1961)","journal-title":"Zhurnal Vychislitel\u2019noi Mat. Mat. Fiziki"},{"key":"9412_CR13","first-page":"2171","volume":"13","author":"FA Fortin","year":"2012","unstructured":"F.A. Fortin, F.M. De Rainville, M.A. Gardner, M. Parizeau, C. Gagn\u00e9, DEAP: Evolutionary algorithms made easy. J. Mach. Learn. Res. 13, 2171\u20132175 (2012)","journal-title":"J. Mach. Learn. Res."},{"key":"9412_CR14","doi-asserted-by":"publisher","unstructured":"F.A. Fortin, S. Grenier, M. Parizeau, Generalizing the improved run-time complexity algorithm for non-dominated sorting. In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, GECCO \u201913, (Association for Computing Machinery, New York, NY, USA, 2013), p. 615\u2013622. https:\/\/doi.org\/10.1145\/2463372.2463454","DOI":"10.1145\/2463372.2463454"},{"key":"9412_CR15","unstructured":"D. Greenfeld, M. Galun, R. Basri, I. Yavneh, R. Kimmel, Learning to optimize multigrid pde solvers. In: International Conference on Machine Learning, 2415\u20132423 (2019)"},{"key":"9412_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02427-0","volume-title":"Multi-Grid Methods and Applications","author":"W Hackbusch","year":"1985","unstructured":"W. Hackbusch, Multi-Grid Methods and Applications (Springer-Verlag, New York, 1985)"},{"issue":"2","key":"9412_CR17","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1162\/106365601750190398","volume":"9","author":"N Hansen","year":"2001","unstructured":"N. Hansen, A. Ostermeier, Completely derandomized self-adaptation in evolution strategies. Evol. Comput. 9(2), 159\u2013195 (2001). https:\/\/doi.org\/10.1162\/106365601750190398","journal-title":"Evol. Comput."},{"key":"9412_CR18","volume-title":"Nonlinear Solid Mechanics: A Continuum Approach for Engineering","author":"G Holzapfel","year":"2001","unstructured":"G. Holzapfel, Nonlinear Solid Mechanics: A Continuum Approach for Engineering (John Wiley and Sons, Hoboken, 2001)"},{"key":"9412_CR19","unstructured":"J.T. Hsieh, S. Zhao, S. Eismann, L. Mirabella, S. Ermon, Learning neural pde solvers with convergence guarantees. arXiv preprint (2019)"},{"key":"9412_CR20","doi-asserted-by":"crossref","unstructured":"R. Huang, R. Li, Y. Xi, Learning optimal multigrid smoothers via neural networks. arXiv preprint arXiv:2102.12071 (2021)","DOI":"10.1137\/21M1430030"},{"issue":"3","key":"9412_CR21","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1007\/s10543-019-00797-w","volume":"60","author":"K Kahl","year":"2020","unstructured":"K. Kahl, N. Kintscher, Automated local fourier analysis (alfa). BIT Numer. Math. 60(3), 651\u2013686 (2020)","journal-title":"BIT Numer. Math."},{"key":"9412_CR22","doi-asserted-by":"publisher","first-page":"112524","DOI":"10.1016\/j.cam.2019.112524","volume":"368","author":"A Katrutsa","year":"2020","unstructured":"A. Katrutsa, T. Daulbaev, I. Oseledets, Black-box learning of multigrid parameters. J. Comput. Appl. Math. 368, 112524 (2020)","journal-title":"J. Comput. Appl. Math."},{"issue":"2","key":"9412_CR23","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF00175355","volume":"4","author":"JR Koza","year":"1994","unstructured":"J.R. Koza, Genetic programming as a means for programming computers by natural selection. Stat. Comput. 4(2), 87\u2013112 (1994). https:\/\/doi.org\/10.1007\/BF00175355","journal-title":"Stat. Comput."},{"issue":"3\u20134","key":"9412_CR24","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s10710-010-9112-3","volume":"11","author":"JR Koza","year":"2010","unstructured":"J.R. Koza, Human-competitive results produced by genetic programming. Genet. Program. Evolvable Mach. 11(3\u20134), 251\u2013284 (2010). https:\/\/doi.org\/10.1007\/s10710-010-9112-3","journal-title":"Genet. Program. Evolvable Mach."},{"key":"9412_CR25","doi-asserted-by":"crossref","unstructured":"C. Lengauer, S. Apel, M. Bolten, S. Chiba, U. R\u00fcde, J. Teich, A. Gr\u00f6\u00dflinger, F. Hannig, H. K\u00f6stler, L. Claus, et\u00a0al., Exastencils: advanced multigrid solver generation. In: Software for Exascale Computing - SPPEXA 2016\u20132019, (Springer, Cham, 2012), p. 405\u2013452.","DOI":"10.1007\/978-3-030-47956-5_14"},{"issue":"3\u20134","key":"9412_CR26","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10710-010-9109-y","volume":"11","author":"RI Mckay","year":"2010","unstructured":"R.I. Mckay, N.X. Hoai, P.A. Whigham, Y. Shan, M. O\u2019neill, Grammar-based genetic programming: a survey. Genet. Program. Evolvable Mach. 11(3\u20134), 365\u2013396 (2010)","journal-title":"Genet. Program. Evolvable Mach."},{"issue":"3","key":"9412_CR27","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1137\/S1064827501397950","volume":"24","author":"CW Oosterlee","year":"2003","unstructured":"C.W. Oosterlee, R. Wienands, A genetic search for optimal multigrid components within a fourier analysis setting. SIAM J. Sci. Comput. 24(3), 924\u2013944 (2003). https:\/\/doi.org\/10.1137\/S1064827501397950","journal-title":"SIAM J. Sci. Comput."},{"key":"9412_CR28","unstructured":"H. Rittich, Extending and automating fourier analysis for multigrid methods. Ph.D. thesis, University of Wuppertal (2017)"},{"key":"9412_CR29","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003","volume-title":"Iterative Methods for Sparse Linear Systems","author":"Y Saad","year":"2003","unstructured":"Y. Saad, Iterative Methods for Sparse Linear Systems, 2 edn, (Society for Industrial and Applied Mathematics, Philadelphia, 2003)","edition":"2"},{"key":"9412_CR30","doi-asserted-by":"crossref","unstructured":"C. Schmitt, S. Kuckuk, F. Hannig, H. K\u00f6stler, J. Teich, Exaslang: a domain-specific language for highly scalable multigrid solvers. In: 2014 Fourth International Workshop on Domain-Specific Languages and High-Level Frameworks for High Performance Computing, 42\u201351. IEEE (2014)","DOI":"10.1109\/WOLFHPC.2014.11"},{"key":"9412_CR31","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-319-40528-5_3","volume-title":"Software for Exascale Computing-SPPEXA 2013-2015","author":"C Schmitt","year":"2016","unstructured":"C. Schmitt, S. Kuckuk, F. Hannig, J. Teich, H. K\u00f6stler, U. R\u00fcde, C. Lengauer, Systems of partial differential equations in exaslang, in Software for Exascale Computing-SPPEXA 2013-2015. (Springer, New York, 2016), pp. 47\u201367"},{"key":"9412_CR32","doi-asserted-by":"publisher","unstructured":"j. Schmitt, S. Kuckuk, H K\u00f6stler, Constructing efficient multigrid solvers with genetic programming. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO \u201920, 1012\u20131020. (Association for Computing Machinery, New York, NY, USA, 2020). https:\/\/doi.org\/10.1145\/3377930.3389811","DOI":"10.1145\/3377930.3389811"},{"issue":"2\u20133","key":"9412_CR33","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1002\/nla.697","volume":"17","author":"A Thekale","year":"2010","unstructured":"A. Thekale, T. Gradl, K. Klamroth, U. R\u00fcde, Optimizing the number of multigrid cycles in the full multigrid algorithm. Numer. Linear Algebra Appl. 17(2\u20133), 199\u2013210 (2010)","journal-title":"Numer. Linear Algebra Appl."},{"key":"9412_CR34","volume-title":"Multigrid","author":"U Trottenberg","year":"2000","unstructured":"U. Trottenberg, C.W. Oosterlee, A. Schuller, Multigrid (Elsevier, Amsterdam, 2000)"},{"key":"9412_CR35","doi-asserted-by":"publisher","DOI":"10.1201\/9781420034998","volume-title":"Practical Fourier analysis for multigrid methods","author":"R Wienands","year":"2004","unstructured":"R. Wienands, W. Joppich, Practical Fourier Analysis for Multigrid Methods (CRC Press, Florida, 2004)"},{"issue":"4","key":"9412_CR36","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/1498765.1498785","volume":"52","author":"S Williams","year":"2009","unstructured":"S. Williams, A. Waterman, D. Patterson, Roofline: an insightful visual performance model for multicore architectures. Commun. ACM 52(4), 65\u201376 (2009). https:\/\/doi.org\/10.1145\/1498765.1498785","journal-title":"Commun. ACM"}],"container-title":["Genetic Programming and Evolvable Machines"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10710-021-09412-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10710-021-09412-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10710-021-09412-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T16:00:17Z","timestamp":1673193617000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10710-021-09412-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,3]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["9412"],"URL":"https:\/\/doi.org\/10.1007\/s10710-021-09412-w","relation":{},"ISSN":["1389-2576","1573-7632"],"issn-type":[{"type":"print","value":"1389-2576"},{"type":"electronic","value":"1573-7632"}],"subject":[],"published":{"date-parts":[[2021,9,3]]},"assertion":[{"value":"30 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}