Article | Proceedings of the 9th International MODELICA Conference; September 3-5; 2012; Munich; Germany | Survey of appropriate matching algorithms for large scale systems of differential algebraic equations

Title:
Survey of appropriate matching algorithms for large scale systems of differential algebraic equations
Author:
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
DOI:
10.3384/ecp12076433
Download:
Full text (pdf)
Year:
2012
Conference:
Proceedings of the 9th International MODELICA Conference; September 3-5; 2012; Munich; Germany
Issue:
076
Article no.:
045
Pages:
433-442
No. of pages:
10
Publication type:
Abstract and Fulltext
Published:
2012-11-19
ISBN:
978-91-7519-826-2
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press; Linköpings universitet


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

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

Author:
Jens Frenkel, Günter Kunze, Peter Fritzson
Title:
Survey of appropriate matching algorithms for large scale systems of differential algebraic equations
DOI:
10.3384/ecp12076433
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.

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

Author:
Jens Frenkel, Günter Kunze, Peter Fritzson
Title:
Survey of appropriate matching algorithms for large scale systems of differential algebraic equations
DOI:
10.3384/ecp12076433
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment