{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:42Z","timestamp":1750309362296,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>\n            This article presents a matching algorithm for bipartite graphs containing repetitive structures and represented by intension as\n            <jats:italic>Set-Based Graphs<\/jats:italic>\n            . Under certain conditions on the structure of the graphs, the computational cost of this novel algorithm is not affected by the cardinality of the sets of vertices and edges. The main application of the algorithm is that of matching large Equation-Based Models where provided that most equations are defined using\n            <jats:monospace>for loop<\/jats:monospace>\n            statements that iterate over vectors of unknown variables, the computational cost becomes independent of the growth of the vectors involved.\n          <\/jats:p>\n          <jats:p>Besides introducing the algorithm, the article describes its implementation in a Modelica compiler and studies its performance over different test models.<\/jats:p>","DOI":"10.1145\/3674831","type":"journal-article","created":{"date-parts":[[2024,6,28]],"date-time":"2024-06-28T17:04:43Z","timestamp":1719594283000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Matching in Large DAE Models"],"prefix":"10.1145","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0065-6697","authenticated-orcid":false,"given":"Denise","family":"Marzorati","sequence":"first","affiliation":[{"name":"FCEIA-UNR, Rosario, Argentina and CIFASIS-CONICET, Rosario, Argentina"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4984-3327","authenticated-orcid":false,"given":"Joaqu\u00edn","family":"Fern\u00e1ndez","sequence":"additional","affiliation":[{"name":"CIFASIS-CONICET, Rosario, Argentina"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7657-3612","authenticated-orcid":false,"given":"Ernesto","family":"Kofman","sequence":"additional","affiliation":[{"name":"FCEIA-UNR, Rosario, Argentina and CIFASIS-CONICET, Rosario, Argentina"}]}],"member":"320","published-online":{"date-parts":[[2024,10,26]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Proceedings of the 13th International Modelica Conference","author":"Agosta Giovanni","year":"2019","unstructured":"Giovanni Agosta, Emanuele Baldino, Francesco Casella, Stefano Cherubin, Alberto Leva, and Federico Terraneo. 2019. Towards a high-performance modelica compiler. In Proceedings of the 13th International Modelica Conference. Link\u00f6ping University Electronic Press."},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511984068","volume-title":"Bipartite Graphs and Their Applications","author":"Asratian Armen S.","year":"1998","unstructured":"Armen S. Asratian, Tristan M. J. Denley, and Roland H\u00e4ggkvist. 1998. Bipartite Graphs and Their Applications. Vol. 131. Cambridge University Press."},{"key":"e_1_3_2_4_2","volume-title":"Proceedings of the 11th International Modelica Conference","author":"Bergero Federico","year":"2015","unstructured":"Federico Bergero, Mariano Botta, and Ernesto Kofman. 2015. Efficient compilation of large scale Modelica models. In Proceedings of the 11th International Modelica Conference."},{"key":"e_1_3_2_5_2","first-page":"557","volume-title":"Proceedings of the 12 International Modelica Conference","author":"Braun Willi","year":"2017","unstructured":"Willi Braun, Francesco Casella, Bernhard Bachmann, 2017. Solving large-scale Modelica models: New approaches and experimental results using OpenModelica. In Proceedings of the 12 International Modelica Conference. Linkoping University Electronic Press, 557\u2013563."},{"key":"e_1_3_2_6_2","volume-title":"Proceedings of Modelica 2002","author":"Br\u00fcck Dag","year":"2002","unstructured":"Dag Br\u00fcck, Hilding Elmqvist, Sven Erik Mattsson, and Hans Olsson. 2002. Dymola for multi-engineering modeling and simulation. In Proceedings of Modelica 2002."},{"key":"e_1_3_2_7_2","first-page":"351","volume-title":"Proceedings of Modelica Conferences","author":"Casella Francesco","year":"2021","unstructured":"Francesco Casella and Adrien Guironnet. 2021. ScalableTestGrids \u2013 An open-source and flexible benchmark suite to assess modelica tool performance on large-scale power system test cases. In Proceedings of Modelica Conferences. 351\u2013358."},{"key":"e_1_3_2_8_2","volume-title":"Continuous System Simulation","author":"Cellier Fran\u00e7ois E.","year":"2006","unstructured":"Fran\u00e7ois E. Cellier and Ernesto Kofman. 2006. Continuous System Simulation. Springer Science & Business Media."},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, trees, and flowers","volume":"17","author":"Edmonds Jack","year":"1965","unstructured":"Jack Edmonds. 1965. Paths, trees, and flowers. Canadian Journal of Mathematics 17 (1965), 449\u2013467.","journal-title":"Canadian Journal of Mathematics"},{"issue":"3","key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3611661","article-title":"Array-aware matching: Taming the complexity of large-scale simulation models","volume":"49","author":"Fioravanti Massimo","year":"2023","unstructured":"Massimo Fioravanti, Daniele Cattaneo, Federico Terraneo, Silvano Seva, Stefano Cherubin, Giovanni Agosta, Francesco Casella, and Alberto Leva. 2023. Array-aware matching: Taming the complexity of large-scale simulation models. ACM Transactions on Mathematical Software 49, 3 (2023), 1\u201325.","journal-title":"ACM Transactions on Mathematical Software"},{"key":"e_1_3_2_12_2","first-page":"433","volume-title":"Proceedings of the 9th International MODELICA Conference","author":"Frenkel Jens","year":"2012","unstructured":"Jens Frenkel, G\u00fcnter Kunze, and Peter Fritzson. 2012. Survey of appropriate matching algorithms for large scale systems of differential algebraic equations. In Proceedings of the 9th International MODELICA Conference. Link\u00f6ping University Electronic Press, 433\u2013442."},{"key":"e_1_3_2_13_2","first-page":"143","volume-title":"Proceedings of the 8th International Modelica Conference (Modelica \u201911)","author":"Frenkel Jens","year":"2011","unstructured":"Jens Frenkel, Christian Schubert, G\u00fcnter Kunze, Peter Fritzson, Martin Sj\u00f6lund, and Adrian Pop. 2011. Towards a benchmark suite for Modelica compilers: Large models. In Proceedings of the 8th International Modelica Conference (Modelica \u201911). Link\u00f6ping University Electronic Press, 143\u2013152."},{"key":"e_1_3_2_14_2","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1109\/SIMSYM.2002.1000174","volume-title":"Proceedings 35th Annual Simulation Symposium (SS \u201902)","author":"Fritzson Peter","year":"2002","unstructured":"Peter Fritzson and Peter Bunus. 2002. Modelica \u2013 A general object-oriented language for continuous and discrete-event system modeling and simulation. In Proceedings 35th Annual Simulation Symposium (SS \u201902). IEEE, 365\u2013380."},{"issue":"4","key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.4173\/mic.2020.4.1","article-title":"The OpenModelica integrated environment for modeling, simulation, and model-based development","volume":"41","author":"Fritzson Peter","year":"2020","unstructured":"Peter Fritzson, Adrian Pop, Karim Abdelhak, Adeel Asghar, Bernhard Bachmann, Willi Braun, Daniel Bouskela, Robert Braun, Lena Buffoni, Francesco Casella, et al. 2020. The OpenModelica integrated environment for modeling, simulation, and model-based development. Modeling, Identification and Control 41, 4 (2020), 241\u2013295.","journal-title":"Modeling, Identification and Control"},{"issue":"6","key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","article-title":"Algorithm 447: Efficient algorithms for graph manipulation","volume":"16","author":"Hopcroft John","year":"1973","unstructured":"John Hopcroft and Robert Tarjan. 1973. Algorithm 447: Efficient algorithms for graph manipulation. Communications of the ACM 16, 6 (1973), 372\u2013378.","journal-title":"Communications of the ACM"},{"issue":"4","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","article-title":"An n \\({}^{5\/2}\\)  algorithm for maximum matchings in bipartite graphs","volume":"2","author":"Hopcroft John E.","year":"1973","unstructured":"John E. Hopcroft and Richard M. Karp. 1973. An n \\({}^{5\/2}\\) algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing 2, 4 (1973), 225\u2013231.","journal-title":"SIAM Journal on computing"},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198501626.001.0001","volume-title":"Fast Parallel Algorithms for Graph Matching Problems","author":"Karpi\u0144ski Marek","year":"1998","unstructured":"Marek Karpi\u0144ski, Marek Karpinski, and Wojciech Rytter. 1998. Fast Parallel Algorithms for Graph Matching Problems. Vol. 9. Oxford University Press."},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"126181","DOI":"10.1016\/j.amc.2021.126181","article-title":"Compact sparse symbolic Jacobian computation in large systems of ODEs","volume":"403","author":"Kofman Ernesto","year":"2021","unstructured":"Ernesto Kofman, Joaqu\u00edn Fern\u00e1ndez, and Denise Marzorati. 2021. Compact sparse symbolic Jacobian computation in large systems of ODEs. Applied Mathematics and Computation 403 (2021), 126181.","journal-title":"Applied Mathematics and Computation"},{"key":"e_1_3_2_20_2","volume-title":"Matching Theory","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"2009","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Michael D Plummer. 2009. Matching Theory. Vol. 367. American Mathematical Soc."},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"126842","DOI":"10.1016\/j.amc.2021.126842","article-title":"Efficient connection processing in equation-based object-oriented models","volume":"418","author":"Marzorati Denise","year":"2022","unstructured":"Denise Marzorati, Joaquin Fern\u00e1ndez, and Ernesto Kofman. 2022. Efficient connection processing in equation-based object-oriented models. Applied Mathematics and Computation 418 (2022), 126842.","journal-title":"Applied Mathematics and Computation"},{"issue":"2","key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1137\/0909014","article-title":"The consistent initialization of differential-algebraic systems","volume":"9","author":"Pantelides Constantinos C.","year":"1988","unstructured":"Constantinos C. Pantelides. 1988. The consistent initialization of differential-algebraic systems. SIAM Journal on Scientific Computing 9, 2 (1988), 213\u2013231.","journal-title":"SIAM Journal on Scientific Computing"},{"key":"e_1_3_2_23_2","volume-title":"Proceedings of the 13th International Modelica Conference","author":"Pop Adrian","year":"2019","unstructured":"Adrian Pop, Per \u00d6stlund, Francesco Casella, Martin Sj\u00f6lund, and R\u00fcdiger Franke. 2019. A new OpenModelica compiler high performance frontend. In Proceedings of the 13th International Modelica Conference. Link\u00f6ping University Electronic Press."},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-981-15-2803-3","volume-title":"Computer Modeling and Simulation of Dynamic Systems Using Wolfram SystemModeler","author":"Rozhdestvensky Kirill","year":"2020","unstructured":"Kirill Rozhdestvensky, Vladimir Ryzhov, Tatiana Fedorova, Kirill Safronov, Nikita Tryaskin, Shaharin Anwar Sulaiman, Mark Ovinis, and Suhaimi Hassan. 2020. Computer Modeling and Simulation of Dynamic Systems Using Wolfram SystemModeler. Springer."},{"key":"e_1_3_2_25_2","first-page":"265","volume-title":"Proceedings of the 11th International Modelica Conference","author":"Schuchart Joseph","year":"2015","unstructured":"Joseph Schuchart, Volker Waurich, Martin Flehmig, Marcus Walther, Wolfgang E Nagel, and Ines Gubsch. 2015. Exploiting repeated structures and vectorization in modelica. In Proceedings of the 11th International Modelica Conference. Link\u00f6ping University Electronic Press, 265\u2013272."},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"124713","DOI":"10.1016\/j.amc.2019.124713","article-title":"Modeling and simulation of large-scale systems: A systematic comparison of modeling paradigms","volume":"365","author":"Schweiger Gerald","year":"2020","unstructured":"Gerald Schweiger, Henrik Nilsson, Josef Schoeggl, Wolfgang Birk, and Alfred Posch. 2020. Modeling and simulation of large-scale systems: A systematic comparison of modeling paradigms. Applied Mathematics and Computation 365 (2020), 124713.","journal-title":"Applied Mathematics and Computation"},{"key":"e_1_3_2_27_2","volume-title":"The Boost Graph Library: User Guide and Reference Manual","author":"Siek Jeremy","year":"2002","unstructured":"Jeremy Siek, Andrew Lumsdaine, and Lie-Quan Lee. 2002. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley."},{"issue":"2","key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan Robert","year":"1972","unstructured":"Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1, 2 (1972), 146\u2013160.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1145\/3365984.3365991","volume-title":"Proceedings of the 9th International Workshop on Equation-based Object-oriented Modeling Languages and Tools","author":"Zimmermann Pablo","year":"2019","unstructured":"Pablo Zimmermann, Joaqu\u00ednFern\u00e1ndez, and Ernesto Kofman. 2019. Set-based graph methods for fast equation sorting in large DAE systems. In Proceedings of the 9th International Workshop on Equation-based Object-oriented Modeling Languages and Tools. 45\u201354."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3674831","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3674831","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:02Z","timestamp":1750291562000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3674831"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3674831"],"URL":"https:\/\/doi.org\/10.1145\/3674831","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2024,9,30]]},"assertion":[{"value":"2023-06-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}