zbMATH — the first resource for mathematics

A comparison of numerical methods for solving multibody dynamics problems with frictional contact modeled via differential variational inequalities. (English) Zbl 1439.74229
Summary: We investigate two classes of solvers used to determine the time evolution of large systems of rigid bodies that mutually interact through contact with friction. The contact is modeled through a complementarity condition; the friction is posed as a variational problem. The system dynamics is described by a set of differential algebraic equations coupled with differential variational inequalities (DVI). Upon discretization in time, the complementarity conditions enforced at the velocity level are relaxed to obtain a cone complementarity problem (CCP). The solution of the CCP, which becomes the simulation bottleneck, is found by minimizing an equivalent quadratic optimization problem with conic constraints. Herein, we investigate two classes of solvers for this constrained optimization problem. The projected Gauss-Jacobi (PGJ), projected Gauss-Seidel (PGS), and accelerated projected gradient descent (APGD) methods are exponents of the first class of solvers. They are first order, using only cost-function value and gradient information. The second class of solvers is represented by a symmetric cone interior point (SCIP) method and a primal-dual interior point (PDIP) method. These second order methods rely on a Newton step to identify the descent direction and a line search to compute the step size. All five methods draw on parallel computing on Graphics Processing Unit (GPU) cards; the Newton step employs a sparse parallel GPU solver. Two types of numerical experiments, filling and drafting, are carried out to evaluate the performance of the five solution strategies in terms of convergence rate, accuracy, and computational cost. For consistency, all numerical experiments were performed in the same open source code modified to host the five methods of interest.

