“Updated Sparse Cholesky Factors for Corotational Elastodynamics” by Hecht, Lee, Shewchuk and O’Brien

We present warp-canceling corotation, 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.

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.Google Scholar
Belytschko, T. and Hsieh, B. 1979. Application of higher order corotational stretch theories to nonlinear finite element analysis. Comput. Struct. 11, 175–182.Google ScholarCross Ref
Bergou, M., Wardetzky, M., Robinson, S., Audoly, B., and Grinspun, E. 2008. Discrete elastic rods. ACM Trans. Graph. 27, 3, 63:1–63:12. Google ScholarDigital Library
Botsch, M., Bommes, D., and Kobbelt, L. 2005. Efficient linear system solvers for mesh processing. In Proceedings of the IMA Conference on the Mathematics of Surfaces. Springer, 62–83. Google ScholarDigital Library
Bridson, R., Fedkiw, R., and Muller-Fischer, M. 2006. Fluid simulation: SIGGRAPH course notes. In ACM SIGGRAPH Courses. 1–87. Google ScholarDigital Library
Bridson, R., Marino, S., and Fedkiw, R. 2003. Simulation of clothing with folds and wrinkles. In Proceedings of the Symposium on Computer Animation. 28–36. Google ScholarDigital Library
Chen, Y., Davis, T. A., Hager, W. W., and Rajamanickam, S. 2008. Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Trans. Math. Softw. 35, 22:1–22:14. Google ScholarDigital Library
Chentanez, N., Alterovitz, R., Ritchie, D., Cho, L., Hauser, K. K., Goldberg, K., Shewchuk, J. R., and O’Brien, J. F. 2009. Interactive simulation of surgical needle insertion and steering. ACM Trans. Graph. 28, 3, 88.1–88.10. Google ScholarDigital Library
Choi, M. G. and Ko, H.-S. 2005. Modal warping: Real-Time simulation of large rotational deformation and manipulation. IEEE Trans. Vis. Comput. Graph. 11, 1, 91–101. Google ScholarDigital Library
Cholesky, A.-L. 1910. Sur la résolution numérique des systèmes d’équations linéaires. Manuscript. Subsequently published in Bull. de la Sabix 39, 81–95, 2005.Google Scholar
Courtecuisse, H., Allard, J., Duriez, C., and Cotin, S. 2010. Asynchronous preconditioners for efficient solving of non-linear deformations. In Proceedings of the 7th Workshop on Virtual Reality Interaction and Physical Simulation. 59–68.Google Scholar
Davis, T. A. 2006. Direct Methods for Sparse Linear Systems. Fundamentals of Algorithms, vol. 2, SIAM. Google ScholarDigital Library
Davis, T. A. and Hager, W. W. 1999. Modifying a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 20, 3, 606–627. Google ScholarDigital Library
Davis, T. A. and Hager, W. W. 2009. Dynamic supernodes in sparse Cholesky update/downdate and triangular solves. ACM Trans. Math. Softw. 35, 4. Google ScholarDigital Library
Etzmuss, O., Keckeisen, M., and Strasser, W. 2003. A fast finite element solution for cloth modelling. In Proceedings of the 11th Pacific Conference on Computer Graphics and Applications. 244–251. Google ScholarDigital Library
Felippa, C. 2007. Introduction to finite element methods. http://www.colorado.edu/engineering/cas/courses.d/NFEM.d.Google Scholar
George, A. 1973. Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10, 2, 345–363.Google ScholarDigital Library
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.Google Scholar
Gill, P. E., Golub, G. H., Murray, W., and Saunders, M. A. 1974. Methods for modifying matrix factorizations. Math. Comput. 28, 126, 505–535.Google Scholar
Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations, 3rd Ed. The Johns Hopkins University Press. Google ScholarDigital Library
Gould, N. I. M., Scott, J. A., and Hu, Y. 2007. A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations. ACM Trans. Math. Softw. 33, 2, 1–32. Google ScholarDigital Library
Grcar, J. F. 2011. John von Neumann’s analysis of Gaussian elimination and the origins of modern numerical analysis. SIAM Rev. 53, 4, 607–682. Google ScholarDigital Library
Grinspun, E., Hirani, A. N., Desbrun, M., and Schröder, P. 2003. Discrete shells. In Proceedings of the Symposium on Computer Animation. 62–67. Google ScholarDigital Library
Hestenes, M. R. and Stiefel, E. 1952. Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bureau Standards 49, 409–436.Google ScholarCross Ref
Horn, B. K. P. 1987. Closed-Form solution of absolute orientation using unit quaternions. J. Opt. Soc. A 4, 4, 629–642.Google ScholarCross Ref
Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the Symposium on Computer Animation. 131–140. Google ScholarDigital Library
Karypis, G. and Kumar, V. 1995. A fast and high quality multilevel scheme for partitioning irregular graphs. In Proceedings of the International Conference on Parallel Processing. 113–122.Google Scholar
Li, X. S. and Demmel, J. W. 1999. A scalable sparse direct solver using static pivoting. In Proceedings of the 9th SIAM Conference on Parallel Processing for Scientic Computing. 1–10.Google Scholar
Lipton, R. J., Rose, D. J., and Tarjan, R. E. 1979. Generalized nested dissection. SIAM J. Numer. Anal. 16, 2, 346–358.Google ScholarDigital Library
Martin, S., Kaufmann, P., Botsch, M., Grinspun, E., and Gross, M. 2010. Unified simulation of elastic rods, shells, and solids. ACM Trans. Graph. 29, 4, 39:1–39:10. Google ScholarDigital Library
Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. 2002. Stable real-time deformations. In Proceedings of the Symposium on Computer Animation. 49–54. Google ScholarDigital Library
Müller, M. and Gross, M. 2004. Interactive virtual materials. In Proceedings of Graphics Interface Conference. 239–246. Google ScholarDigital Library
Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. 24, 3, 471–478. Google ScholarDigital Library
Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2006. Physically based deformable models in computer graphics. Comput. Graph. Forum 25, 4, 809–836.Google ScholarCross Ref
Nour-Omid, B. and Rankin, C. C. 1991. Finite rotation analysis and consistent linearization using projectors. Comput. Meth. Appl. Mechan. Engin. 93, 353–384.Google ScholarCross Ref
Parker, E. G. and O’Brien, J. F. 2009. Real-Time deformation and fracture in a game environment. In Proceedings of the Symposium on Computer Animation. 156–166. Google ScholarDigital Library
Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 2002. Numerical Recipes in C++: The Art of Scientific Computing. Cambridge University Press. Google ScholarDigital Library
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. Google ScholarDigital Library
Sorkine, O., Cohen-Or, D., Irony, D., and Toledo, S. 2005. Geometry-Aware bases for shape approximation. IEEE Trans. Vis. Comput. Graph. 11, 2, 1–11. Google ScholarDigital Library
Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Proceedings of SIGGRAPH Conference. 205–214. Google ScholarDigital Library
Toledo, S. 2003. TAUCS: A library of sparse linear solvers. http://www.tau.ac.il/~stoledo/taucs.Google Scholar
Zhu, Y., Sifakis, E., Teran, J., and Brandt, A. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. 29, 2, 16:1–16:18. Google ScholarDigital Library