{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T13:57:36Z","timestamp":1776866256768,"version":"3.51.2"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,6,26]],"date-time":"2021-06-26T00:00:00Z","timestamp":1624665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/N032861\/1"],"award-info":[{"award-number":["EP\/N032861\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"crossref","award":["DE-AC02-06CH11357"],"award-info":[{"award-number":["DE-AC02-06CH11357"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/R029423\/1, EP\/V001493\/1, and EP\/L015803\/1"],"award-info":[{"award-number":["EP\/R029423\/1, EP\/V001493\/1, and EP\/L015803\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>Effective relaxation methods are necessary for good multigrid convergence. For many equations, standard Jacobi and Gau\u00df\u2013Seidel are inadequate, and more sophisticated space decompositions are required; examples include problems with semidefinite terms or saddle point structure. In this article, we present a unifying software abstraction, PCPATCH, for the topological construction of space decompositions for multigrid relaxation methods. Space decompositions are specified by collecting topological entities in a mesh (such as all vertices or faces) and applying a construction rule (such as taking all degrees of freedom in the cells around each entity). The software is implemented in PETSc and facilitates the elegant expression of a wide range of schemes merely by varying solver options at runtime. In turn, this allows for the very rapid development of fast solvers for difficult problems.<\/jats:p>","DOI":"10.1145\/3445791","type":"journal-article","created":{"date-parts":[[2021,6,26]],"date-time":"2021-06-26T16:14:12Z","timestamp":1624724052000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["PCPATCH"],"prefix":"10.1145","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1241-7060","authenticated-orcid":false,"given":"Patrick E.","family":"Farrell","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2292-0735","authenticated-orcid":false,"given":"Matthew G.","family":"Knepley","sequence":"additional","affiliation":[{"name":"University at Buffalo, Buffalo, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8062-1453","authenticated-orcid":false,"given":"Lawrence","family":"Mitchell","sequence":"additional","affiliation":[{"name":"Durham University, Durham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Wechsung","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-97-00826-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00005386"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492906210018"},{"key":"e_1_2_1_4_1","volume-title":"Richard Tran Mills, Todd Munson, Karl Rupp, Patrick Sanan, Barry F. Smith, Stefano Zampini, Hong Zhang, and Hong Zhang.","author":"Balay Satish","year":"2019","unstructured":"Satish Balay , Shrirang Abhyankar , Mark F. Adams , Jed Brown , Peter Brune , Kris Buschelman , Lisandro Dalcin , Victor Eijkhout , William D. Gropp , Dmitry Karpeyev , Dinesh Kaushik , Matthew G. Knepley , Dave A. May , Lois Curfman McInnes , Richard Tran Mills, Todd Munson, Karl Rupp, Patrick Sanan, Barry F. Smith, Stefano Zampini, Hong Zhang, and Hong Zhang. 2019 . PETSc Users Manual. Technical Report ANL-95\/11 - Revision 3.12. Argonne National Laboratory . Satish Balay, Shrirang Abhyankar, Mark F. Adams, Jed Brown, Peter Brune, Kris Buschelman, Lisandro Dalcin, Victor Eijkhout, William D. Gropp, Dmitry Karpeyev, Dinesh Kaushik, Matthew G. Knepley, Dave A. May, Lois Curfman McInnes, Richard Tran Mills, Todd Munson, Karl Rupp, Patrick Sanan, Barry F. Smith, Stefano Zampini, Hong Zhang, and Hong Zhang. 2019. PETSc Users Manual. Technical Report ANL-95\/11 - Revision 3.12. Argonne National Laboratory."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1268776.1268779"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1816"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2019.06.001"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646421"},{"key":"e_1_2_1_9_1","first-page":"13","article-title":"The distributed and unified numerics environment, version 2.4","volume":"4","author":"Blatt Markus","year":"2016","unstructured":"Markus Blatt , Ansgar Burchardt , Andreas Dedner , Christian Engwer , Jorrit Fahlke , Bernd Flemisch , Christoph Gersbacher , Carsten Gr\u00e4ser , Felix Gruber , Christoph Gr\u00fcninger , Dominic Kempf , Robert Kl\u00f6fkorn , Tobias Malkmus , Steffen M\u00fcthing , Martin Nolte , Marian Piatkowski , and Oliver Sander . 2016 . The distributed and unified numerics environment, version 2.4 . Archive Numer. Softw. 4 , 100 (2016), 13 \u2013 29 . DOI:https:\/\/doi.org\/10.11588\/ans.2016.100.26526 Markus Blatt, Ansgar Burchardt, Andreas Dedner, Christian Engwer, Jorrit Fahlke, Bernd Flemisch, Christoph Gersbacher, Carsten Gr\u00e4ser, Felix Gruber, Christoph Gr\u00fcninger, Dominic Kempf, Robert Kl\u00f6fkorn, Tobias Malkmus, Steffen M\u00fcthing, Martin Nolte, Marian Piatkowski, and Oliver Sander. 2016. The distributed and unified numerics environment, version 2.4. Archive Numer. Softw. 4, 100 (2016), 13\u201329. DOI:https:\/\/doi.org\/10.11588\/ans.2016.100.26526","journal-title":"Archive Numer. Softw."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050234"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2014.11.002"},{"key":"e_1_2_1_12_1","volume-title":"Livne","author":"Brandt Achi","year":"2011","unstructured":"Achi Brandt and Oren E . Livne . 2011 . Multigrid Techniques: 1984 Guide with Applications to Fluid Dynamics (2nd ed.). Classics in Applied Mathematics, Vol. 67 . SIAM. Achi Brandt and Oren E. Livne. 2011. Multigrid Techniques: 1984 Guide with Applications to Fluid Dynamics (2nd ed.). Classics in Applied Mathematics, Vol. 67. SIAM."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/130936725"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S106482750037620X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900002427"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Victorita Dolean Pierre Jolivet and Fr\u00e9d\u00e9ric Nataf. 2015. An Introduction to Domain Decomposition Methods. SIAM. DOI:https:\/\/doi.org\/10.1137\/1.9781611974065  Victorita Dolean Pierre Jolivet and Fr\u00e9d\u00e9ric Nataf. 2015. An Introduction to Domain Decomposition Methods. SIAM. DOI:https:\/\/doi.org\/10.1137\/1.9781611974065","DOI":"10.1137\/1.9781611974065"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02510214"},{"key":"e_1_2_1_18_1","volume-title":"Wathen","author":"Elman Howard C.","year":"2014","unstructured":"Howard C. Elman , David J. Silvester , and Andrew J . Wathen . 2014 . Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics (2nd ed.). Oxford University Press . Howard C. Elman, David J. Silvester, and Andrew J. Wathen. 2014. Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics (2nd ed.). Oxford University Press."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1219370"},{"key":"e_1_2_1_20_1","unstructured":"Firedrake-Zenodo. 2019. Software used in \u201cPCPATCH: Software for the topological construction of multigrid relaxation methods.\u201d DOI:https:\/\/doi.org\/10.5281\/ZENODO.3552611  Firedrake-Zenodo. 2019. Software used in \u201cPCPATCH: Software for the topological construction of multigrid relaxation methods.\u201d DOI:https:\/\/doi.org\/10.5281\/ZENODO.3552611"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1997.5651"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142903425409"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1332748"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1515\/jnum-2012-0013"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089014.1089021"},{"key":"e_1_2_1_26_1","volume-title":"Ham","author":"Homolya Mikl\u00f3s","year":"2017","unstructured":"Mikl\u00f3s Homolya , Robert C. Kirby , and David A . Ham . 2017 . Exposing and exploiting structure: Optimal code generation for high-order finite element methods. arxiv:1711.02473 (2017). Mikl\u00f3s Homolya, Robert C. Kirby, and David A. Ham. 2017. Exposing and exploiting structure: Optimal code generation for high-order finite element methods. arxiv:1711.02473 (2017)."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503212"},{"key":"e_1_2_1_28_1","volume-title":"Sherwin","author":"Karniadakis George E.","year":"2005","unstructured":"George E. Karniadakis and Spencer J . Sherwin . 2005 . Spectral\/ Element Methods for Computational Fluid Dynamics (2nd ed.). Oxford University Press . George E. Karniadakis and Spencer J. Sherwin. 2005. Spectral\/ Element Methods for Computational Fluid Dynamics (2nd ed.). Oxford University Press."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1155\/2009\/948613"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 3rd International Conference on Exascale Applications and Software (EASC\u201915)","author":"Lange Michael","year":"2008","unstructured":"Michael Lange , Matthew G. Knepley , and Gerard J. Gorman . 2015. Flexible, scalable mesh and data management using PETSc DMPlex . In Proceedings of the 3rd International Conference on Exascale Applications and Software (EASC\u201915) . University of Edinburgh, Edinburgh, Scotland, UK, 71\u201376. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=28 2008 3.2820097. Michael Lange, Matthew G. Knepley, and Gerard J. Gorman. 2015. Flexible, scalable mesh and data management using PETSc DMPlex. In Proceedings of the 3rd International Conference on Exascale Applications and Software (EASC\u201915). University of Edinburgh, Edinburgh, Scotland, UK, 71\u201376. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=2820083.2820097."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218202507002522"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1731022.1731030"},{"key":"e_1_2_1_34_1","volume-title":"Lecture Notes in Computational Science and Engineering","volume":"84","author":"Logg Anders","year":"2012","unstructured":"Anders Logg , Garth N. Wells , and Johan Hake . 2012 . DOLFIN: A C++\/Python finite element library. In Automated Solution of Differential Equations by the Finite Element Method, Anders Logg, Kent-Andre Mardal, and Garth Wells (Eds.) . Lecture Notes in Computational Science and Engineering , Vol. 84 . Springer Berlin, 173\u2013225. DOI:https:\/\/doi.org\/10.1007\/978-3-642-23099-8_10 Anders Logg, Garth N. Wells, and Johan Hake. 2012. DOLFIN: A C++\/Python finite element library. In Automated Solution of Differential Equations by the Finite Element Method, Anders Logg, Kent-Andre Mardal, and Garth Wells (Eds.). Lecture Notes in Computational Science and Engineering, Vol. 84. Springer Berlin, 173\u2013225. DOI:https:\/\/doi.org\/10.1007\/978-3-642-23099-8_10"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.762"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.716"},{"key":"e_1_2_1_37_1","first-page":"736","article-title":"A nodal basis for piecewise polynomials of degree","volume":"29","author":"Morgan John","year":"1975","unstructured":"John Morgan and L. Ridgway Scott . 1975 . A nodal basis for piecewise polynomials of degree . Math. Comput. 29 , 131 (1975), 736 . DOI:https:\/\/doi.org\/10.2307\/2005284 John Morgan and L. Ridgway Scott. 1975. A nodal basis for piecewise polynomials of degree . Math. Comput. 29, 131 (1975), 736. DOI:https:\/\/doi.org\/10.2307\/2005284","journal-title":"Math. Comput."},{"key":"e_1_2_1_38_1","volume-title":"Elements of Algebraic Topology","author":"Munkres James R.","unstructured":"James R. Munkres . 1984. Elements of Algebraic Topology . CRC Press . James R. Munkres. 1984. Elements of Algebraic Topology. CRC Press."},{"key":"e_1_2_1_39_1","unstructured":"NGSolve 2017. Building blocks for programming preconditioners. Retrieved from https:\/\/ngsolve.org\/docu\/latest\/i-tutorials\/unit-2.1.2-blockjacobi\/blockjacobi.html#A-Block-Jacobi-preconditioner.  NGSolve 2017. Building blocks for programming preconditioners. Retrieved from https:\/\/ngsolve.org\/docu\/latest\/i-tutorials\/unit-2.1.2-blockjacobi\/blockjacobi.html#A-Block-Jacobi-preconditioner."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598338093"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2020.109844"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01385709"},{"key":"e_1_2_1_43_1","article-title":"Firedrake: Automating the finite element method by composing abstractions","volume":"43","author":"Rathgeber Florian","year":"2016","unstructured":"Florian Rathgeber , David A. Ham , Lawrence Mitchell , Michael Lange , Fabio Luporini , Andrew T. T. McRae , Gheorghe-Teodor Bercea , Graham R. Markall , and Paul H. J. Kelly . 2016 . Firedrake: Automating the finite element method by composing abstractions . ACM Trans. Math. Softw. 43 , 3 (2016), 24:1\u201324:27. DOI:https:\/\/doi.org\/10.1145\/2998441 Florian Rathgeber, David A. Ham, Lawrence Mitchell, Michael Lange, Fabio Luporini, Andrew T. T. McRae, Gheorghe-Teodor Bercea, Graham R. Markall, and Paul H. J. Kelly. 2016. Firedrake: Automating the finite element method by composing abstractions. ACM Trans. Math. Softw. 43, 3 (2016), 24:1\u201324:27. DOI:https:\/\/doi.org\/10.1145\/2998441","journal-title":"ACM Trans. Math. Softw."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050465"},{"key":"e_1_2_1_46_1","volume-title":"Technical Report ASC Report 30\/2014","author":"Sch\u00f6berl Joachim","unstructured":"Joachim Sch\u00f6berl . 2014. C++ Implementation of Finite Elements in NG Solve . Technical Report ASC Report 30\/2014 . Vienna University of Technology . Joachim Sch\u00f6berl. 2014. C++ Implementation of Finite Elements in NGSolve. Technical Report ASC Report 30\/2014. Vienna University of Technology."},{"key":"e_1_2_1_47_1","volume-title":"Gropp","author":"Smith Barry F.","year":"1996","unstructured":"Barry F. Smith , Petter Bjorstad , and William D . Gropp . 1996 . Domain Decomposition : Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press . Barry F. Smith, Petter Bjorstad, and William D. Gropp. 1996. Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press."},{"key":"e_1_2_1_48_1","volume-title":"Widlund","author":"Toselli Andrea","year":"2005","unstructured":"Andrea Toselli and Olof B . Widlund . 2005 . Domain Decomposition Methods \u2014 Algorithms and Theory. Springer Berlin . DOI:https:\/\/doi.org\/10.1007\/b137868 Andrea Toselli and Olof B. Widlund. 2005. Domain Decomposition Methods \u2014 Algorithms and Theory. Springer Berlin. DOI:https:\/\/doi.org\/10.1007\/b137868"},{"key":"e_1_2_1_49_1","volume-title":"Efficient Solvers for Incompressible Flow Problems: An Algorithmic and Computational Approach","author":"Turek Stefan","unstructured":"Stefan Turek . 1999. Efficient Solvers for Incompressible Flow Problems: An Algorithmic and Computational Approach . Springer . Stefan Turek. 1999. Efficient Solvers for Incompressible Flow Problems: An Algorithmic and Computational Approach. Springer."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(86)90008-2"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/1034116"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00518-5"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1025785"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3445791","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3445791","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3445791","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:13Z","timestamp":1750195693000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3445791"}},"subtitle":["Software for the Topological Construction of Multigrid Relaxation Methods"],"short-title":[],"issued":{"date-parts":[[2021,6,26]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3445791"],"URL":"https:\/\/doi.org\/10.1145\/3445791","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,26]]},"assertion":[{"value":"2019-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}