Article | Proceedings of the 9th International MODELICA Conference; September 3-5; 2012; Munich; Germany | Achieving O(n) Complexity for Models from Modelica.Mechanics.Multibody

Title:
Achieving O(n) Complexity for Models from Modelica.Mechanics.Multibody
Author:
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
DOI:
10.3384/ecp12076705
Download:
Full text (pdf)
Year:
2012
Conference:
Proceedings of the 9th International MODELICA Conference; September 3-5; 2012; Munich; Germany
Issue:
076
Article no.:
072
Pages:
705-712
No. of pages:
8
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


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.

Keywords: MultiBody; Relaxation; Gaussian Elimination; OpenModelica

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

Author:
Christian Schubert, Jens Frenkel, Günter Kunze, Michael Beitelschmidt
Title:
Achieving O(n) Complexity for Models from Modelica.Mechanics.Multibody
DOI:
10.3384/ecp12076705
References:
[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

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

Author:
Christian Schubert, Jens Frenkel, Günter Kunze, Michael Beitelschmidt
Title:
Achieving O(n) Complexity for Models from Modelica.Mechanics.Multibody
DOI:
10.3384/ecp12076705
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment