Efficient Matching in Large DAE Models

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 iterates 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.