Achieving O(n) Complexity for Models from Modelica.Mechanics.Multibody

Christian Schubert
Professur für Baumaschinen- und Fördertechnik, Technische Universität Dresden, Dresden, Germany

Jens Frenkel
Professur für Baumaschinen- und Fördertechnik, Technische Universität Dresden, Dresden, Germany

Günter Kunze
Professur für Baumaschinen- und Fördertechnik, Technische Universität Dresden, Dresden, Germany

Michael Beitelschmidt
Professur für Dynamik und Mechanismentechnik, Technische Universität Dresden, Dresden, Germany

Ladda ner artikelhttp://dx.doi.org/10.3384/ecp12076705

Ingår i: Proceedings of the 9th International MODELICA Conference; September 3-5; 2012; Munich; Germany

Linköping Electronic Conference Proceedings 76:72, s. 705-712

Visa mer +

Publicerad: 2012-11-19

ISBN: 978-91-7519-826-2

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


When translating a model that uses elements from Modelica.Mechanics.MultiBody the Modelica Compiler has to deal with a large sparse linear system of equations. The application of Tearing yields a dense linear system usually of size equal to the number of degrees of freedom. Solving such a system for the unknowns requires O(n³) operations. From literature algorithms can be found that are able to solve a mechanical system in only O(n) operations. The way those algorithms have been formulated inhibited the application in a general equation based framework like Modelica. This paper presents a graph theoretical generalization of those O(n) algorithms which has been implemented into the OpenModelica Compiler (OMC). The performance of the new algorithm has been compared to Tearing by looking at several test models.


MultiBody; Relaxation; Gaussian Elimination; OpenModelica


[1] H. Elmqvist; and M. Otter: Methods for Tearing Systems of Equations in Object Oriented Modeling; Proc. ESM’94; European Simulation Multiconference; Barcelona; Spain; June 13; 1994; pp. 326-332.

[2] R. Featherstone: The calculation of robot dynamics using articulated-body inertias. International Journal of Robotics Research 2; May 1983; pp. 13-30. doi: 10.1177/027836498300200102.

[3] R. Featherstone: Rigid Body Dynamics Algorithms. Springer; New York; 2008. doi: 10.1007/978-0-387-74315-8.

[4] H. Brandl; R. Johanni and M. Otter: A very efficient algorithm for the simulation of robots and similar multibody systems without inversion of the mass matrix; In Kopacek; P.; Troth; I. and Desoyer; K. (Eds.); Theory of Robots; Oxford; Pergamon Press; 1988; pp. 95- 100

[5] M. Otter; H. Elmqvist; and F.E. Cellier: Relaxing: A symbolic sparse matrix method exploiting the model structure in generating efficient simulation code; Proc. Symp. Modelling; Analysis; and Simulation; CESA’96; IMACS MultiConference on Computational Engineering in Systems Applications; Lille; France; vol.1; 1995; pp. 1-12

[6] I.S. Duff; A.M. Ersiman; and J.K. Reid: Direct Methods for Sparse Matrices; Oxford University Press; 1986

[7] S.E. Mattsson and G. Söderlind: Index Reduction in Differential Algebraic Equations Using Dummy Derivatives; SIAM Journal on Scientific Computing; Vol. 14; No. 3; pp. 677-692; 1993. doi: 10.1137/0914043.

[8] R. Tarjan: Depth-first search and linear graph algorithms; 12th Annual Symposium on Switching and Automata Theory; 13-15 Oct.; 1971; pp. 114 - 121. doi: 10.1109/SWAT.1971.10.

[9] E. Carpanzano: Order Reduction of General Nonlinear DAE Systems by Automatic Tearing; Mathematical and Computer Modelling of Dynamical Systems; Vol. 6; Iss. 2; 2000

Citeringar i Crossref