{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:42:28Z","timestamp":1787017348560,"version":"build-2736575974"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2012,8,6]],"date-time":"2012-08-06T00:00:00Z","timestamp":1344211200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["CCF-0635381 and IIS-0915462"],"award-info":[{"award-number":["CCF-0635381 and IIS-0915462"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0635381 and IIS-0915462"],"award-info":[{"award-number":["CCF-0635381 and IIS-0915462"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005595","name":"University of California","doi-asserted-by":"publisher","award":["09-LR-01-118889-OBRJ"],"award-info":[{"award-number":["09-LR-01-118889-OBRJ"]}],"id":[{"id":"10.13039\/100005595","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2012,8,6]]},"abstract":"<jats:p>\n                    We present\n                    <jats:italic>warp-canceling corotation<\/jats:italic>\n                    , a nonlinear finite element formulation for elastodynamic simulation that achieves fast performance by making only partial or delayed changes to the simulation's linearized system matrices. Coupled with an algorithm for incremental updates to a sparse Cholesky factorization, the method realizes the stability and scalability of a sparse direct method without the need for expensive refactorization at each time step. This finite element formulation combines the widely used corotational method with stiffness warping so that changes in the per-element rotations are initially approximated by inexpensive per-node rotations. When the errors of this approximation grow too large, the per-element rotations are selectively corrected by updating parts of the matrix chosen according to locally measured errors. These changes to the system matrix are propagated to its Cholesky factor by incremental updates that are much faster than refactoring the matrix from scratch. A nested dissection ordering of the system matrix gives rise to a hierarchical factorization in which changes to the system matrix cause limited, well-structured changes to the Cholesky factor. We show examples of simulations that demonstrate that the proposed formulation produces results that are visually comparable to those produced by a standard corotational formulation. Because our method requires computing only partial updates of the Cholesky factor, it is substantially faster than full refactorization and outperforms widely used iterative methods such as preconditioned conjugate gradients. Our method supports a controlled trade-off between accuracy and speed, and unlike most iterative methods its performance does not slow for stiffer materials but rather it actually improves.\n                  <\/jats:p>","DOI":"10.1145\/2231816.2231821","type":"journal-article","created":{"date-parts":[[2012,9,11]],"date-time":"2012-09-11T18:21:06Z","timestamp":1347387666000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":58,"title":["Updated sparse cholesky factors for corotational elastodynamics"],"prefix":"10.1145","volume":"31","author":[{"given":"Florian","family":"Hecht","sequence":"first","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yeon Jin","family":"Lee","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan R.","family":"Shewchuk","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James F.","family":"O'Brien","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,9,7]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Barrett R. Berry M. Chan T. Demmel J. Donato J. Dongarra J. Eijkhout V. Pozo R. Romine C. and van der Vorst H. 1993. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM Pennsylvania PA.  Barrett R. Berry M. Chan T. Demmel J. Donato J. Dongarra J. Eijkhout V. Pozo R. Romine C. and van der Vorst H. 1993. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM Pennsylvania PA.","DOI":"10.1137\/1.9781611971538"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7949(79)90085-3"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360662"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11537908_5"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1185657.1185730"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the Symposium on Computer Animation. 28--36","author":"Bridson R."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531394"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.13"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Cholesky A.-L. 1910. Sur la r\u00e9solution num\u00e9rique des syst\u00e8mes d'\u00e9quations lin\u00e9aires. Manuscript. Subsequently published in Bull. de la Sabix 39 81--95 2005.  Cholesky A.-L. 1910. Sur la r\u00e9solution num\u00e9rique des syst\u00e8mes d'\u00e9quations lin\u00e9aires. Manuscript. Subsequently published in Bull. de la Sabix 39 81--95 2005.","DOI":"10.4000\/sabix.529"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the 7th Workshop on Virtual Reality Interaction and Physical Simulation. 59--68","author":"Courtecuisse H."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1196434"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897321076"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1462173.1462176"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the 11th Pacific Conference on Computer Graphics and Applications. 244--251","author":"Etzmuss O."},{"key":"e_1_2_2_16_1","unstructured":"Felippa C. 2007. Introduction to finite element methods. http:\/\/www.colorado.edu\/engineering\/cas\/courses.d\/NFEM.d.  Felippa C. 2007. Introduction to finite element methods. http:\/\/www.colorado.edu\/engineering\/cas\/courses.d\/NFEM.d."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"e_1_2_2_18_1","unstructured":"Gibson S. F. F. and Mirtich B. 1997. A survey of deformable modeling in computer graphics. Tech. rep. TR97-19 Mitsubishi Electric Research Laboratory. November.  Gibson S. F. F. and Mirtich B. 1997. A survey of deformable modeling in computer graphics. Tech. rep. TR97-19 Mitsubishi Electric Research Laboratory. November."},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Gill P. E. Golub G. H. Murray W. and Saunders M. A. 1974. Methods for modifying matrix factorizations. Math. Comput. 28 126 505--535.  Gill P. E. Golub G. H. Murray W. and Saunders M. A. 1974. Methods for modifying matrix factorizations. Math. Comput. 28 126 505--535.","DOI":"10.1090\/S0025-5718-1974-0343558-6"},{"key":"e_1_2_2_20_1","unstructured":"Golub G. H. and Van Loan C. F. 1996. Matrix Computations 3rd Ed. The Johns Hopkins University Press.   Golub G. H. and Van Loan C. F. 1996. Matrix Computations 3rd Ed. The Johns Hopkins University Press."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236465"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734716"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the Symposium on Computer Animation. 62--67","author":"Grinspun E."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.4.000629"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028523.1028541"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the International Conference on Parallel Processing. 113--122","author":"Karypis G."},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the 9th SIAM Conference on Parallel Processing for Scientic Computing. 1--10","author":"Li X. S."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778776"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/545261.545269"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of Graphics Interface Conference. 239--246","author":"M\u00fcller M."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073216"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2006.01000.x"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7825(91)90248-5"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1599470.1599492"},{"key":"e_1_2_2_37_1","unstructured":"Press W. H. Teukolsky S. A. Vetterling W. T. and Flannery B. P. 2002. Numerical Recipes in C&plus;&plus;: The Art of Scientific Computing. Cambridge University Press.   Press W. H. Teukolsky S. A. Vetterling W. T. and Flannery B. P. 2002. Numerical Recipes in C&plus;&plus;: The Art of Scientific Computing. Cambridge University Press."},{"key":"e_1_2_2_38_1","unstructured":"Shewchuk J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. Tech. rep. CMU-CS-94-125 School of Computer Science Carnegie Mellon University Pittsburgh PA.   Shewchuk J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. Tech. rep. CMU-CS-94-125 School of Computer Science Carnegie Mellon University Pittsburgh PA."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.33"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/37401.37427"},{"key":"e_1_2_2_41_1","volume-title":"TAUCS: A library of sparse linear solvers","author":"Toledo S.","year":"2003"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1731047.1731054"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2231816.2231821","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2231816.2231821","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:48:52Z","timestamp":1750222132000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2231816.2231821"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,6]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,8,6]]}},"alternative-id":["10.1145\/2231816.2231821"],"URL":"https:\/\/doi.org\/10.1145\/2231816.2231821","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,6]]},"assertion":[{"value":"2011-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-09-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}