Conference article

Survey of appropriate matching algorithms for large scale systems of differential algebraic equations

Jens Frenkel
Dresden Technical University, Institute of Mobile Machinery and Processing Machines, Germany

Günter Kunze
Dresden Technical University, Institute of Mobile Machinery and Processing Machines, Germany

Peter Fritzson
PELAB - Programming Environment Lab, Dept. Computer Science, Linköping University, Linköping, Sweden

Download articlehttp://dx.doi.org/10.3384/ecp12076433

Published in: Proceedings of the 9th International MODELICA Conference; September 3-5; 2012; Munich; Germany

Linköping Electronic Conference Proceedings 76:45, p. 433-442

Show more +

Published: 2012-11-19

ISBN: 978-91-7519-826-2

ISSN: 1650-3686 (print), 1650-3740 (online)

Abstract

This paper presents a survey on matching algorithms which are required to translate Modelica Models. Several implementations of matching algorithms are benchmarked on a set of physical models from mechanical systems in ODE and DAE representation. The major part of algorithms is based on the Augmenting Paths Method and one algorithm is based on the Push-Relabel Method. The algorithms are implemented in the programming language C and Meta-Modelica. In addition two cheap matching algorithms are used to jump-start the advanced matching process.

Keywords

matching; index reduction; modelimark

References

[1] Alt; H.; Blum; N.; Mehlhorn; K.; Paul; M.: Computing a maximum cardinality matching in a bipartite graph in time O(n1:5pm=log(n)); Information Processing Letters; Volume 37; Issue 4; 28 February 1991; Pages 237-240. doi: 10.1016/0020-0190(91)90195-N.

[2] Berge; C. The Theroy of Graphs. Methuen; London; 1962

[3] Blum. N.: A simplified realization of the Hopcroft-Karp approach to maximum matching in general graphs. Technical report; Universität Bonn; 1999.

[4] Duff; I. S. On algorithms for obtaining a maximum transversal. ACM Trun.s. Math. Softw. 7(1981); 315-330. doi: 10.1145/355958.355963.

[5] Duff; I.S.; Erisman; A.M.; Reid; J.K.: Direct methods for sparse matrices;1986;Clarendon Press Oxford

[6] Duff; I. S.; Reid J. K.; Harwell; A.: An implementation of Tarjan’s algorithm for the block triangularization of a matrix;in ACM Trans. Math. Software Volume 4; pp. 137-147; 1978. doi: 10.1145/355780.355785.

[7] Duff; I. S.: Algorithm 575: Permutations for a Zero-Free Diagonal [F1]. ACM Trans. Math. Softw. 7; 3 September 1981; 387-390. doi: 10.1145/355958.355968.

[8] Duff; I. S.; Wiberg; T.: Remarks on implementation of O(n1=2t) assignment algorithms ;in ACM Trans. Math. Software Volume1 4; pp. 267-287; 1988. doi: 10.1145/44128.44131.

[9] Duff; I.S.; Kaya; K.; Uçar; B.: Design; implementation; and analysis of maximum transversal algorithms;ACM Transactions on Mathematical Software (TOMS);38;2;13;2011;ACM

[10] Elmqvist; H.: A Structured Model Language for Large Continuous Systems; Ph.D. Dissertation; Report CODEN: LUTFD2/(TFRT-1015); Dept. of Automatic Control; Lund Institute of Technology; Lund; Sweden; 1978

[11] Frenkel; J.; Schubert; C.; Kunze; G.; Fritzson; P.; Sjölund; M.; Pop; A.: Towards a Benchmark Suite for Modelica Compilers: Large Models. In: Proceedings of the 8th Modelica Conference 2011; Dresden; Germany; Modelica Association; 20-22 March 2011. https://www.modelica.org/events/modelica2011/Proceedings/pages/papers/07_1_ID_183_a_fv.pdf

[12] Goldberg; A. V.; Tarjan; R. E.: A new approach to the maximum flow problem. Annual ACM Symposium on Theory of Computing; Proceedings of the eighteenth annual ACM symposium on Theory of computing; 136-146

[13] Hopcroft; J. E.; Karp; R. M.: A n5=2 algorithm for maximum matchings in bipartite graphs. SIAM Journal of Computing; 2(4): 225-231; 1973. doi: 10.1137/0202019.

[14] Kaya; K.; Langguth; J.; Manne; F.; Uçar; B.: Experiments on Push-Relabel-based Maximum Cardinality Matching Algorithms for Bipartite Graphs; CERFACS Tech. Report TR/PA/11/33; May; 2011

[15] Kaya; K.: http://bmi.osu.edu/ kamer/research.html; last visit 2012-02-05; Matchmaker v0.3

[16] Kunkel; P.; Mehrmann; V.: Index reduction for differential-algebraic equations by minimal extension. Z. angew. Math. Mech.; 84: pp. 579-597; 2004. doi: 10.1002/zamm.200310127.

[17] Kunze; G.; Frenkel; J.; Knoll; C.; Schubert C.; Voigt; S.: PyMbs: Ein generisches Software Werkzeug für die Simulation von Mehrkörpersystemen; VDI Mechatronik Tagung; 2011.

[18] Mattsson; S.; Söderlind; G.: Index reduction in differential-Algebraic equations using dummy derivatives; SIAM J. Sci. Comput. 14; 677-692; 1993. doi: 10.1137/0914043.

[19] Mattsson; S.E.; Olsson; H; Elmqviste; H. Dynamic election of States in Dymola. In: Proceedings of the Modelica Workshop 2000; Lund; Sweden; Modelica Association; 23-24 Oct. 2000.

[20] Mattsson; S.E.; Söderlind; G.: A new technique for solving high-index differential-algebraic equations using dummy derivatives; Computer-Aided Control System Design; 1992. (CACSD); 1992 IEEE Symposium on ; pp.218-224; 17-19 Mar 1992

[21] Pantelides C. The Consistent Initialization of Differential-Algebraic Systems.SIAM J. Sci. and Stat. Comput. Volume 9; Issue 2; pp. 213-231; March 1988. doi: 10.1137/0909014.

[22] Pop; A.; Fritzson; P.: MetaModelica: A Unified Equation-Based Semantical and Mathematical Modelling Language. In Proceedings of Joint Modular Languages Conference 2006 (JMLC2006) LNCS Springer Verlag. Jesus College; Oxford; England; Sept 13-15; 2006.

[23] Pothen; A; Fan; C.-J.: Computing the block triangular form of a sparse matrix. ACM Trans. Math. Softw. 16; 4 ;December 1990; 303-324

[24] Setubal; J.C.: Sequential and parallel experimental results with bipartite matching algorithms ; in Technical Report EC-96-09; Institute of Computing; University of Campinas; Brasil; 1996

[25] Soares; R. de P.; Secchi; A. R.: Direct Initialisation and Solution of High-Index DAESystems. in Proceedings of the European Symbosium on Computer Aided Process Engineering - 15; Barcelona; Spain; 2005

[26] R. Tarjan; Depth-first search and linear graph algorithms; in Conf.Record 1971 IEEE 12th Annu. Symp. Switch. Automata Theory; 1971;pp. 114-121

[27] Unger; J.; Kröner; A.; Marquardt;W.: Structural analysis of differential-algebraic equation systems-theory and applications; Computers & Chemical Engineering; Volume 19; Issue 8; August 1995; Pages 867-882. doi: 10.1016/0098-1354(94)00094-5.

Citations in Crossref