{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T16:28:13Z","timestamp":1721406493157},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,7,12]],"date-time":"2020-07-12T00:00:00Z","timestamp":1594512000000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1755544,CCF-1813624"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"Simulation methods are rapidly advancing the accuracy, consistency and controllability of elastodynamic modeling and animation. Critical to these advances, we require efficient time step solvers that reliably solve all implicit time integration problems for elastica. While available time step solvers succeed admirably in some regimes, they become impractically slow, inaccurate, unstable, or even divergent in others --- as we show here. Towards addressing these needs we present the Decomposed Optimization Time Integrator (DOT), a new domain-decomposed optimization method for solving the per time step, nonlinear problems of implicit numerical time integration. DOT is especially suitable for large time step simulations of deformable bodies with nonlinear materials and high-speed dynamics. It is efficient, automated, and robust at large, fixed-size time steps, thus ensuring stable, continued progress of high-quality simulation output. Across a broad range of extreme and mild deformation dynamics, using frame-rate size time steps with widely varying object shapes and mesh resolutions, we show that DOT always converges to user-set tolerances, generally well-exceeding and always close to the best wall-clock times across all previous nonlinear time step solvers, irrespective of the deformation applied.<\/jats:p>","DOI":"10.1145\/3306346.3322951","type":"journal-article","created":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T19:04:08Z","timestamp":1562958248000},"page":"1-10","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Decomposed optimization time integrator for large-step elastodynamics"],"prefix":"10.1145","volume":"38","author":[{"given":"Minchen","family":"Li","sequence":"first","affiliation":[{"name":"University of Pennsylvania & Adobe Research"}]},{"given":"Ming","family":"Gao","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}]},{"given":"Timothy","family":"Langlois","sequence":"additional","affiliation":[{"name":"Adobe Research"}]},{"given":"Chenfanfu","family":"Jiang","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}]},{"given":"Danny M.","family":"Kaufman","sequence":"additional","affiliation":[{"name":"Adobe Research"}]}],"member":"320","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"20","article-title":"2017. Fast Cholesky factorization on GPUs for batch and native modes","author":"Abdelfattah A.","year":"2017","unstructured":"A. Abdelfattah , A. Haidar , S. Tomov , and J. Dongarra . 2017. Fast Cholesky factorization on GPUs for batch and native modes in MAGMA. J of Comp Sci 20 ( 2017 ). A. Abdelfattah, A. Haidar, S. Tomov, and J. Dongarra. 2017. Fast Cholesky factorization on GPUs for batch and native modes in MAGMA. J of Comp Sci 20 (2017).","journal-title":"MAGMA. J of Comp Sci"},{"key":"e_1_2_2_2_1","doi-asserted-by":"crossref","unstructured":"U. M Ascher. 2008. Numerical methods for evolutionary differential equations. U. M Ascher. 2008. Numerical methods for evolutionary differential equations.","DOI":"10.1137\/1.9780898718911"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601116"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"e_1_2_2_5_1","volume-title":"Int Conf Math Comp Meth App Nucl Sci Eng.","author":"Brown J.","unstructured":"J. Brown and P. Brune . 2013. Low-rank quasi-Newton updates for robust Jacobian lagging in Newton-type methods . In Int Conf Math Comp Meth App Nucl Sci Eng. J. Brown and P. Brune. 2013. Low-rank quasi-Newton updates for robust Jacobian lagging in Newton-type methods. In Int Conf Math Comp Meth App Nucl Sci Eng."},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"J. C. Butcher. 2016. Numerical methods for ordinary differential equations. J. C. Butcher. 2016. Numerical methods for ordinary differential equations.","DOI":"10.1002\/9781119121534"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778775"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"e_1_2_2_9_1","doi-asserted-by":"crossref","unstructured":"P. Deufihard. 2011. Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms. P. Deufihard. 2011. Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms.","DOI":"10.1007\/978-3-642-23899-4"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"V. Dolean P. Jolivet and F. Nataf. 2015. An introduction to domain decomposition methods: algorithms theory and parallel implementation. V. Dolean P. Jolivet and F. Nataf. 2015. An introduction to domain decomposition methods: algorithms theory and parallel implementation.","DOI":"10.1137\/1.9781611974065"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2459687"},{"key":"e_1_2_2_12_1","unstructured":"E. Hairer C. Lubich and G. Wanner. 2006. Geometric Numerical Integration. E. Hairer C. Lubich and G. Wanner. 2006. Geometric Numerical Integration."},{"key":"e_1_2_2_13_1","unstructured":"E. Hairer S. P N\u00f8rsett and G. Wanner. 2008. Solving Ordinary Differential Equations I. E. Hairer S. P N\u00f8rsett and G. Wanner. 2008. Solving Ordinary Differential Equations I."},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"E. Hairer and G. Wanner. 1996. Solving Ordinary Differential Equations II. E. Hairer and G. Wanner. 1996. Solving Ordinary Differential Equations II.","DOI":"10.1007\/978-3-642-05221-7"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2231816.2231821"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2006.08.014"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0207(20001210)49:10<1295::AID-NME993>3.0.CO;2-W"},{"key":"e_1_2_2_18_1","first-page":"20","article-title":"1998. A fast and high quality multilevel scheme for partitioning irregular graphs","author":"Karypis G.","year":"1998","unstructured":"G. Karypis and V. Kumar . 1998. A fast and high quality multilevel scheme for partitioning irregular graphs . SIAM J on Sci Comp 20 ( 1998 ). G. Karypis and V. Kumar. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J on Sci Comp 20 (1998).","journal-title":"SIAM J on Sci Comp"},{"key":"e_1_2_2_19_1","volume-title":"Symp Comp Anim.","author":"Kharevych L.","unstructured":"L. Kharevych , W. Yang , Y. Tong , E. Kanso , J. E Marsden , P. Schr\u00f6der , and M. Desbrun . 2006. Geometric, variational integrators for computer animation . In Symp Comp Anim. L. Kharevych, W. Yang, Y. Tong, E. Kanso, J. E Marsden, P. Schr\u00f6der, and M. Desbrun. 2006. Geometric, variational integrators for computer animation. In Symp Comp Anim."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.78"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982430"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508406"},{"key":"e_1_2_2_23_1","first-page":"4","article-title":"2017","volume":"36","author":"Liu T.","year":"2017","unstructured":"T. Liu , S. Bouaziz , and L. Kavan . 2017 . Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Trans Graph 36 , 4 ( 2017 ). T. Liu, S. Bouaziz, and L. Kavan. 2017. Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Trans Graph 36, 4 (2017).","journal-title":"Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Trans Graph"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2994258.2994272"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964967"},{"key":"e_1_2_2_26_1","unstructured":"A. McAdams A. Selle R. Tamstorf J. Teran and E. Sifakis. 2011. Computing the singular value decomposition of 3X 3 matrices with minimal branching and elementary floating point operations. University of Wisconsin Madison (2011). A. McAdams A. Selle R. Tamstorf J. Teran and E. Sifakis. 2011. Computing the singular value decomposition of 3X 3 matrices with minimal branching and elementary floating point operations. University of Wisconsin Madison (2011)."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvcir.2007.01.005"},{"key":"e_1_2_2_28_1","volume-title":"Symp on Comp Anim.","author":"Narain R.","year":"2016","unstructured":"R. Narain , M. Overby , and G. E Brown . 2016 . ADMM ⊇ projective dynamics: fast simulation of general constitutive models .. In Symp on Comp Anim. R. Narain, M. Overby, and G. E Brown. 2016. ADMM ⊇ projective dynamics: fast simulation of general constitutive models.. In Symp on Comp Anim."},{"key":"e_1_2_2_29_1","volume-title":"Steepest descent and differential equations. J of the Mathematical Society of Japan 37, 2","author":"Neuberger JW","year":"1985","unstructured":"JW Neuberger . 1985. Steepest descent and differential equations. J of the Mathematical Society of Japan 37, 2 ( 1985 ). JW Neuberger. 1985. Steepest descent and differential equations. J of the Mathematical Society of Japan 37, 2 (1985)."},{"key":"e_1_2_2_30_1","unstructured":"J. Nocedal and S. Wright. 2006. Numerical Optimization. J. Nocedal and S. Wright. 2006. Numerical Optimization."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(98)00219-9"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2730875"},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","unstructured":"N. Parikh and S. Boyd. 2012. Block splitting for distributed optimization. N. Parikh and S. Boyd. 2012. Block splitting for distributed optimization.","DOI":"10.1007\/s12532-013-0061-8"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"A. Quarteroni A. Valli and P.M.A. Valli. 1999. Domain Decomposition Methods for Partial Differential Equations. A. Quarteroni A. Valli and P.M.A. Valli. 1999. Domain Decomposition Methods for Partial Differential Equations.","DOI":"10.1007\/978-94-011-4647-0_11"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275067"},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","unstructured":"S. Sell\u00e1n H. Y. Cheng Y. Ma M. Dembowski and A. Jacobson. 2018. Solid Geometry Processing on Deconstructed Domains. CoRR (2018). S. Sell\u00e1n H. Y. Cheng Y. Ma M. Dembowski and A. Jacobson. 2018. Solid Geometry Processing on Deconstructed Domains. CoRR (2018).","DOI":"10.1111\/cgf.13592"},{"key":"e_1_2_2_37_1","volume-title":"A modification of Newton's method. Ukrainian Mathematical J 19, 1","author":"Shamanskii VE","year":"1967","unstructured":"VE Shamanskii . 1967. A modification of Newton's method. Ukrainian Mathematical J 19, 1 ( 1967 ). VE Shamanskii. 1967. A modification of Newton's method. Ukrainian Mathematical J 19, 1 (1967)."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073618"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180491"},{"key":"e_1_2_2_40_1","volume-title":"Symp Comp Anim.","author":"Stomakhin A.","year":"2012","unstructured":"A. Stomakhin , R. Howes , C. Schroeder , and J. M Teran . 2012 . Energetically consistent invertible elasticity . In Symp Comp Anim. A. Stomakhin, R. Howes, C. Schroeder, and J. M Teran. 2012. Energetically consistent invertible elasticity. In Symp Comp Anim."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073368.1073394"},{"key":"e_1_2_2_42_1","unstructured":"C. Xiao-Chuan and D. Maksymilian. 1994. Domain Decomposition Methods for Monotone Nonlinear Elliptic Problems. In Contemporary Math. C. Xiao-Chuan and D. Maksymilian. 1994. Domain Decomposition Methods for Monotone Nonlinear Elliptic Problems. In Contemporary Math."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201359"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3306346.3322951","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3306346.3322951","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,18]],"date-time":"2023-09-18T07:03:17Z","timestamp":1695020597000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306346.3322951"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,12]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3306346.3322951"],"URL":"http:\/\/dx.doi.org\/10.1145\/3306346.3322951","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,12]]},"assertion":[{"value":"2019-07-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}