Several new algorithms are proposed that in effect transform DAEs (Differential Algebraic Equations) to a special index one form that can be simulated with standard DAE integrators. The transformation to this form is performed without solving linear and/or nonlinear equation systems, the sparsity of the equations is kept, and array equations remain array equations or differentiated versions of them. Furthermore, certain DAEs can be handled where structural index reduction methods fail. It is expected that these new algorithms will help to treat large Modelica models of any index in a better way as it is currently possible. The algorithms have been evaluated and tested in the experimental simulation environment Modia that is implemented with the Julia programming language.
Modelica, Modia, Julia, DAE, sparse DAE, large DAE, Pantelides algorithm, Dummy Derivative Method.ve Method
M. Arnold (2016): DAE aspects of multibody systems. In A. Ilchmann, T. Reis (eds.): Surveys in Differential-Algebraic Equations IV. - Springer, 2017 (in print). - A preliminary version of this material was published as Technical Report 01-2016, Martin Luther University Halle-Wittenberg, Report No. 01, 2016. http://sim.mathematik.unihalle.de/reports/sources/2016/01-2016.pdf
U.M. Ascher, L.R. Petzold (1991): Projected Implicit Runge–Kutta Methods for Differential-Algebraic Equations. SIAM J. Numer. Anal., 28(4), pp. 1097–1120.
A. Bahainv, H. Schichl, A. Neumaier (2016a): Tearing systems of nonlinear equations. I. A survey. http://www.mat.univie.ac.at/~neum/ms/tearing_survey.pdf
A. Bahainv, H. Schichl, A. Neumaier (2016b): Tearing systems of nonlinear equations. II. A practical exact algorithm. http://www.mat.univie.ac.at/~neum/ms/tearing_exact_algorithm.pdf
E.H. Bareiss (1968): Sylvester’s Identity and Multistep Integer-Preserving Gaussian Elimination. Math. Comp. 22, pp. 565-578.
M.A. Bender, J.T. Fineman, S. Gilbert, R.E. Tarjan (2016): A New Approach to Incremental Cycle Detection and Related Problems. ACM Transactions on Algorithms, Volume 12, Issue 2.
A. Benveniste, B. Caillaud, H. Elmqvist, K. Ghorbal, M. Otter, and Marc Pouzet (2017): Multi-Mode DAE Models Challenges, Theory and Implementation. Lecture Notes on Computer Science, submitted for review.
J. Bezanson, A. Edelman, S. Karpinski and V.B. Shah (2017): Julia: A Fresh Approach to Numerical Computing. SIAM Review, Vol. 59, No. 1, pp. 65-98. http://julialang.org/publications/julia-fresh-approach-BEKS.pdf; see also: http://julialang.org/
K.E. Brenan, S.L. Campbell, and L.R. Petzold (1996): Numerical Solution of Initial Value Problems in Differential-Algebraic Equations. SIAM.
E. Carpanzano, R. Girelli (1997): The Tearing Problem: Definition, Algorithm and Application to Generate Efficient Computational Code from DAE Systems. Proceedings of 2nd Mathmod Vienna, IMACS Symposium on Mathematical Modelling, Wien.
S. Chowdhry, H. Krendl, and A.A. Linninger (2004): Symbolic numeric index analysis algorithm for differential algebraic equations. Industrial and Engineering Chemistry Research. Vol. 43, Issue 14, pp. 3886-3894.
W. Cook, and A. Rohe (1999): Computing Minimum-Weight Perfect Matchings. INFORMS Journal of Computing, Vol. 11. www.math.uwaterloo.ca/~bico/papers/match_ijoc.pdf
I.S. Duff (1981): On algorithms for obtaining a maximum transversal. ACM Trans. Math. Software, Vol. 7, Issue 3.
I.S. Duff, K. Kaya, and B. Ucar (2011): Design, Implementation, and Analysis of Maximum Transversal Algorithms. ACM Trans. Math. Software, Vol. 38, Issue 2.
J. Edmonds (1965): Paths, Trees , and Flowers. Canadian Journal of Mathematics. Vol. 17, pp. 449-467. https://cms.math.ca/openaccess/cjm/v17/cjm1965v17.0449-0467.pdf
E. Eich (1993): Convergence Results for a Coordinate Projecion Method Applied To Mechanical Systems with Algebraic Constraints. SIAM J. Numer. Anal. Vol. 30, No. 5, pp. 1467-1482.
H. Elmqvist, M. Otter (1994): Methods for Tearing Systems of Equations in Object-Oriented Modeling. Proceedings ESM’94, European Simulation Multiconference, Barcelona, Spain, June 1–3, pp. 326–332.
H. Elmqvist, T. Henningsson, M. Otter (2016): System Modeling and Programming in a Unified Environment based on Julia. Proceedings of ISoLA 2016 Conference Oct. 10-14, T. Margaria and B. Steffen (Eds.), Part II, LNCS 9953, pp. 198-217. http://www.isolaconference.org/isola2016/proceedings.html
H. Elmqvist, S.E. Mattsson (2016): Exploiting Model Graph Analysis for Simplified Modeling and Improved Diagnostics. Proceedings EOOLT ’16, April 18, Milano, Italy.
H. Elmqvist, T. Henningsson, M. Otter (2017): Innovations for future Modelica. Modelica Conference 2017, Prague.
J. Frenkel, G. Kunze, P. Fritzson (2012): Survey of appropriate matching algorithms for large scale systems of differential algebraic equations. Proceedings of the 9th International Modelica Conference, Munich. http://www.ep.liu.se/ecp/076/045/ecp12076045.pdf
C. Führer (1988): Differential-algebraische Gleichungssysteme in mechanischen Mehrkörpersystemen. Theorie, numerische Ansätze und Anwendungen. PhD thesis, TU München, Mathematisches Institut und Institut für Informatik.
C.W. Gear (1988): Differential-Algebraic Equation Index Transformations. SIAM J. Sci. Stat. Comput., Vol. 9, No. 1, pp. 39-47.
C.W. Gear, G.K. Gupta and B. Leimkuhler (1985): Automatic integration of Euler–Lagrange equations with constraints. J. Comp. Appl. Math., 12&13, pp. 77–90.
A.C. Hindmarsh, P.N. Brown, K.E. Grant, S.L. Lee, R. Serban, D.E. Shumaker, and C. S. Woodward (2005): SUNDIALS: Suite of Nonlinear and Differential/Algebraic Equation Solvers. ACM Transactions on Mathematical Software, Vol. 31, No. 3, pp. 363–396. http://computation.llnl.gov/projects/sundials/toms_sundials.pdf
G. Kron (1962): Diakoptics – The piecewise Solution of Large-Scale Systems. MacDonald & Co., London.
S.E. Mattsson and G. Söderlind (1993): Index Reduction in Differential-Algebraic Equations using Dummy Derivatives. SIAM Journal of Scientific Computing. 14(3), pp. 677-692.
S.E. Mattsson, H. Olsson and H. Elmqvist (2000): Dynamic Selection of States in Dymola. Modelica Workshop 2000, Lund, Sweden, pp. 61-67. https://www.modelica.org/events/workshop2000/proceedings/old/Mattsson.pdf
R.C. Melville, L. Trajkovic,S.-C. Fang, L.T. Watson (1993): Artifical parameter homotopy methods for the DC operating point problem," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, pp. 861-877.
M. Otter (1999): Objektorientierte Modellierung Physikalischer Systeme, Teil 4: Transformationsalgorithmen. At Automatisierungstechnik, 47, 3, pp. A9-A12.
C.C. Pantelides (1988): The Consistent Initialization of Differential-Algebraic Systems. SIAM Journal on Scientific and Statistical Computing, 9(2):213–231.
L. Petzold and P. Lötstedt (1986): Numerical Solution of Nonlinear Differential Equations with Algebraic Constraints II: Practical Implications. SIAM J. Sci. Stat. Comput. Vol. 7, No. 3, pp. 720-733.
J.D. Pryce (2001). A Simple Structural Analysis Method for DAEs. BIT Numerical Mathematics, Vol. 41, Issue 2, pp. 364-394.
J. Schuchart, V. Waurich, M. Flehmig, M. Walther, W.E. Nagel, I. Gubsch (2015): Exploiting Repeated Structures and Vectorization in Modelica. Proc. of the 11th Int. Modelica Conference, Versailles. www.ep.liu.se/ecp/118/028/ecp15118265.pdf
M. Sielemann (2012): Device-Oriented Modeling and Simulation in Aircraft Energy Systems Design. PhDDissertation. Technische Universität Hamburg-Harburg. http://www.dr.hut-verlag.de/9783843905046.html
R.L. Sigurðsson (2016): Practical performance of incremental topological sorting and cycle detection algorithms. Chalmers University of Technology. Master Thesis.
http://publications.lib.chalmers.se/records/fulltext/248308/248308.pdf
S.S. Skiena (2008): The Algorithm Design Manual. Second edition. Springer.
K. Stavaker: Contributions to Simulation of Modelica Models on Data-Parallel Multi-Core Architectures. PhD thesis. Linköping University. http://liu.divaportal.org/smash/get/diva2:806837/FULLTEXT01.pdf
P.R. Turner (1995): A simplified fraction-free Integer Gauss Elimination Algorithm. REPORT NO: NAWCADPAX-96-196-TR. Office of Naval Research. http://www.dtic.mil/cgibin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA313755
