{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T16:26:01Z","timestamp":1777307161259,"version":"3.51.4"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,5,8]],"date-time":"2015-05-08T00:00:00Z","timestamp":1431043200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2015,5,8]]},"abstract":"<jats:p>\n            We present a solution method that, compared to the traditional Gauss-Seidel approach, reduces the time required to simulate the dynamics of large systems of rigid bodies interacting through frictional contact by one to two orders of magnitude. Unlike Gauss-Seidel, it can be easily parallelized, which allows for the physics-based simulation of systems with millions of bodies. The proposed\n            <jats:italic>accelerated projected gradient descent<\/jats:italic>\n            (APGD) method relies on an approach by Nesterov in which a quadratic optimization problem with conic constraints is solved at each simulation time step to recover the normal and friction forces present in the system. The APGD method is validated against experimental data, compared in terms of speed of convergence and solution time with the Gauss-Seidel and Jacobi methods, and demonstrated in conjunction with snow modeling, bulldozer dynamics, and several benchmark tests that highlight the interplay between the friction and cohesion forces.\n          <\/jats:p>","DOI":"10.1145\/2735627","type":"journal-article","created":{"date-parts":[[2015,5,11]],"date-time":"2015-05-11T16:30:57Z","timestamp":1431361857000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":75,"title":["Using Nesterov's Method to Accelerate Multibody Dynamics with Friction and Contact"],"prefix":"10.1145","volume":"34","author":[{"given":"Hammad","family":"Mazhar","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI"}]},{"given":"Toby","family":"Heyn","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, WI and Epic Systems, Verona, WI"}]},{"given":"Dan","family":"Negrut","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI"}]},{"given":"Alessandro","family":"Tasora","sequence":"additional","affiliation":[{"name":"University of Parma, Parma, Italy"}]}],"member":"320","published-online":{"date-parts":[[2015,5,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/zamm.201000073"},{"key":"e_1_2_1_2_1","first-page":"051305","article-title":"Penetration depth for shallow impact cratering","volume":"71","author":"Ambroso M. A.","year":"2005","journal-title":"Phys. Rev."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"E. Andersen and K. Andersen. 2000. The mosek interior point optimizer for linear programming: An implementation of the homogeneous algorithm. In High Performance Optimization H. Frenk K. Roos T. Terlaky and S. Zhang Eds. Springer 197--232.  E. Andersen and K. Andersen. 2000. The mosek interior point optimizer for linear programming: An implementation of the homogeneous algorithm. In High Performance Optimization H. Frenk K. Roos T. Terlaky and S. Zhang Eds. Springer 197--232.","DOI":"10.1007\/978-1-4757-3216-0_8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0349-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0590-7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/08905459608905271"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1047"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-008-9223-4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-011-0029-5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1899404.1899410"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1976.1101194"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.29"},{"key":"e_1_2_1_14_1","unstructured":"O. Bonnefon and G. Daviet. 2011. Quartic formulation of Coulomb 3D frictional contact. Tech. rep. Rapport Technique RT-0400 INRIA.  O. Bonnefon and G. Daviet. 2011. Quartic formulation of Coulomb 3D frictional contact. Tech. rep. Rapport Technique RT-0400 INRIA."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566623"},{"key":"e_1_2_1_16_1","first-page":"5","article-title":"Model for collisions in granular gases","volume":"53","author":"Brilliantov N. V.","year":"1996","journal-title":"Phys. Rev."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1051\/proc\/2009019"},{"key":"e_1_2_1_18_1","volume-title":"Comput. Rend. Sci. Paris 25","author":"A.","year":"1847"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"R. W. Cottle J.-S. Pang and R. E. Stone. 2009. The Linear Complementarity Problem. Academic Press New York.  R. W. Cottle J.-S. Pang and R. E. Stone. 2009. The Linear Complementarity Problem. Academic Press New York.","DOI":"10.1137\/1.9780898719000"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Symposium on Rock Mechanics.","author":"Cundall P.","year":"1971"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0148-9062(88)92293-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1680\/geot.1979.29.1.47"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024173"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0895-7177(98)00119-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmat1813"},{"key":"e_1_2_1_26_1","unstructured":"J. W. Demmel. 2011. SuperLu users' guide. http:\/\/crd.lbl.gov\/&sim;xiaoye\/SuperLU\/superlu&lowbar;ug.pdf.  J. W. Demmel. 2011. SuperLu users' guide. http:\/\/crd.lbl.gov\/&sim;xiaoye\/SuperLU\/superlu&lowbar;ug.pdf."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556789508805606"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243980.1243986"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0305040"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"D. M. Flickinger J. Williams and J. Trinkle. 2013. What's wrong with collision detection in multibody dynamic simulation&quest; In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA'13). 959--964.  D. M. Flickinger J. Williams and J. Trinkle. 2013. What's wrong with collision detection in multibody dynamic simulation&quest; In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA'13). 959--964.","DOI":"10.1109\/ICRA.2013.6630689"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the International Symposium on Contact Mechanics (CMIS'06)","author":"Glocker C."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882358"},{"key":"e_1_2_1_33_1","volume-title":"Computer-Aided Kinematics and Dynamics of Mechanical Systems","author":"Haug E. J."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.4513"},{"key":"e_1_2_1_36_1","unstructured":"Intel. 2013. The Intel math kernel library sparse matrix vector multiply format prototype package. http:\/\/software.intel.com\/en-us\/article\/the-intel-math-kernel-library-sparse-matrix-vector-multiply-format-prot otype-package.  Intel. 2013. The Intel math kernel library sparse matrix vector multiply format prototype package. http:\/\/software.intel.com\/en-us\/article\/the-intel-math-kernel-library-sparse-matrix-vector-multiply-format-prot otype-package."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.68.1259"},{"key":"e_1_2_1_38_1","unstructured":"K. L. Johnson. 1987. Contact Mechanics. Cambridge University Press.  K. L. Johnson. 1987. Contact Mechanics. Cambridge University Press."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(99)00034-1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/100800105"},{"key":"e_1_2_1_41_1","unstructured":"A. Li R. Serban and D. Negrut. 2013. A SPIKE-based approach for the parallel solution of sparse linear systems on GPU cards. Tech. rep. TR-2013-05 University of Wisconsin-Madison. http:\/\/sbel.wisc.edu\/documents\/TR-2013-05.pdf.  A. Li R. Serban and D. Negrut. 2013. A SPIKE-based approach for the parallel solution of sparse linear systems on GPU cards. Tech. rep. TR-2013-05 University of Wisconsin-Madison. http:\/\/sbel.wisc.edu\/documents\/TR-2013-05.pdf."},{"key":"e_1_2_1_42_1","volume-title":"The Physics of Granular Media","author":"Luding S."},{"key":"e_1_2_1_43_1","unstructured":"H. Mazhar J. Bollman E. Forti A. Praeger T. Osswald and D. Negrut 2013a. Studying the effect of powder geometry of the selective laser sintering process. Tech. rep. TR-2013-03 Simulation-Based Engineering Laboratory University of Wisconsin-Madison. http:\/\/sbel.wisc.edu\/documents\/TR-2013-03.pdf.  H. Mazhar J. Bollman E. Forti A. Praeger T. Osswald and D. Negrut 2013a. Studying the effect of powder geometry of the selective laser sintering process. Tech. rep. TR-2013-03 Simulation-Based Engineering Laboratory University of Wisconsin-Madison. http:\/\/sbel.wisc.edu\/documents\/TR-2013-03.pdf."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5194\/ms-4-49-2013"},{"key":"e_1_2_1_45_1","unstructured":"H. Mazhar D. Melanz M. Ferris and D. Negrut. 2014a. An analysis of several methods for handling hard-sphere frictional contact in rigid multibody dynamics. Tech. rep. TR-2014-11 Simulation-Based Engineering Laboratory University of Wisconsin-Madison. http:\/\/sbel.wisc.edu\/documents\/TR-2014-11.pdf.  H. Mazhar D. Melanz M. Ferris and D. Negrut. 2014a. An analysis of several methods for handling hard-sphere frictional contact in rigid multibody dynamics. Tech. rep. TR-2014-11 Simulation-Based Engineering Laboratory University of Wisconsin-Madison. http:\/\/sbel.wisc.edu\/documents\/TR-2014-11.pdf."},{"key":"e_1_2_1_46_1","unstructured":"H. Mazhar J. Schneider and D. Negrut. 2014b. Preliminary results for helical anchoring project. Tech. rep. TR-2014-10 Simulation-Based Engineering Laboratory. University of Wisconsin-Madison http:\/\/sbel.wisc.edu\/documents\/TR-2014-10.pdf.  H. Mazhar J. Schneider and D. Negrut. 2014b. Preliminary results for helical anchoring project. Tech. rep. TR-2014-10 Simulation-Based Engineering Laboratory. University of Wisconsin-Madison http:\/\/sbel.wisc.edu\/documents\/TR-2014-10.pdf."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11044-011-9246-y"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 3rd Biennial Joint Conference on Engineering Systems and Analysis (ESDA'96)","author":"Moreau J. J."},{"key":"e_1_2_1_49_1","unstructured":"A. Nemirovsky and D. B. Yudin. 1983. Problem Complexity and Method Efficiency in Optimization. John Wiley and Sons.  A. Nemirovsky and D. B. Yudin. 1983. Problem Complexity and Method Efficiency in Optimization. John Wiley and Sons."},{"key":"e_1_2_1_50_1","first-page":"372","article-title":"A method of solving a convex programming problem with convergence rate O (1\/k2)","volume":"27","author":"Nesterov Y.","year":"2003","journal-title":"Soviet Math. Doklady"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Nesterov Y.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"e_1_2_1_52_1","unstructured":"B. O'Donoghue and E. Candes. 2012. Adaptive restart for accelerated gradient schemes. ArXiv e-prints.  B. O'Donoghue and E. Candes. 2012. Adaptive restart for accelerated gradient schemes. ArXiv e-prints."},{"key":"e_1_2_1_53_1","unstructured":"T. Poschel and T. Schwager. 2005. Computational Granular Dynamics: Models and Algorithms. Springer.  T. Poschel and T. Schwager. 2005. Computational Granular Dynamics: Models and Algorithms. Springer."},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the Thematic Conference on Multibody Dynamics (ECCOMAS'09)","author":"Preclik T. M."},{"key":"e_1_2_1_55_1","unstructured":"T. M. Preclik and U. Rude. 2011. Solution existence and non-uniqueness of Coulomb friction. Tech. rep. 4 Friedrich-Alexander University Erlangen-Nurnberg Institut fur Informatik Nurnberg Germany.  T. M. Preclik and U. Rude. 2011. Solution existence and non-uniqueness of Coulomb friction. Tech. rep. 4 Friedrich-Alexander University Erlangen-Nurnberg Institut fur Informatik Nurnberg Germany."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2003.07.011"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2011.09.024"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185602"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599360110"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0207(19960815)39:15<2673::AID-NME972>3.0.CO;2-I"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2304576.2304624"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11012-013-9694-y"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijnonlinmec.2013.01.010"},{"key":"e_1_2_1_64_1","first-page":"315","article-title":"Large-scale parallel multi-body dynamics with frictional contact on the graphical processing unit","volume":"222","author":"Tasora A.","year":"2008","journal-title":"J. Multi-Body Dynam."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185601"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1115\/DETC2003\/VIB-48342"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.90.194301"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2003.10.025"},{"key":"e_1_2_1_69_1","volume-title":"Proc. Royal Soc. London Series A: Math. Phys. Engin. Sci. 455","author":"Vu-Quoc L.","year":"1991"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2735627","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2735627","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:35Z","timestamp":1750227395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2735627"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,8]]},"references-count":68,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,5,8]]}},"alternative-id":["10.1145\/2735627"],"URL":"https:\/\/doi.org\/10.1145\/2735627","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,8]]},"assertion":[{"value":"2014-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}