Efficient Matching in Large DAE Models
Article No.: 18, Pages 1 - 25
Abstract
This article presents a matching algorithm for bipartite graphs containing repetitive structures and represented by intension as Set-Based Graphs. 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 for loop statements that iterate over vectors of unknown variables, the computational cost becomes independent of the growth of the vectors involved.
Besides introducing the algorithm, the article describes its implementation in a Modelica compiler and studies its performance over different test models.
References
[1]
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öping University Electronic Press.
[2]
Armen S. Asratian, Tristan M. J. Denley, and Roland Häggkvist. 1998. Bipartite Graphs and Their Applications. Vol. 131. Cambridge University Press.
[3]
Federico Bergero, Mariano Botta, and Ernesto Kofman. 2015. Efficient compilation of large scale Modelica models. In Proceedings of the 11th International Modelica Conference.
[4]
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–563.
[5]
Dag Brück, Hilding Elmqvist, Sven Erik Mattsson, and Hans Olsson. 2002. Dymola for multi-engineering modeling and simulation. In Proceedings of Modelica 2002.
[6]
Francesco Casella and Adrien Guironnet. 2021. ScalableTestGrids – 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–358.
[7]
François E. Cellier and Ernesto Kofman. 2006. Continuous System Simulation. Springer Science & Business Media.
[8]
Jack Edmonds. 1965. Paths, trees, and flowers. Canadian Journal of Mathematics 17 (1965), 449–467.
[9]
Massimo Fioravanti. 2020. M.A.R.C.O.: An Experimental High-Performance Modelica Compiler for Large Scale Systems. Master’s thesis. Dipartimento di Elettronica, Informazione e Bioingegneria. POLITECNICO DI MILANO.
[10]
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–25.
[11]
Jens Frenkel, Günter 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öping University Electronic Press, 433–442.
[12]
Jens Frenkel, Christian Schubert, Günter Kunze, Peter Fritzson, Martin Sjölund, and Adrian Pop. 2011. Towards a benchmark suite for Modelica compilers: Large models. In Proceedings of the 8th International Modelica Conference (Modelica ’11). Linköping University Electronic Press, 143–152.
[13]
Peter Fritzson and Peter Bunus. 2002. Modelica – A general object-oriented language for continuous and discrete-event system modeling and simulation. In Proceedings 35th Annual Simulation Symposium (SS ’02). IEEE, 365–380.
[14]
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–295.
[15]
John Hopcroft and Robert Tarjan. 1973. Algorithm 447: Efficient algorithms for graph manipulation. Communications of the ACM 16, 6 (1973), 372–378.
[16]
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–231.
[17]
Marek Karpiński, Marek Karpinski, and Wojciech Rytter. 1998. Fast Parallel Algorithms for Graph Matching Problems. Vol. 9. Oxford University Press.
[18]
Ernesto Kofman, Joaquín Fernández, and Denise Marzorati. 2021. Compact sparse symbolic Jacobian computation in large systems of ODEs. Applied Mathematics and Computation 403 (2021), 126181.
[19]
László Lovász and Michael D Plummer. 2009. Matching Theory. Vol. 367. American Mathematical Soc.
[20]
Denise Marzorati, Joaquin Fernández, and Ernesto Kofman. 2022. Efficient connection processing in equation-based object-oriented models. Applied Mathematics and Computation 418 (2022), 126842.
[21]
Constantinos C. Pantelides. 1988. The consistent initialization of differential-algebraic systems. SIAM Journal on Scientific Computing 9, 2 (1988), 213–231.
[22]
Adrian Pop, Per Östlund, Francesco Casella, Martin Sjölund, and Rüdiger Franke. 2019. A new OpenModelica compiler high performance frontend. In Proceedings of the 13th International Modelica Conference. Linköping University Electronic Press.
[23]
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.
[24]
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öping University Electronic Press, 265–272.
[25]
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.
[26]
Jeremy Siek, Andrew Lumsdaine, and Lie-Quan Lee. 2002. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley.
[27]
Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1, 2 (1972), 146–160.
[28]
Pablo Zimmermann, Joaquín Fernández, 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–54.
Index Terms
- Efficient Matching in Large DAE Models
Recommendations
Efficient connection processing in equation–based object–oriented models
Highlights- A novel methodology for transforming a large set of connections into the corresponding set of equations is presented.
AbstractThis work introduces a novel methodology for transforming a large set of connections into the corresponding set of equations as required by the flattening stage of the compilation process of object oriented models. The proposed ...
Location-domination and matching in cubic graphs
A dominating set of a graph G is a set D of vertices of G such that every vertex outside D is adjacent to a vertex in D . A locating-dominating set of G is a dominating set D of G with the additional property that every two distinct vertices outside D ...
Maximum weight induced matching in some subclasses of bipartite graphs
AbstractA subset of edges of a graph is called a matching in G if no two edges in M share a common vertex. A matching M in G is called an induced matching if G[M], the subgraph of G induced by M, is the same as G[S], the subgraph of G induced ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2024
129 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 26 October 2024
Online AM: 28 June 2024
Accepted: 25 May 2024
Revised: 07 May 2024
Received: 14 June 2023
Published in TOMS Volume 50, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 124Total Downloads
- Downloads (Last 12 months)124
- Downloads (Last 6 weeks)24
Reflects downloads up to 24 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in