74M15 Contact in solid mechanics
65L80 Numerical methods for differential-algebraic equations
70E55 Dynamics of multibody systems
Full Text: DOI
[1] Richard, P.; Nicodemi, M.; Delannay, R.; Ribiere, P.; Bideau, D., Slow relaxation and compaction of granular systems, Nat. Mater., 4, 2, 121-128 (2005)
[2] Stewart, D. E., Existence of solutions to rigid body dynamics and the Painlevé paradoxes, C. R. Acad. Sci., Paris, 325, 689-693 (1997)
[3] Haug, E. J., Computer-Aided Kinematics and Dynamics of Mechanical Systems, Vol. I (1989), Prentice-Hall: Prentice-Hall Englewood Cliffs, New Jersey
[4] Shabana, A. A., Computational Dynamics (1994), John Wiley & Sons
[5] Stewart, D. E., Rigid-body dynamics with friction and impact, SIAM Rev., 42, 1, 3-39 (2000)
[6] Stewart, D. E.; Trinkle, J. C., An implicit time-stepping scheme for rigid-body dynamics with inelastic collisions and coulomb friction, Internat. J. Numer. Methods Engrg., 39, 2673-2691 (1996)
[7] Anitescu, M.; Potra, F. A., Formulating dynamic multi-rigid-body contact problems with friction as solvable linear complementarity problems, Nonlinear Dynam., 14, 231-247 (1997)
[8] Hairer, E.; Wanner, G., Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems (1996), Springer: Springer Berlin
[9] Anitescu, M., Optimization-based simulation of nonsmooth rigid multibody dynamics, Math. Program., 105, 1, 113-143 (2006)
[10] Stewart, D. E., Convergence of a time-stepping scheme for rigid body dynamics and resolution of Painlevé’s problems, Arch. Ration. Mech. Anal., 145, 3, 215-260 (1998)
[11] Heyn, T., On the Modeling, Simulation, and Visualization of Many-Body Dynamics Problems with Friction and Contact (2013), Department of Mechanical Engineering, University of Wisconsin: Department of Mechanical Engineering, University of Wisconsin Madison
[12] Bertails-Descoubes, F.; Cadoux, F.; Daviet, G.; Acary, V., A nonsmooth Newton solver for capturing exact Coulomb friction in fiber assemblies, ACM Trans. Graph., 30, 1, 6 (2011)
[13] Daviet, G.; Bertails-Descoubes, F.; Boissieux, L., A hybrid iterative solver for robustly capturing Coulomb friction in hair dynamics, ACM Trans. Graph., 30, 6, 139 (2011)
[14] Acary, V.; Cadoux, F.; Lemarechal, C.; Malick, J., A formulation of the linear discrete Coulomb friction problem via convex optimization, ZAMM Z. Angew. Math. Mech., 91, 2, 155-175 (2011)
[15] Bonnefon, O.; Daviet, G., Quartic formulation of Coulomb 3D frictional contact , Technical Report RT-0400 (2011), INRIA: INRIA Grenoble
[16] Moreau, J. J.; Jean, M., Numerical treatment of contact and friction: The contact dynamics method, (Proceedings of the Third Biennial Joint Conference on Engineering Systems and Analysis (1996)), 201-208
[17] Anitescu, M.; Hart, G. D., A constraint-stabilized time-stepping approach for rigid multibody dynamics with joints, contact and friction, Internat. J. Numer. Methods Engrg., 60, 14, 2335-2371 (2004)
[19] Tasora, A.; Negrut, D.; Anitescu, M., Large-scale parallel multi-body dynamics with frictional contact on the Graphical Processing Unit, J. Multi-body Dyn., 222, 4, 315-326 (2008)
[21] Shojaaee, Z.; Shaebani, M. R.; Brendel, L.; Toeroek, J.; Wolf, D. E., An adaptive hierarchical domain decomposition method for parallel contact dynamics simulations of granular materials, J. Comput. Phys., 231, 2, 612-628 (2012)
[22] Tonge, R.; Benevolenski, F.; Voroshilov, A., Mass splitting for jitter-free parallel rigid body simulation, ACM Trans. Graph., 31, 4, 105 (2012)
[23] Heyn, T.; Anitescu, M.; Tasora, A.; Negrut, D., Using Krylov subspace and spectral methods for solving complementarity problems in many-body contact dynamics simulation, IJNME, 95, 7, 541-561 (2013)
[24] Mazhar, H.; Heyn, T.; Tasora, A.; Negrut, D., Using Nesterov’s method to accelerate multibody dynamics with friction and contact, ACM Trans. Graph., 34, 3 (2015)
[25] Fang, L., A Primal-Dual Interior Point Method for Solving Multibody Dynamics Problems with Frictional Contact, MS Thesis (2014), University of Wisconsin-Madison: University of Wisconsin-Madison Madison, WI, USA
[26] Kleinert, J., Simulating Granular Material using Nonsmooth Time-Stepping and a Matrix-Free Interior Point Method, PhD Thesis (2015), University of Kaiserslautern
[27] Anitescu, M.; Tasora, A., An iterative approach for cone complementarity problems for nonsmooth dynamics, Comput. Optim. Appl., 47, 2, 207-235 (2010)
[28] Tasora, A.; Anitescu, M., A matrix-free cone complementarity approach for solving large-scale, nonsmooth, rigid body dynamics, Comput. Methods Appl. Mech. Engrg., 200, 5-8, 439-453 (2011)
[29] Negrut, D.; Tasora, A.; Anitescu, M.; Mazhar, H.; Heyn, T.; Pazouki, A., Solving large multi-body dynamics problems on the GPU, GPU Gems, 4, 269-280 (2011)
[30] Nesterov, Y., A method of solving a convex programming problem with convergence rate \(O(1 / k^2)\), Sov. Math. Dokl., 27, 2, 372-376 (1983)
[31] Cauchy, A., Méthode générale pour la résolution des systemés d’équations simultanées, C. R. Sci. Paris, 25, 1847, 536-538 (1847)
[32] Bertsekas, D., On the Goldstein-Levitin-Polyak gradient projection method, IEEE Trans. Automat. Control, 21, 2, 174-184 (1976)
[33] Nemirovsky, A.; Yudin, D. B., Problem Complexity and Method Efficiency in Optimization (1983), John Wiley & Sons
[34] Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course (2003), Springer
[35] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009)
[36] Becker, S. R.; Candès, E. J.; Grant, M. C., Templates for convex cone problems with applications to sparse signal recovery, Math. Program. Comput., 3, 3, 165-218 (2011)
[38] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press
[39] Li, A.; Serban, R.; Negrut, D., Analysis of a splitting approach for the parallel solution of linear systems on GPU cards, SIAM J. Sci. Comput. (2017), (in press)
[40] Polizzi, E.; Sameh, A. H., A parallel hybrid banded system solver: the SPIKE algorithm, Parallel Comput., 32, 2, 177-194 (2006)
[41] Tasora, A.; Serban, R.; Mazhar, H.; Pazouki, A.; Melanz, D.; Fleischmann, J.; Taylor, M.; Sugiyama, H.; Negrut, D., Chrono: An open source multi-physics dynamics engine, (Kozubek, T., High Performance Computing in Science and Engineering -Lecture Notes in Computer Science (2016), Springer), 19-49
[43] Melanz, D., Physics-based Contact using the Complementarity Approach for Discrete Element Applications in Vehicle Mobility and Terramechanics, PhD Thesis (2016), University of Wisconsin-Madison
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.