Splitting Methods for Dry Frictional Contact Problems in Rigid Multibody Systems: Preliminary Performance Results

Claude Lacoursière
Vrlab/HPC2N and Computing Science, Umeå Universitet, Sweden \ CMLabs Simulations Inc. , Canada

Ladda ner artikelhttp://www.ep.liu.se/ecp_article/index.en.aspx?issue=010;article=004

Ingår i: The Annual SIGRAD Conference. Special Theme - Real-Time Simulations. Conference Proceedings from SIGRAD2003

Linköping Electronic Conference Proceedings 10:4, s. 11-16

Visa mer +

Publicerad: 2003-11-20


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


A splitting method for solving LCP based models of dry frictional contact problems in rigid multibody systems based on box MLCP solver is presented. Since such methods rely on fast and robust box MLCP solvers; several methods are reviewed and their performance is compared both on random problems and on simulation data. We provide data illustrating the convergence rate of the splitting method which demonstrates that they present a viable alternative to currently available methods.

CR Categories: G.1.6 [Mathematics of Computing]: OptimizationóNonlinear Programming I.3.5 [Computer Graphics]: Computational Geometry and Object ModelingóPhysically based modeling I.3.7 [Computer Graphics]: Three-Dimensional Graphics and RealismóVirtual Reality I.6.8 [Simulation and Modeling]: Types of SimulationóAnimation


Physics based modeling; constraints; LCP; dry friction; rigid multibody dynamics


AL-FAHED; A. M.; STRAVROULAKIS; G.; AND PANAGIOTOPOULOS; P. 1991. Hard and soft ngered robot grippers. the linear complementarity approach. Z. angew. Math. u. Mech. 71; 7/8; 257?265.

ALEFELD; G. E.; CHEN; X.; AND POTRA; F. A. 1999. Numerical validation of solutions of linear complementarity problems. Numerische Mathematik 83; 1; 1?24. Also available as preprint as report-102.ps from ftp.math.uiowa.edu.

ANITESCU; M.; AND POTRA; F. 1997. Formulating dynamic multi-rigidbody contact problems with friction as solvable linear complementarity problems. Nonlinear Dynamics 14; 231?247.

ANITESCU; M.; POTRA; F. A.; AND STEWART; D. E. 1999. Time-stepping for three-dimensional rigid body dynamics. Computer Methods in Applied Mechanics and Engineering 177; 183?197.

COTTLE; R. W.; PANG; J.-S.; AND STONE; R. E. 1992. The Linear Complementarity Problem. Computer Science and Scientic Computing. Academic Press; New York.

COTTLE; R. 1968. The principal pivot method of quadratic programming.In Mathematics of the Decision Sciences part I.; American Mathematical Society; Providence; RI.; G. Dantzig and A. V. Jr.; Eds.; vol. 11-12 of Lectures in Applied Mathematics; American Math. Society; 144?162.

DOST´A L; Z.; HASLINGER; J.; AND KUC ERA; R. 2002. Implementation of the xed point method in contact problems with coulomb friction based on a dual splitting type technique. J. of Comp. and Appl. Maht. 140; 245?256.

GOLDSTEIN; H. 1980. Classical Mechanics; second ed. Addison-Wesley; Reading; MA; USA.

GOLUB; G. H.; AND VAN LOAN; C. F. 1996. Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins Press; Baltimore.

GUENDELMAN; E.; BRIDSON; R.; AND RONALD FEDKIW. 2003. Nonconvex rigid bodies with stacking. In Proceedings of the ACM SIGGRAPH 2003; ACM Transactions on Graphics; J. Hart; Ed.; vol. 22; 871?878.

HAIRER; E.; AND WANNER; G. 1996. Solving Ordinary Differential Equations II: Stiff and Differential Algebraic Problems; second revised edition ed.; vol. 14 of Springer Series in Computational Mathematics. Springer-Verlag; Berlin; Heidelberg; New York; London; Paris; Tokyo; Hong Kong.

J´U DICE; J. J.; AND PIRES; F. M. 1994. A block principal pivoting algorithm for large-scale strictly monotone linear complementarity problems. Computers Ops Res. 21; 5; 587?596.

