{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:21Z","timestamp":1750219761703,"version":"3.41.0"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T00:00:00Z","timestamp":1695081600000},"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":[[2023,9,30]]},"abstract":"<jats:p>Equation-based modelling is a powerful approach to tame the complexity of large-scale simulation problems. Equation-based tools automatically translate models into imperative languages. When confronted with nowadays\u2019 problems, however, well assessed model translation techniques exhibit scalability issues that are particularly severe when models contain very large arrays. In fact, such models can be made very compact by enclosing equations into looping constructs, but reflecting the same compactness into the translated imperative code is nontrivial. In this paper, we face this issue by concentrating on a key step of equations-to-code translation, the equation\/variable matching. We first show that an efficient translation of models with (large) arrays needs awareness of their presence, by defining a figure of merit to measure how much the looping constructs are preserved along the translation. We then show that the said figure of merit allows to define an optimal array-aware matching, and as our main result, that the so stated optimal array-aware matching problem is NP-complete. As an additional result, we propose a heuristic algorithm capable of performing array-aware matching in polynomial time. The proposed algorithm can be proficiently used by model translator developers in the implementation of efficient tools for large-scale system simulation.<\/jats:p>","DOI":"10.1145\/3611661","type":"journal-article","created":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T12:10:07Z","timestamp":1690805407000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Array-Aware Matching: Taming the Complexity of Large-Scale Simulation Models"],"prefix":"10.1145","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-7258-4104","authenticated-orcid":false,"given":"Massimo","family":"Fioravanti","sequence":"first","affiliation":[{"name":"Politecnico di Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1453-3257","authenticated-orcid":false,"given":"Daniele","family":"Cattaneo","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7475-6167","authenticated-orcid":false,"given":"Federico","family":"Terraneo","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5207-3824","authenticated-orcid":false,"given":"Silvano","family":"Seva","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5579-5942","authenticated-orcid":false,"given":"Stefano","family":"Cherubin","sequence":"additional","affiliation":[{"name":"NTNU Norwegian University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0255-4475","authenticated-orcid":false,"given":"Giovanni","family":"Agosta","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4509-0711","authenticated-orcid":false,"given":"Francesco","family":"Casella","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2165-2078","authenticated-orcid":false,"given":"Alberto","family":"Leva","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,9,19]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"[n.d.]. Dymola home page. https:\/\/www.3ds.com\/products-services\/catia\/products\/dymola\/"},{"key":"e_1_3_3_3_2","unstructured":"[n.d.]. JModelica home page. https:\/\/jmodelica.org\/"},{"key":"e_1_3_3_4_2","unstructured":"[n.d.]. ModiaBase home page. https:\/\/github.com\/ModiaSim\/ModiaBase.jl"},{"key":"e_1_3_3_5_2","unstructured":"[n.d.]. OpenModelica home page. https:\/\/www.openmodelica.org\/"},{"key":"e_1_3_3_6_2","unstructured":"[n.d.]. SimulationX home page. https:\/\/www.mathworks.com\/products\/connections\/product_detail\/simulationx.html"},{"key":"e_1_3_3_7_2","volume-title":"Model Based Control: Case Studies in Process Engineering","author":"Agachi Paul Serban","year":"2007","unstructured":"Paul Serban Agachi, Zolt\u00e1n K. Nagy, Mircea Vasile Cristea, and \u00c1rp\u00e1d Imre-Lucaci. 2007. Model Based Control: Case Studies in Process Engineering. John Wiley & Sons, Hoboken, NJ, USA."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.3384\/ecp19157313"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3365984.3365988"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ifacol.2019.11.383"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.procir.2019.03.072"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/CACSD.1989.69825","volume-title":"Proc. 2nd IEEE Control Systems Society Workshop on Computer-Aided Control System Design","author":"Andersson Mats","year":"1989","unstructured":"Mats Andersson. 1989. An object-oriented language for model representation. In Proc. 2nd IEEE Control Systems Society Workshop on Computer-Aided Control System Design. Tampa, FL, USA, 8\u201315."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0098-1354(01)00631-7"},{"key":"e_1_3_3_14_2","first-page":"8","volume-title":"Proc. 3rd IEEE Control Systems Society Symposium on Computer-Aided Control System Design","author":"\u00c5str\u00f6m Karl Johan","year":"1986","unstructured":"Karl Johan \u00c5str\u00f6m and Wolfgang Kreutzer. 1986. System representations. In Proc. 3rd IEEE Control Systems Society Symposium on Computer-Aided Control System Design. Arlington, VA, USA, 8\u201315."},{"key":"e_1_3_3_15_2","volume-title":"Structural Pitfalls of State-of-the-art Modelica Compilers: An Explorative Analysis","author":"Baldino Emanuele","year":"2018","unstructured":"Emanuele Baldino. 2018. Structural Pitfalls of State-of-the-art Modelica Compilers: An Explorative Analysis. MSc Thesis in Computer Science Engineering. Politecnico di Milano. http:\/\/hdl.handle.net\/10589\/144734"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690400608"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/SoSE50414.2020.9130534"},{"key":"e_1_3_3_18_2","first-page":"121","volume-title":"Proc. 2nd International Workshop on Equation-Based Object-Oriented Languages and Tools","author":"Bunus Peter","year":"2008","unstructured":"Peter Bunus and Karin Lunde. 2008. Supporting model-based diagnostics with equation-based object oriented languages. In Proc. 2nd International Workshop on Equation-Based Object-Oriented Languages and Tools. Paphos, Cyprus, 121\u2013130."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.3384\/ecp15118459"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ifacol.2017.08.1096"},{"key":"e_1_3_3_21_2","first-page":"35","volume-title":"Proc. 2nd International Workshop on Equation-Based Object-Oriented Languages and Tools","author":"Casella Francesco","year":"2008","unstructured":"Francesco Casella, Filippo Donida, and Marco Lovera. 2008. Beyond simulation: Computer aided control system design using equation-based object oriented modelling for the next decade. In Proc. 2nd International Workshop on Equation-Based Object-Oriented Languages and Tools. Paphos, Cyprus, 35\u201345."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1080\/13873950500071082"},{"key":"e_1_3_3_23_2","first-page":"40","volume-title":"Simulation in Engineering Sciences","author":"Cellier Fran\u00e7ois E.","year":"1983","unstructured":"Fran\u00e7ois E. Cellier. 1983. Simulation software: Today and tomorrow. In Simulation in Engineering Sciences, J. Burger and Y. Jarny (Eds.). Elsevier, Amsterdam, The Netherlands, 40\u201355."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/1121743"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ress.2018.03.025"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.compind.2019.103130"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1080\/13873950701847090"},{"key":"e_1_3_3_28_2","volume-title":"What Every Programmer Should Know About Memory","author":"Drepper Ulrich","year":"2007","unstructured":"Ulrich Drepper. 2007. What Every Programmer Should Know About Memory. https:\/\/people.freebsd.org\/lstewart\/articles\/cpumemory.pdf"},{"key":"e_1_3_3_29_2","volume-title":"Proc. Summer Computer Simulation Conference","author":"Elmqvist Hilding","year":"1979","unstructured":"Hilding Elmqvist. 1979. DYMOLA \u2013 A structured model language for large continuous systems. In Proc. Summer Computer Simulation Conference. Toronto, Canada."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/37.16751"},{"key":"e_1_3_3_31_2","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/978-3-030-30985-5_4","volume-title":"From Software Engineering to Formal Methods and Tools, and Back","author":"Fitzgerald John","year":"2019","unstructured":"John Fitzgerald, Peter Gorm Larsen, and Ken Pierce. 2019. Multi-modelling and co-simulation in the engineering of cyber-physical systems: Towards the digital twin. In From Software Engineering to Formal Methods and Tools, and Back, M. H. Ter Beek, A. Fantechi, and L. Semini (Eds.). Springer, Berlin, Germany, 40\u201355."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_3_33_2","first-page":"1","volume-title":"Mathematics in Industrial Problems. The IMA Volumes in Mathematics and its Applications","author":"Friedman Avner","year":"1992","unstructured":"Avner Friedman. 1992. Sparse matrix methods for chemical process simulation. In Mathematics in Industrial Problems. The IMA Volumes in Mathematics and its Applications. Vol. 49. Springer, New York, NY, USA, 1\u201310."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.3384\/ecp18154206"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASWEC.2009.46"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.3182\/20020721-6-ES-1901.01014"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1115\/1.4049537"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1089014.1089020"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2005.1511865"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/271130.271197"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICECS.2008.4675002"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.arcontrol.2020.08.003"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/358438.349320"},{"key":"e_1_3_3_46_2","first-page":"545","volume-title":"Proc. 40th European Microwave Conference","author":"Li Le-Wei","year":"2010","unstructured":"Le-Wei Li. 2010. Integral-equation based fast solvers developed for microwave and RF applications. In Proc. 40th European Microwave Conference. Paris, France, 545\u2013548."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.3384\/ecp09430034"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ifacol.2018.08.415"},{"key":"e_1_3_3_49_2","first-page":"542","volume-title":"Proc. 26th INCOSE International Symposium","author":"Malone Robert","year":"2016","unstructured":"Robert Malone, Brittany Friedland, John Herrold, and Daniel Fogarty. 2016. Insights from large scale model based systems engineering at Boeing. In Proc. 26th INCOSE International Symposium. Edinburgh, UK, 542\u2013555."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/SEST.2018.8495846"},{"issue":"3","key":"e_1_3_3_51_2","first-page":"16","article-title":"Modelica: An international effort to design the next generation modelling language","volume":"38","author":"Mattsson Sven Erik","year":"1997","unstructured":"Sven Erik Mattsson, Hilding Elmqvist, and Jan F. Broenink. 1997. Modelica: An international effort to design the next generation modelling language. Journal A 38, 3 (1997), 16\u201319.","journal-title":"Journal A"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0967-0661(98)00047-1"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00163-016-0247-y"},{"key":"e_1_3_3_54_2","first-page":"275","volume-title":"Proc. 2nd International Modelica Conference","author":"Moormann Dieter","year":"2002","unstructured":"Dieter Moormann and Gertjan Looye. 2002. The Modelica flight dynamics library. In Proc. 2nd International Modelica Conference. Oberpfaffenhofen, Germany, 275\u2013284."},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1515\/auto-2017-0130"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1201\/9780429347474-4"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.3384\/ecp17132565"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(96)00058-0"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.5555\/54431.54432"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.3384\/ecp19157689"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_3_3_62_2","first-page":"505","volume-title":"Proc. 34th IEEE International Parallel and Distributed Processing Symposium","author":"Rouet Fran\u00e7ois-Henry","year":"2020","unstructured":"Fran\u00e7ois-Henry Rouet, Cleve Ashcraft, Jef Dawson, Roger Grimes, Erman Guleryuz, Seid Koric, Robert F. Lucas, James S. Ong, Todd A. Simons, and Ting-Ting Zhu. 2020. Scalability challenges of an industrial implicit finite element code. In Proc. 34th IEEE International Parallel and Distributed Processing Symposium. New Orleans, LA, USA, 505\u2013514."},{"key":"e_1_3_3_63_2","first-page":"1147","volume-title":"Proc. 8th International IBPSA Conference","author":"Sahlin Per","year":"2003","unstructured":"Per Sahlin, Lars Eriksson, Pavel Grozman, Hans Johnsson, Alexander Shapovalov, and Mika Vuolle. 2003. Will equation-based building simulation make it?-experiences from the introduction of IDA Indoor Climate And Energy. In Proc. 8th International IBPSA Conference. Eindhoven, The Netherlands, 1147\u20131154."},{"key":"e_1_3_3_64_2","first-page":"285\u2013 292","volume-title":"Proc. 5th International Modelica Conference","author":"Sandholm Anders","year":"2006","unstructured":"Anders Sandholm, Peter Bunus, and Peter Fritzson. 2006. A numeric library for use in Modelica simulations with LAPACK, SuperLU, Interpolation, and MatrixIO. In Proc. 5th International Modelica Conference. Vienna, Austria, 285\u2013 292."},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2018.2804917"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.3384\/ecp15118265"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2019.124713"},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.3384\/diss.diva-116346"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-7788(00)00113-4"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(84)80011-3"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(84)80012-5"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDC.2002.1177754"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cirp.2018.04.055"},{"key":"e_1_3_3_74_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_3_75_2","first-page":"351","article-title":"High performance computing in flow simulations","volume":"134","author":"Tezduyar Tayfun E.","year":"1996","unstructured":"Tayfun E. Tezduyar, Shahrouz K. Aliabadi, Michael J. Behr, Arthur G. Johnson, Vinay J. Kalro, and Matthew Litke. 1996. High performance computing in flow simulations. Computer Methods in Applied Mechanics and Engineering 134 (1996), 351\u2013373.","journal-title":"Computer Methods in Applied Mechanics and Engineering"},{"key":"e_1_3_3_76_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1367-5788(03)00010-5"},{"key":"e_1_3_3_77_2","first-page":"575","volume-title":"Proc. 20th International Conference on Tools and Algorithms for the Construction and Analysis of Systems","author":"Beek Dirk A. van","year":"2014","unstructured":"Dirk A. van Beek, Wan J. Fokkink, Dennis Hendriks, Albert T. Hofkamp, Jasen Markovski, Joanna M. van de Mortel-Fronczak, and Michel A. Reniers. 2014. CIF 3: Model-based engineering of supervisory controllers. In Proc. 20th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Grenoble, France, 575\u2013580."},{"key":"e_1_3_3_78_2","doi-asserted-by":"publisher","DOI":"10.5220\/0007250402290239"},{"key":"e_1_3_3_79_2","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1007\/978-3-642-11842-5_58","volume-title":"High Performance Computing and Applications","author":"Wang Wenqing","year":"2010","unstructured":"Wenqing Wang and Olaf Kolditz. 2010. Sparse matrix and solver objects for parallel finite element simulation of multi-field problems. In High Performance Computing and Applications, W. Zhang and Z. Chen (Eds.). Springer, Berlin, Germany, 418\u2013425."},{"key":"e_1_3_3_80_2","volume-title":"Proc. 2nd SimBuild Conference","author":"Wetter Michael","year":"2006","unstructured":"Michael Wetter and Christoph Haugstetter. 2006. Modelica versus TRNSYS \u2013 A comparison between an equation-based and a procedural modeling language for building energy simulation. In Proc. 2nd SimBuild Conference. Cambridge, MA, USA."},{"key":"e_1_3_3_81_2","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1145\/3365984.3365991","volume-title":"Proc. 9th International Workshop on Equation-based Object-oriented Modeling Languages and Tools","author":"Zimmermann Pablo","year":"2019","unstructured":"Pablo Zimmermann, Joaqu\u00edn Fern\u00e1ndez, and Ernesto Kofman. 2019. Set-based graph methods for fast equation sorting in large DAE systems. In Proc. 9th International Workshop on Equation-based Object-oriented Modeling Languages and Tools. Berlin, Germany, 45\u201354."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611661","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3611661","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:08Z","timestamp":1750178228000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611661"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,19]]},"references-count":80,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3611661"],"URL":"https:\/\/doi.org\/10.1145\/3611661","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2023,9,19]]},"assertion":[{"value":"2021-10-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-17","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}