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

Christian Schubert; Jens Frenkel; Günter Kunze; Michael Beitelschmidt

Title:

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:

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

Export in BibTex, RIS or text

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:

http://dx.doi.org/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:

https://doi.org10.3384/ecp12076705

Note: the following are taken directly from CrossRef

Citations:

No citations available at the moment

Responsible for this page: Peter Berkesand
Last updated: 2019-11-06