J´U DICE; J. J.; MACHADO; J.; AND FAUSTINO; A. 1992. An extension of the lemke’s method for the solution of a generalized linear complementarity problem. In System Modelling and Optimization; Springer-Verlag;
P. Kall; Ed.; vol. 180 of Lecture Notes in Control and Information Sciences; 221?230. Proc.; 15th IFIP TC7 Conference; Zurich; September 1991.

J´U DICE; J. J. 1994. Algorithms for linear complementarity problems. In Algorithms for Continuous Optimization; Kluwer Academic Publishers; E. Spedicato; Ed.; vol. 434 of NATO ASI Series C; Mathematical and Physical Sciences; Advanced Study Institute; NATO; 435?475.

KELLER; E. 1973. The general quadratic optimization problem. Mathematical Programming 5; 311?337.

KELLEY; C. T. 1995. Iterative Methods for Linear and Nonlinear Equations; vol. 16 of SIAM Frontiers. SIAM Publ.; Philadelphia.

KOSTREVA; M. M. 1978. Block pivot methods for solving the complementarity problem. Lin. Alg. Appl.; 21; 207?215.

LAYTON; R. A. 1998. Principles of Analytical System Dynamics. Mechanical Engineering Series. Springer-Verlag; Berlin; Heidelberg; New York; London; Paris; Tokyo; Hong Kong.

LEMKE; C. E. 1965. Bimatrix equilibrium points and mathematical programming. Management Science 11; 681?689.

LI; D.; AND FUKUSHIMA; M. 2000. Smoothing newton and quasi-newton methods for mixed complementarity problems. Comp. Opt. and Appl. 17; 203?230.

MILENKOVIC; V. J.; AND SCHMIDL; H. 2001. Optimization-based animation. In SIGGRAPH 2001 Conference Proceedings; August 12?17; 2001; Los Angeles; CA; Computer Graphics Proceedings; Annual Conference Series; 37?46.

MIRTICH; B.; AND CANNY; J. 1995. Impulse based simulation of rigid bodies. In Symposium on Interactive 3D Graphics; ACM Press; New York; ACM; 181?188.

MURTY; K. G. 1974. Note on a bard-type scheme for solving the complementarity problems. Opsearch 11; 123?130.

MURTY; K. G. 1988. Linear Complementarity; Linear and Nonlinear Programming. Helderman-Verlag; Heidelberg.

PANG; J.-S.; AND TRINKLE; J. C. 1996. Complementarity formulations and existence of solutions of dynamics multi-rigid-body contact problems with coulomb friction. Journal of Mathematical Computing 73; 2; 199.

PFEIFFER; F.; AND GLOCKER; C. 1996. Multibody Dynamics with Unilateral Contacts. Wiley Series in Nonlinear Science. John Wiley & Sons; New York; London; Sydney.

SARGENT; R. W. H. 1978. An effcient implementation of the lemke algorithm and its extension to deal with upper and lower bounds. Mathematical Programming Study 7; 36?54.

STEWART; D. E.; AND TRINKLE; J. 1996. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction. International Journal for N erical Methods in Engineering 39; 2673?2691.

STEWART; D. E. 1997. Existence of solutions to rigid body dynamics and the painlev´e paradoxes. C. R. Acad. Sci. Paris 325; S´erie I; 689?693.

TRINKLE; J. C.; PANG; J.; SUDARSKY; S.; AND LO; G. 1997. On dynamic multi-rigid-body contact problems with coulomb friction. Z. angew. Math. u. Mech. 77; 4; 267?279.

TZITZOURIS; J. A. 2001. Numerical Resolution of Frictional Multi-Rigid- Body Systems via Fully Immplicit Time-Stepping and Nonlinear Complementarity. PhD thesis; Johns Hopkins University. S

IMUNOVI´C ; S.; AND SAIGAL; S. 1994. Frictional contact formulation using quadratic programming. Computational Mechanics 15; 173?187.

ZHANG; L.; AND GAO; Z. 2003. Quadratic one-step smoothing newton method for p0 lcp without strict complementarity. Appl. Math. and Comp. 140; 367?379.

Citeringar i Crossref