Determining over- and under-constrained systems of equations using structural constraint delta

ABSTRACT

Computer aided modeling and simulation of complex physical systems, using components from multiple application domains, such as electrical, mechanical, and hydraulic, have in recent years witnessed a significant growth of interest. In the last decade, equation-based object-oriented (EOO) modeling languages, (e.g. Modelica, gPROMS, and VHDL-AMS) based on acausal modeling using Differential Algebraic Equations (DAEs), have appeared. With such languages, it is possible to model physical systems at a high level of abstraction by using reusable components.A model in an EOO language needs to have the same number of equations as unknowns. A previously unsolved problem concerning this property is the efficient detection of over- or under-constrained models in the case of separately compiled models.This paper describes a novel technique to determine over- and under-constrained systems of equations in models, based on a concept called structural constraint delta. In many cases it is also possible to locate the source of the constraint-problem. Our approach makes use of static type checking and consists of a type inference algorithm. We have implemented it for a subset of the Modelica language, and successfully validated it on several examples.

REFERENCES

• 1: Peter Bunus and Peter Fritzson. Automated Static Analysis of Equation-Based Components. SIMULATION, 80(7--8):321--245, 2004.
• 2: Ernst Christen and Kenneth Bakalar. VHDL-AMS - A Hardware Description Language for Analog and Mixed-Signal Applications. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 46(10):1263--1272, 1999.
• 3: I. S. Duff , J. K. Reid, Algorithm 529: Permutations To Block Triangular Form [F1], ACM Transactions on Mathematical Software (TOMS), v.4 n.2, p.189-192, June 1978 [doi>10.1145/355780.355790]
• 4: Dynasim. Dymola - Dynamic Modeling Laboratory with Modelica (Dynasim AB). http://www.dynasim.se/ {Last accessed: 8 May 2006}.
• 5: Georgina Fábián. A Language and Simulator for Hybrid Systems. PhD thesis, Technische Universiteit Eindhoven, the Netherlands, 1999.
• 6: Peter Fritzson, Principles of Object-Oriented Modeling and Simulation with Modelica 2.1, Wiley-IEEE Computer Society Pr, 2003
• 7: Peter Fritzson, Peter Aronsson, Húakan Lundvall, Kaj Nyström, Adrian Pop, Levon Saldamli, and David Broman. The OpenModelica Modeling, Simulation, and Development Environment. In Proceedings of the 46th Conference on Simulation and Modeling (SIMS'05), pages 83--90, Trondheim, Norway, 2005.
• 8: MathWorks. The Mathworks - Simulink - Simulation and Model-Based Design. http://www.mathworks.com/products/simulink/ Last accessed: 15 May 2006.
• 9: Modelica Association. Modelica - A Unified Object-Oriented Language for Physical Systems Modeling - Language Specification Version 2.2, February 2005. Available from: http://www.modelica.org {Last accessed: 29 March 2006}.
• 10: M. Oh and Costas C. Pantelides. A modelling and Simulation Language for Combined Lumped and Distributed Parameter Systems. Computers and Chemical Engineering, 20(6--7):611--633, 1996.
• 11: Linda R. Petzold. A Description of DASSL: A Differential/Algebraic System Solver. In IMACS Trans. on Scientific Comp., 10th IMACS World Congress on Systems Simulation and Scientific Comp., Montreal, Canada, 1982.
• 12: Benjamin C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.2 Simulation Languages

General Terms:
Algorithms, Languages

Keywords:
equation-based, modeling, object-oriented, over-constrained, separate compilation, type checking, under-constrained